【 POJ - 3801】Crazy Circuits(有源汇、上下界最小流)

 

【分析】

　　就是一个有源汇、有上下界的最小流。汇点源点连一条INF的边变成循环流，新增超级源点、超级汇点，拆边，跑最大流判满流。这题不用拆边再反过来跑一遍求最小流，因为所有边的上届都是INF。

 

代码如下：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define Maxn 1010

 #define Maxm 100100

 #define INF 0xfffffff

 char s[];

 int stt,edd;

 int first[Maxn],dis[Maxn];

 int sum;

 struct node

 {

     int x,y,f,o,next;

 }t[Maxm];int len;

 int mymin(int x,int y) {return x<y?x:y;}

 void ins(int x,int y,int f)

 {

     if(x==stt) sum+=f;

     t[++len].x=x;t[len].y=y;t[len].f=f;

     t[len].next=first[x];first[x]=len;t[len].o=len+;

     t[++len].x=y;t[len].y=x;t[len].f=;

     t[len].next=first[y];first[y]=len;t[len].o=len-;

 }

 void make_edge(int x,int y,int k1,int k2)

 {

     ins(stt,y,k1);

     ins(x,edd,k1);

     ins(x,y,k2-k1);

 }

 queue<int > q;

 bool bfs(int st,int ed)

 {

     while(!q.empty()) q.pop();

     memset(dis,-,sizeof(dis));

     q.push(st);dis[st]=;

     while(!q.empty())

     {

         int x=q.front();

         for(int i=first[x];i;i=t[i].next) if(t[i].f>)

         {

             int y=t[i].y;

             if(dis[y]==-)

             {

                 dis[y]=dis[x]+;

                 q.push(y);

             }

         }

         q.pop();

     }

     if(dis[ed]!=-) return ;

     return ;

 }

 int ffind(int x,int ed,int flow)

 {

     if(x==ed) return flow;

     int now=;

     for(int i=first[x];i;i=t[i].next) if(t[i].f>)

     {

         int y=t[i].y;

         if(dis[y]==dis[x]+)

         {

             int a=ffind(y,ed,mymin(flow-now,t[i].f));

             t[i].f-=a;

             t[t[i].o].f+=a;

             now+=a;

             if(now==flow) break;

         }

     }

     if(now==) dis[x]=-;

     return now;

 }

 int max_flow(int st,int ed)

 {

     int ans=;

     while(bfs(st,ed))

     {

         ans+=ffind(st,ed,INF);

     }

     if(ans!=sum) return -;

     return ans;

 }

 int main()

 {

     int n,m;

     while()

     {

         scanf("%d%d",&n,&m);

         if(n==&&m==) break;

         int st=n+,ed=st+;len=;

         stt=ed+;edd=stt+;sum=;

         memset(first,,sizeof(first));

         for(int i=;i<=m;i++)

         {

             int x,y;

             scanf("%s",s);

             if(s[]=='+') x=st;

             else if(s[]=='-') x=ed;

             else

             {

                 int now=;x=;

                 while(s[now]>=''&&s[now]<='') x=x*+s[now++]-'';

             }scanf("%s",s);

             if(s[]=='+') y=st;

             else if(s[]=='-') y=ed;

             else

             {

                 int now=;y=;

                 while(s[now]>=''&&s[now]<='') y=y*+s[now++]-'';

             }

             int c;

             scanf("%d",&c);

             make_edge(x,y,c,INF);

         }

         int id=len+;

         ins(ed,st,INF);

         int now=max_flow(stt,edd);

         if(now==-) printf("impossible\n");

         else

         {

             printf("%d\n",t[id].f);

         }

     }

     return ;

 }

[POJ3801]

2016-06-13 13:12:16