poj 1459Power Network解题报告

网络流的压入重标记算法模板，完全按照算法导论的模式打出来的，没有什么优化之类的，只是为了给自己打模板，要省赛了，加油啊。
View Code
  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #define N 105
  5 #define min(x,y) x<y?x:y
  6 #define inf 0x7fffffff
  7 using namespace std;
  8 int f[N][N],c[N][N];
  9 int h[N],e[N];
 10 int n,m,s,t;
 11 int nc,np;
 12 void init()
 13 {
 14     int i;
 15     memset(h,0,sizeof(h));
 16     memset(e,0,sizeof(e));
 17     memset(f,0,sizeof(f));
 18     h[s]=n;
 19     for(i=0;i<n;i++)
 20     {
 21         if(c[s][i])
 22         {
 23             f[s][i]=c[s][i];
 24             f[i][s]=-c[s][i];
 25             e[i]=c[s][i];
 26             e[s]-=c[s][i];
 27         }
 28     }
 29 }
 30 void push(int u,int v)
 31 {
 32     int d=min(e[u],c[u][v]-f[u][v]);
 33     f[u][v]+=d;
 34     f[v][u]=-f[u][v];
 35     e[u]-=d;
 36     e[v]+=d;
 37 }
 38 bool relabel(int u)
 39 {
 40     int mh=inf,i;
 41     for(i=0;i<n;i++)
 42     {
 43         if(c[u][i]>f[u][i])
 44         mh=min(mh,h[i]);
 45     }
 46     if(mh==inf)
 47     return false;
 48     h[u]=mh+1;
 49     for(i=0;i<n;i++)
 50     {
 51         if(e[u]==0)
 52         break;
 53         if(h[i]==mh&&c[u][i]>f[u][i])
 54         push(u,i);
 55     }
 56     return true;
 57 }
 58 int push_relabel()
 59 {
 60     init();
 61     int i;
 62     bool flag=true;
 63     while(flag)
 64     {
 65         flag=false;

 66         for(i=0;i<n-2;i++)
 67         if(e[i]>0)
 68         flag=flag||relabel(i);
 69     }
 70     return e[t];
 71 }
 72 int main()
 73 {
 74     int i,x,y,z;
 75     char tmp[10];
 76     while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
 77     {
 78         s=n;
 79         t=n+1;
 80         n+=2;
 81         memset(c,0,sizeof(c));
 82         for(i=0;i<m;i++)
 83         {
 84             scanf("%s",tmp);
 85             sscanf(tmp,"(%d,%d)%d",&x,&y,&z);
 86             c[x][y]=z;
 87         }
 88         for(i=0;i<np;i++)
 89         {
 90             scanf("%s",tmp);
 91             sscanf(tmp,"(%d)%d",&x,&z);
 92             c[s][x]=z;
 93         }
 94         for(i=0;i<nc;i++)
 95         {
 96             scanf("%s",tmp);
 97             sscanf(tmp,"(%d)%d",&x,&z);
 98             c[x][t]=z;
 99         }
100         printf("%d\n",push_relabel());
101     }
102     return 0;
103 }