HDU 3549 Flow Problem(有向边网络流)
九野的博客，转载请注明出处 ：http://blog.csdn.net/acmmmm/article/details/11221561
题意：T个测试数据
下面n，m表示n个点m条有向带权边
m条边
问：从1-n最大流多少
测板子的题目，没啥思路
下面用的是dinic，开始没有考虑反向弧debug了好久，附赠一大坨测试数据
#include <iostream>#include <string>#include <cstring>#include <algorithm>#include <cstdio>#include <cctype>#include <queue>#include <stdlib.h>#include <cstdlib>#include <math.h>#include <set>#include <vector>#define inf 100000000#define eps 1e-8#define N 205#define M 1050#define ll intusing namespace std;inline ll Max(ll a,ll b){return a>b?a:b;}inline ll Min(ll a,ll b){return a<b?a:b;}//M为边数 N为点数 从1-n//M为边数 N为点数 从1-nstruct Edge{int from,to,flow,cap, nex;}edge[M*2];//双向边，注意RE 注意这个模版是 相同起末点的边 合并而不是去重int head[N],edgenum;//2个要初始化-1和0void addedge(int u,int v,int cap){//网络流要加反向弧Edge E={u,v,0,cap,head[u]};edge[edgenum]=E;head[u]=edgenum++;Edge E2={v,u,0,0,head[v]}; //这里的cap若是单向边要为0edge[edgenum]=E2;head[v]=edgenum++;}int dis[N],cur[N];//距离起点的距离 cur[i]表示i点正在考虑的边 优化不再考虑已经用过的点 初始化为headbool vis[N];bool BFS(int Start,int End){memset(vis,0,sizeof(vis)); memset(dis,-1,sizeof(dis));queue<int>Q;while(!Q.empty())Q.pop();Q.push(Start);dis[Start]=0;vis[Start]=1;while(!Q.empty()){int u = Q.front(); Q.pop();for(int i=head[u];i!=-1;i=edge[i].nex){Edge E =edge[i];if(!vis[E.to] && E.cap>E.flow){vis[E.to]=1;dis[E.to]=dis[u]+1;if(E.to==End)return true;Q.push(E.to);}}}return false;}int DFS(int x, int a,int End){//流入x 的流量是aif(x==End || a==0)return a;int flow = 0, f;for(int& i=cur[x];i!=-1;i=edge[i].nex){Edge& E = edge[i];if(dis[x]+1 == dis[E.to] && (f = DFS(E.to , Min(a, E.cap-E.flow), End))>0 ){E.flow += f;edge[ i^1 ].flow -= f;//反向边要减掉flow += f;a -= f;if(a==0)break;}}return flow;}int Maxflow(int Start,int End){int flow=0; while(BFS(Start,End)){memcpy(cur,head,sizeof(head));//把head的数组复制过去flow += DFS(Start, inf, End);}return flow;}int main() {int T,Cas=1,n,m,i,a,b,c;scanf("%d",&T);while (T--) {memset(head,-1,sizeof(head));edgenum=0;scanf("%d %d",&n,&m);while(m--){scanf("%d %d %d",&a,&b,&c);addedge(a,b,c);}printf("Case %d: %d\n",Cas++,Maxflow(1,n));}return 0;}/*993 21 2 12 3 13 31 2 12 3 11 3 13 21 3 21 3 53 21 2 4561 2 564313 3 1 3 1001 1 1001 1 10011 151 2 1 1 3 11 4 12 5 12 6 13 7 13 8 14 9 14 10 15 11 16 11 17 11 18 11 19 11 110 11 111 151 2 21 3 21 4 22 5 12 6 13 7 13 8 14 9 14 10 15 11 16 11 17 11 18 11 19 11 110 11 111 151 2 21 3 11 4 22 5 12 6 13 7 13 8 14 9 14 10 15 11 16 11 17 11 18 11 19 11 110 11 12 02 11 2 46514 41 2 102 1 52 4 201 3 34 51 2 102 1 52 4 201 3 33 4 19 101 5 22 4 62 3 4 1 2 93 9 55 9 42 3 14 2 16 7 13 7 24 41 2 101 3 23 4 12 4 14 41 2 11 3 13 4 102 4 10ans:1270100365046511011722*/