/*Date : 2015-8-21 晚上Author : ITAKMotto :今日的我要超越昨日的我，明日的我要胜过今日的我；以创作出更好的代码为目标，不断地超越自己。*/#include #include using namespace std;///oo表示无穷大const int oo = 1e9+5;///mm表示边的最大数量，因为要双向建边const int mm = 111111;///点的最大数量const int mn = 1000;///node:节点数,src:源点,dest:汇点,edge:边数int node, src, dest, edge;///ver:边指向的结点,flow:边的流量,next:链表的下一条边int ver[mm], flow[mm], next[mm];///head:节点的链表头,work:用于算法中的临时链表头,dis:距离int head[mn], work[mn], dis[mn], q[mn];///初始化void Init(int _node, int _src, int _dest){ node = _node, src = _src, dest = _dest; for(int i=0; i =0; i=next[i]) if(flow[i] && dis[v=ver[i]]<0) { ///这条边必须有剩余流量 dis[q[r++]=v] = dis[u] + 1; if(v == dest) return 1; } return 0;}///寻找可行流的增广路算法，按节点的距离来找，加快速度int Dinic_dfs(int u, int exp){ if(u == dest) return exp; ///work 是临时链表头，这里用 i 引用它，这样寻找过的边不再寻找* for(int &i=work[u],v,tmp; i>=0; i=next[i]) { if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0) { ///正反向边容量改变 flow[i] -= tmp; flow[i^1] += tmp; return tmp; } } return 0;}///求最大流，直到没有可行流int Dinic_flow(){ int i, ret=0, data; while(Dinic_bfs()) { for(i=0; i