给出N个点，M条有向边
如果有向边的标号是1的话，就表示该边的上界下界都为容量
如果有向边的标号为0的哈，表示该边的下界为0，上界为容量
现在问，从1到N的最小流是多少，并输出每条边的流量

像无源汇点上下界可行流那样建图，然后从SS->ST跑一次，然后t->s连一条容量为+∞的边，跑一次，t->s这条边的流量即为最小流。

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<queue>
  5. #define INF 0x7f7f7f7f
  6. #define MAXN 100
  7. using namespace std;
  8. int n,m,d[MAXN+10],S,T,num,dist[MAXN+10],vd[MAXN+10],tot,l[MAXN*MAXN+10],flow;
  9. void Read(int &x){
  10.     char c;
  11.     while(c=getchar(),c!=EOF)
  12.         if(c>=\'0\'&&c<=\'9\'){
  13.             x=c-\'0\';
  14.             while(c=getchar(),c>=\'0\'&&c<=\'9\')
  15.                 x=x*10+c-\'0\';
  16.             ungetc(c,stdin);
  17.             return;
  18.         }
  19. }
  20. struct node{
  21.     int v,cap;
  22.     node *next,*back;
  23. }*adj[MAXN+10],edge[MAXN*MAXN+10],*ecnt=edge,*epos[MAXN*MAXN+10];
  24. void addedge(int u,int v,int cap,int pos){
  25.     node *p=++ecnt;
  26.     p->v=v;
  27.     p->cap=cap;
  28.     p->next=adj[u];
  29.     epos[pos]=p;
  30.     adj[u]=p;
  31.     p=p->back=++ecnt;
  32.     p->v=u;
  33.     p->cap=0;
  34.     p->next=adj[v];
  35.     adj[v]=p;
  36.     p->back=ecnt-1;
  37. }
  38. void read(){
  39.     Read(n),Read(m);
  40.     int i,u,v,z,c;
  41.     for(i=1;i<=m;i++){
  42.         Read(u),Read(v),Read(z),Read(c);
  43.         if(c==1)
  44.             d[u]-=z,d[v]+=z,epos[i]=0,l[i]=z;
  45.         else
  46.             addedge(u,v,z,i);
  47.     }
  48.     S=n+1,T=n+2;
  49.     for(i=1;i<=n;i++)
  50.         if(d[i]>0)
  51.             addedge(S,i,d[i],0),tot+=d[i];
  52.         else if(d[i]<0)
  53.             addedge(i,T,-d[i],0);
  54. }
  55. int dfs(int u,int augu){
  56.     if(u==T)
  57.         return augu;
  58.     int v,augv=0,delta,mind=num-1;
  59.     for(node *p=adj[u];p;p=p->next)
  60.         if(p->cap){
  61.             v=p->v;
  62.             if(dist[u]==dist[v]+1){
  63.                 delta=min(augu-augv,p->cap);
  64.                 delta=dfs(v,delta);
  65.                 augv+=delta;
  66.                 p->cap-=delta;
  67.                 p->back->cap+=delta;
  68.                 if(augu==augv||dist[S]>=num)
  69.                     return augv;
  70.             }
  71.             mind=min(mind,dist[v]);
  72.         }
  73.     if(!augv){
  74.         if(!--vd[dist[u]])
  75.             dist[S]=num;
  76.         dist[u]=mind+1;
  77.         vd[dist[u]]++;
  78.     }
  79.     return augv;
  80. }
  81. void mcmf(){
  82.     memset(dist,0,sizeof dist);
  83.     memset(vd,0,sizeof vd);
  84.     num=n+2;
  85.     vd[0]=num;
  86.     while(dist[S]<num)
  87.         flow+=dfs(S,INF);
  88. }
  89. void print(){
  90.     if(flow!=tot){
  91.         puts("Impossible");
  92.         return;
  93.     }
  94.     printf("%d\n",epos[m+1]->back->cap);
  95.     for(int i=1;i<m;i++)
  96.         if(epos[i])
  97.             printf("%d ",epos[i]->back->cap);
  98.         else
  99.             printf("%d ",l[i]);
  100.     if(epos[m])
  101.         printf("%d\n",epos[m]->back->cap);
  102.     else
  103.         printf("%d\n",l[m]);
  104. }
  105. int main()
  106. {
  107.     read();
  108.     mcmf();
  109.     addedge(n,1,INF,m+1);
  110.     mcmf();
  111.     print();
  112. }

版权声明：本文为outerform原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/outerform/p/5921894.html