POJ-1459 Power Network

题意：有发电站，用户，中转站，求整个网络最大耗电量。

解：求最大流嘛。套了一个Dinic，T了。加上当前弧优化，AC了。

代码：

  1 #include
  2 #include 
  3 #include <string.h>
  4 #include 
  5 #include 
  6 #include 
  7 using namespace std;
  8 #define ll long long
  9 #define maxx 1005
 10 #define maxe 50005
 11 #define inf 0x3f3f3f3f
 12 const int mod=1e9+7;
 13 //#define int long long
 14 struct edge{
 15     int u,v,w;
 16     int nxt;
 17 }e[maxe];
 18 int cnt=0,head[maxx]={0};
 19 int st,en;
 20 void add(int u,int v,int w){
 21     e[cnt].u=u;
 22     e[cnt].v=v;
 23     e[cnt].w=w;
 24     e[cnt].nxt=head[u];
 25     head[u]=cnt++;
 26 }
 27 int n,np,nc,m;
 28 int depth[maxx],now[maxx];
 29 int bfs(){
 30     memset(depth,0x3f,sizeof(depth));
 31     queue<int> q;
 32     q.push(st);depth[st] = 0;now[st] = head[st];
 33     while(!q.empty()){
 34         int x = q.front();q.pop();
 35         for(int i=head[x];i!=-1;i=e[i].nxt){
 36             int y=e[i].v;
 37             if(e[i].w>0&&depth[y]==inf){
 38                 q.push(y);
 39                 now[y]=head[y];
 40                 depth[y]=depth[x]+1;
 41                 if(y==en)
 42                     return 1;
 43             }
 44         }
 45     }
 46     return 0;
 47 }
 48 
 49 int dfs(int x,int flow){
 50     if(x==en)
 51         return flow;
 52     int ans = 0,k,i;
 53     for(i=now[x];i!=-1&&flow;i=e[i].nxt){
 54         now[x]=i;
 55         int y=e[i].v;
 56         if(e[i].w>0&&(depth[y]==depth[x]+1)){
 57             k=dfs(y,min(flow,e[i].w));
 58             if(!k)    depth[y]=inf;
 59             e[i].w-=k;
 60             e[i^1].w+=k;
 61             ans+=k;
 62             flow-=k;
 63         }
 64     }
 65     return ans;
 66 }
 67 
 68 int dinic(){
 69     int ans=0;
 70     while(bfs())
 71         ans+=dfs(st,inf);
 72     return ans;
 73 }
 74 signed main() {
 75     while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){
 76         cnt=0;
 77         memset(e,0,sizeof e);
 78         memset(head,-1,sizeof head);
 79         st=n+1,en=n+2;
 80         for(int i=0;i){
 81             int u,v,w;
 82             while(getchar()!='(');
 83             scanf("%d,%d)%d",&u,&v,&w);
 84             add(u,v,w);
 85             add(v,u,0);
 86         }
 87         for(int i=0;i){
 88             int v,w;
 89             while(getchar()!='(');
 90             scanf("%d)%d",&v,&w);
 91             add(st,v,w);
 92             add(v,st,0);
 93         }
 94         for(int i=0;i){
 95             int u,w;
 96             while(getchar()!='(');
 97             scanf("%d)%d",&u,&w);
 98             add(u,en,w);
 99             add(en,u,0);
100         }
101         printf("%d\n",dinic());
102     }
103     return 0;
104 }