POJ1459(最大流Isap)

题意:有一个电力网络,有发电厂,有用户,图提供的信息有发电厂和用户的容量,还有边,以及边的容量和流量,求解用户的最大使用量.

先输入四个数 n np nc m,n表示的是总共的顶点数目,np表示发电厂的数目,nc表示用户的数目,m表示边数.

再输入m条边的信息,再输入np个发电厂的信息,再输入nc个用户的信息

(1)对输入的m条边建边

(2)对源点到每个发电站建边

(3)对每个用户到汇点建边

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 using namespace std;
  7 #define inf 0x7fffffff
  8 #define N 300
  9 #define M 30000
 10 int cur[N],pre[N],gap[N],dis[N];
 11 int size,head[N];
 12 struct Edge
 13 {
 14     int v,w,next;
 15     Edge(){}
 16     Edge(int V,int W,int NEXT):v(V),w(W),next(NEXT){}
 17 }edge[M];
 18 void Init()
 19 {
 20     size = 0;
 21     memset(head,-1,sizeof(head));
 22 }
 23 void InsertEdge(int u,int v,int w)
 24 {
 25     edge[size] = Edge(v,w,head[u]);
 26     head[u] = size++;
 27     edge[size] = Edge(u,0,head[v]);
 28     head[v] = size++;
 29 }
 30 int Isap(int st,int ed,int n)
 31 {
 32     for(int i=0; i<=n; i++)
 33     {
 34         cur[i] = head[i];
 35         gap[i] = dis[i] = 0;
 36     }
 37     int u = pre[st] = st;
 38     int aug = inf ,maxflow = 0;
 39     while(dis[st] < n)
 40     {
 41         loop:
 42         for(int &i=cur[u]; i!=-1; i=edge[i].next)
 43         {
 44             int v = edge[i].v;
 45             if(edge[i].w && dis[u]==dis[v]+1)
 46             {
 47                 aug = min(aug,edge[i].w);
 48                 pre[v] = u;
 49                 u = v;
 50                 if(v==ed)
 51                 {
 52                     maxflow += aug;
 53                     for(u=pre[u]; v!=st; v=u,u=pre[u])
 54                     {
 55                         edge[cur[u]].w -= aug;
 56                         edge[cur[u]^1].w += aug;
 57                     }
 58                     aug = inf;
 59                 }
 60                 goto loop;
 61             }
 62         }
 63         int mindis = n;
 64         for(int i=head[u]; i!=-1; i=edge[i].next)
 65         {
 66             int v = edge[i].v;
 67             if(edge[i].w && dis[v] < mindis)
 68             {
 69                 cur[u] = i;
 70                 mindis = dis[v];
 71             }
 72         }
 73         if(--gap[dis[u]]==0) break;
 74         gap[dis[u]=mindis+1]++;
 75         u = pre[u];
 76     }
 77     return maxflow;
 78 }
 79 int main()
 80 {
 81     int n,np,nc,m,st,ed,nv,u,v,w;
 82     char s[15];
 83     while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
 84     {
 85         Init(); nv = n+2; st = n ; ed = n+1;
 86         for(int i=1; i<=m; i++)
 87         {
 88             scanf("%s",s);
 89             sscanf(s,"(%d,%d)%d",&u,&v,&w); //学到了,sscanf分离字符串中的数字 
 90             InsertEdge(u,v,w);
 91         }
 92         for(int i=1; i<=np; i++)
 93         {
 94             scanf("%s",s);
 95             sscanf(s,"(%d)%d",&v,&w);
 96             InsertEdge(st,v,w);
 97         }
 98         
 99         for(int i=1; i<=nc; i++)
100         {
101             scanf("%s",s);
102             sscanf(s,"(%d)%d",&u,&w);
103             InsertEdge(u,ed,w);
104         }
105         printf("%d
",Isap(st,ed,nv));
106     }
107     return 0;
108 }

View Code