poj 1459 多源多汇点最大流

时间：2022-02-04 07:47:27

Sample Input

2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20

7 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7

         (3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5

         (0)5 (1)2 (3)2 (4)1 (5)4

7个点包括电站和用户，2个电站，3个用户，13条边，输入13条边，输入2个电站，输入3个用户

poj 1459 多源多汇点最大流



Sample Output


15

6

增加一个源点一个汇点即可




 /*

 POJ 1459

 */

 #include<stdio.h>

 #include<string.h>

 #include<queue>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 //****************************************************

 //最大流模板

 //初始化：g[][],start,end

 //******************************************************

 const int MAXN=;

 const int INF=0x3fffffff;

 int g[MAXN][MAXN];//存边的容量，没有边的初始化为0

 int path[MAXN],flow[MAXN],start,end;

 int n;//点的个数，编号0-n.n包括了源点和汇点。

 queue<int>q;

 int bfs()

 {

     int i,t;

     while(!q.empty())q.pop();//把清空队列

     memset(path,-,sizeof(path));//每次搜索前都把路径初始化成-1

     path[start]=;

     flow[start]=INF;//源点可以有无穷的流流进

     q.push(start);

     while(!q.empty())

     {

         t=q.front();

         q.pop();

         if(t==end)break;

         //枚举所有的点，如果点的编号起始点有变化可以改这里

         for(i=;i<=n;i++)

         {

             if(i!=start&&path[i]==-&&g[t][i])

             {

                 flow[i]=flow[t]<g[t][i]?flow[t]:g[t][i];

                 q.push(i);

                 path[i]=t;

             }

         }

     }

     if(path[end]==-)return -;//即找不到汇点上去了。找不到增广路径了

     return flow[end];

 }

 int Edmonds_Karp()

 {

     int max_flow=;

     int step,now,pre;

     while((step=bfs())!=-)

     {

         max_flow+=step;

         now=end;

         while(now!=start)

         {

             pre=path[now];

             g[pre][now]-=step;

             g[now][pre]+=step;

             now=pre;

         }

     }

     return max_flow;

 }

 int main()//多源多汇点，在前面加个源点，后面加个汇点，转成单源单汇点

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int np,nc,m;

     int u,v,z;

     while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)

     {

         memset(g,,sizeof(g));

         while(m--)

         {

             while(getchar()!='(');

             scanf("%d,%d)%d",&u,&v,&z);

             u++;v++;

             g[u][v]=z;

         }

         while(np--)

         {

             while(getchar()!='(');

             scanf("%d)%d",&u,&z);

             u++;

             g[][u]=z;

         }

         while(nc--)

         {

             while(getchar()!='(');

             scanf("%d)%d",&u,&z);

             u++;

             g[u][n+]=z;

         }

         n++;

         start=;

         end=n;

         printf("%d\n",Edmonds_Karp());

     }

     return ;

 }


相关文章