今天做题实在是杯具，A了最水的一题后，看另外一道字符串题，想到以前写过一道动态规划的类似匹配问题，可这题数据实在是有点在，估计了复杂度以后我竟然把千万级的复杂度看成了百万级的了，写了代码，过了样例，优化了几次也也超时，吐血啊，这时小强和ly把另外一题的题意给我说了一下，唉，被刚才那题弄郁闷了，没啥心思，不过也没其它办法，看了一下，感觉他们的思路是对的，就让他说写，结果超时，然后我又用线段树敲，最后还是超时，真的是想吐血哦，最后终于想到了O（N）的算法，其实也不难想，咋就没想到直接用O（N）的呢

题意：给定n个开区间，给区间赋一定的值，求取舍某些区间，使取得的值总和最大，前提是所取的区间覆盖某一个或一些点不超过K次

算法：对n个区间的端点进行离散化，离散化后的点i->i+1连一条边，容量为k, 费用为0， 对于离散化后的线段u,v从u->v 连一条边，容量为1，费用为-w[u,v], 然后从源点向1（离散化后的最左边点）连一条边，容量为k,费用为0，再从离散化后的最右边点right向汇点right+1连一条边，容量为k,费用为0,因为要求每个点的覆盖不超过k次，

题意：n个人，m种类别，每个人有分别对应的一些类别，把这n个人分在m种类别中，使人数最多的类别中的人类最少，也就是最多中求最少

算法：二分答案，构图时把二分后的值作为每个类别到汇点的容量, 源点向每个人连一条边，容量为1，每个人向可以加进的组连一条边，容量也为1，求最大流，如果流值为n，表示该方案可以，再进行二分，

#include 

题意：给定n头牛和B个牛场，每个牛场有一个容量，每头牛把对B个牛场的喜爱程序排成序列，把n头牛分到一些牛场里面，使得每头牛对它所在的牛场的喜欢程度的最大最小差值最小，输出这个范围大小，

算法：枚举差值 再枚举每个范围，构图求最大流，如果最大流等于n则表示此差值满足要求（差值从最小开始枚举的情况）输出

#include 

题目大意：有k个牛奶加工场，每个加工厂有一个容纳牛奶的头数上限，且都为m,有c头奶牛，每头奶牛都有一个位置，奶牛，加工厂，奶牛和工厂之间有一些道路，在所有的奶牛都能到一个加工厂里面的前提下，找出走过距离最远中的最短距离

算法：先用floyed算出每头奶牛到每个加工厂的最短距离，（我把距离存储到一个dis数组，为的是二分答案), 最后再用求最大流方法求出最后答案）

算法：最大流 构图的时候要仔细

刚开始我用dinic写，居然TLE，，构图后点数最多为372个点，边数最多为720和，dinic复杂度为O(n^2*E) 感觉1s也差不多要耗完，想到最大流的流量比较小，FF算法复杂度为O(EM), E为边数，M为最大流量，能承受，于是用FF过了，641ms, 还得优化啊

#include 

给定一个由n 行数字组成的数字梯形如下图所示。梯形的第一行有m个数字。从梯形的顶部的m个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。
规则1：从梯形的顶至底的m条路径互不相交。
规则2：从梯形的顶至底的m条路径仅在数字结点处相交。
规则3：从梯形的顶至底的m条路径允许在数字结点相交或边相交。

最小费用流，主要构图的时候要小心。

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define INF 1<<30
#define SIZE 800
struct Edge
{
int u, v, c, w, next;
}edge[SIZE*3];
int bg[SIZE];
int n, m;
int mset;
int pre[SIZE];
bool visit[SIZE];
int dist[SIZE];
void addEdge( int u, int v, int c, int w)

难得的一次提交一次AC，提交的时候心里都没底。嘿嘿，一A。主要是在建图的时候要小心，这里最容易出错。然后用最大流模板就可以了。

写得有点乱，将就看吧。

#include<iostream>
#include<queue>
using namespace std;
#define SIZE 105
#define oo 21000000
int n, m, k;
struct node
{
char device[30], other[30];
}devices[SIZE],

//最小费用最大流。

#include<iostream>
#include<queue>
using namespace std;
#define SIZE 51
#define INF 1<<30
struct Edge
{
int u, v, c, w, next;
}edge[SIZE*SIZE*SIZE];
int N, M, K;
int order[SIZE][SIZE];
int supply[SIZE][SIZE];
int cost[SIZE][SIZE][SIZE];
int bg[SIZE*3];
int dist[SIZE*3];
int pre[SIZE*3];
bool visit[SIZE*3

//http://acm.pku.edu.cn/JudgeOnline/problem?id=3422

算法：最小费用流。把一个点拆成两个点，u, u', u->u'加一条边，容量为1,费用为点值取反，注意因为走过这条边之后以后还可以走。所以还要在这两点之间加一条边，容易为m-1(即最多走m次，费用为0，再从u'向另外两个可以走的点加边，容易为m,费用为0, ......同样反向边的容量为0，但费用为点的值。图建好之后用SPFA算法每次找最小费用路径，迭代相加当流量为m时最后就是最小费用流

//混合图的欧拉回路。我用的最大流，还有一种搜索死活没AC。有空再看看吧。

#include<iostream>
#include<queue>
using namespace std;
#define SIZE 209
#define oo 2100000000
int map[SIZE][SIZE];
int n, m;
bool visited[SIZE];
int level[SIZE];
int father[SIZE];
int source;
int maxflow;
int indegree[SIZE], outdegree[SIZE];
int deg[SIZE];
void DFS(

//这道题我会的邻接矩阵做，一直WA，看了网上的算法，几本上都是用邻接表做的。有些看着还比较烦人，我还是用惯了邻接矩阵，纠结了很久才AC，分析原因主要有两点。一是在判断边是否可以增流的时候。枚举不全面。唉。还是网络流理解还有点差。刚开始只枚举了正向边，反向边没有枚举所以一直WA。

我的代码：

#include<iostream>
#include<queue>
using namespace std;