hdu（1532）Drainage Ditches

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

完全一样的方法；

#include"string.h"
#include"stdio.h"
#include"queue"
#define inf 9999999
using namespace std;
int r[300][300];
int pre[300];
int visit[300];
int n,m;
int bfs(int s,int t)
{
 int p,i;
 queue<int>q;
 memset(visit,0,sizeof(visit));
 memset(pre,0,sizeof(pre));
 pre[s]=s;
 visit[s]=1;
 q.push(s);
 while(!q.empty())
 {
  p=q.front();
  q.pop();
  for(i=1;i<=m;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 i;
 while(scanf("%d%d",&n,&m)!=EOF)
 {
  int a,b,c;
  memset(r,0,sizeof(r));
  for(i=0;i<n;i++)
  {
   scanf("%d%d%d",&a,&b,&c);
   r[a][b]+=c;
  }
  printf("%d\n",EK(1,m));
 }
 return 0;
}

这篇关于hdu（1532）Drainage Ditches的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---