hdu(3549)Flow Problem

本文主要是介绍hdu(3549)Flow Problem，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include"stdio.h"
#include"string.h"
#include"queue"
int r[100][100];
int pre[1000];
int visit[1000];
#define inf 999999999
using namespace std;
int n,m;
int bfs(int s,int t)//查找增广路。
{
 int p,i;
 memset(pre,0,sizeof(pre));
 memset(visit,0,sizeof(visit));
 queue<int>q;
 pre[s]=s;
 visit[s]=1;
 q.push(s);
 while(!q.empty())
 {
  p=q.front();//注意细节（）不可掉。。
  q.pop();
  for(i=1;i<=n;i++)
  {
   if(visit[i]==0&&r[p][i])
   {
    pre[i]=p;
    visit[i]=1;
    if(i==t)
     return 1;
    q.push(i);
   }
  }
 }
 return 0;
}
int EK(int s,int t)//计算最大流量。。
{
 int d,i,flow=0;
 while(bfs(s,t))
 {
  d=inf;
  for(i=t;i!=s;i=pre[i])
   d=d<r[pre[i]][i]?d:r[pre[i]][i];
  for(i=t;i!=s;i=pre[i])
  {
   r[pre[i]][i]-=d;
   r[i][pre[i]]+=d;
  }
  flow+=d;
 }
 return flow;
}
int main()
{
 int t,i,j=1;
 scanf("%d",&t);
 while(t--)
 {
  scanf("%d%d",&n,&m);
  memset(r,0,sizeof(r));
  for(i=0;i<m;i++)
  {
   int a,b,c;
   scanf("%d%d%d",&a,&b,&c);
   r[a][b]+=c;
  }
  printf("Case %d: %d\n",j++,EK(1,n));
 }
 return 0;
}

这篇关于hdu(3549)Flow Problem的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---