hdu3549Flow Problem（最大流模板题）

题目链接：

http://acm.split.hdu.edu.cn/showproblem.php?pid=3549

题目大意：

n个点m条边，找到1到n使得流量最大。

题目思路：

最大流模板题，这里用到了Dinic算法，学习传送门--》https://comzyh.com/blog/archives/568/《--

代码：

#include 
using namespace std;  
  
const int maxn=1000;  
  
struct node{  
    int u,v,next,c;  
};  
node edge[maxn<<1];  
int head[maxn];  
int cnt;  
int dis[maxn];  
int n,m;//n是边的个数，m是顶点个数 
int ans; //最大流 
  
  
void init(){  
    memset(head,-1,sizeof(head));  
    cnt=0;  
    memset(dis,-1,sizeof(dis));  
    ans=0;  
}  
  
void add(int a,int b,int c){  //建立邻接表 
    edge[cnt].u=a;  
    edge[cnt].v=b;  
    edge[cnt].c=c;  
    edge[cnt].next=head[a];  
    head[a]=cnt++;  
}  
  
int bfs()// 给各点分层，离源点的远近分  
{  
 memset(dis, -1, sizeof(dis));  
 queue q;  
 dis[1] = 0;  
 q.push(1);  
 int i;  
 int cur;  
 while(!q.empty())  
 {  
  cur = q.front();  
  q.pop();  
  for(i = head[cur]; i != -1; i = edge[i].next)  
  {  
   if(dis[edge[i].v] == -1 && edge[i].c > 0)  
   {  
    dis[edge[i].v] = dis[cur] + 1;  
    q.push(edge[i].v);  
   }  
  }  
 }  
 if(dis[m] < 0)  
  return 0;  
 return 1;  
}  
  
int Find(int x,int low){//找增广  
    int a;  
    if(x==m) return low;  
    for(int i=head[x];i!=-1;i=edge[i].next){  
        int v=edge[i].v;  
        if(dis[v]==dis[x]+1 && edge[i].c>0 &&(a=Find(v,min(low,edge[i].c))))  
        {  
            edge[i].c -=a;  
            edge[i^1].c +=a;  
            return a;  
        }  
    }  
    return 0;  
}  
  
void dinic(){  
    int temp;  
    while(bfs()){  
//        printf("%d\n",tmp);  
//        if(tmp==0) break;  
        temp=Find(1,0x3f3f3f3f);  
         ans+=temp;  
    }  
   // printf("%d\n",ans);  
}  
  
int main(){
int t;cin>>t;
for(int i=1;i<=t;i++){   
        scanf("%d%d",&m,&n);
        int a,b,flow;  
        init();  
        for(int i=1;i<=n;i++){  
            scanf("%d%d%d",&a,&b,&flow);  //flow是权值。 
            add(a,b,flow);  
            add(b,a,0);  
        }  
        dinic();
        printf("Case %d: %d\n",i,ans);  
    }
return 0;  
}