poj 1459 Power Network （最大流模版）

直接套用最大流的模板的，主要是建图的过程。

输入分别为m个点，a个发电站，b个用户，n条边；接下去是n条边的信息(u,v)cost，cost表示边(u,v)的最大流量；a个发电站的信息(u)cost，cost表示发电站u能提供的最大流量；b个用户的信息(v)cost，cost表示每个用户v能接受的最大流量。
典型的最大网络流中多源多汇的问题，在图中添加1个源点S和汇点T，将S和每个发电站相连，边的权值是发电站能提供的最大流量；将每个用户和T相连，边的权值是每个用户能接受的最大流量。从而转化成了一般的最大网络流问题，然后求解。




map[i][j]记录的就是i->j可以增加的流量
  2 第一次bfs 时可能看不出来但，第二次你就可以看出来了
  3 
  4 #include<stdio.h>
  5 #include<queue>
  6 #include<string.h>
  7 #define maxn 1000
  8 #define inf 0x7fffffff
  9 using namespace std;
 10 queue<int>q;
 11 int map[maxn][maxn],path[maxn],flow[maxn];
 12 int n,np,nc,m,s,e;
 13 int bfs()
 14 {
 15     while(!q.empty())q.pop();
 16     memset(path,-1,sizeof(path));
 17     memset(flow,0,sizeof(flow));//其实这里清空和不清空没区别 ，应为每一次都是由前面的flow得到后面的flow
 18     path[s]=1;
 19     flow[s]=inf;
 20     q.push(s);
 21     while(!q.empty())
 22     {
 23         int k=q.front();
 24          q.pop();
 25          if(k==e)break;
 26          for(int i=0;i<=n;i++)
 27          {
 28              if(i!=s&&path[i]==-1&&map[k][i])
 29              {
 30                  flow[i]=flow[k]<map[k][i]?flow[k]:map[k][i];
 31                  path[i]=k;
 32                  q.push(i);
 33 
 34 
 35              }
 36          }
 37     }
 38     if(path[e]==-1)return -1;
 39     else return flow[n];
 40 
 41 }
 42 int EK()
 43 {
 44     int max_flow=0,step,now,pre;
 45     while((step=bfs())!=-1)
 46     {
 47         max_flow+=step;
 48         now=e;
 49         while(now!=s)
 50         {
 51             pre=path[now];
 52             map[now][pre]+=step;
 53             map[pre][now]-=step;//这里可以将 刚找到 的 增光路经 删掉
 54             now=pre;
 55         }
 56 
 57     }
 58     return max_flow;
 59 }
 60 int main()
 61 {
 62     int u,v,z;
 63    while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
 64    {
 65        memset(map,0,sizeof(map));
 66        while(m--)
 67        {
 68            while(getchar()!='(');
 69 
 70             scanf("%d,%d)%d",&u,&v,&z);
 71             u++;v++;
 72             map[u][v]=z;
 73 
 74     }
 75        while(np--)
 76        {
 77            while(getchar()!='(');
 78 
 79                      scanf("%d)%d",&u,&z);
 80                       u++;
 81                       map[0][u]=z;
 82         }
 83        while(nc--)
 84        {
 85            while(getchar()!='(');
 86 
 87                      scanf("%d)%d",&u,&z);
 88                      u++;
 89                      map[u][n+1]=z;
 90 
 91 
 92 
 93        }
 94        n++;
 95        s=0;
 96        e=n;
 97 
 98        int ans=EK();
 99        printf("%d\n",ans);
100    }
101 }

poj 1459 Power Network （最大流 模版）

poj 1459 Power Network （最大流模版）