分类存档：默认分类

【题目大意】
给定源汇，一些弧必须满载。问源到汇的最小流是多少？
【算法分析】
通过加弧当然。。。这是最简单的方法。。。反向增广这么高科技的就算了。。。
【其它】
复习上下界网络流。居然没1Y。原因1是有一个地方N写成E了。（就是数组没开够。。。），原因2是MLE。
我的习惯一直是把数组开大很多的。。。SGU这种限这么死的地方就果断悲剧。
【CODE】
#include #include #include const int N=155;
const int E=N*N*6;
struct edge{int x,y,c,next;};

struct Network_t{
    int e,S,T,Flow;
    edge g[E];
    int ls[N],fa[N],cur[N],num[N],d[N];
    void init(){
        e=1;
        memset(ls,0,sizeof(ls));
    }

    void clr(){
        for (int i=3;i<=e;i+=2){
            g[i-1].c+=g[i].c;
            g[i].c=0;
        }
    }

    void addedge(int x,int y,int c){
        g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=e;
        g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=e;
    }

    void relabel(int k){
        cur[k]=ls[k];
        int mm=T;
        for (int t=ls[k];t;t=g[t].next)
          if (g[t].c && d[g[t].y]            mm=d[g[t].y];
        d[k]=mm+1;
    }

    void change(){
        int nf=0x7FFFFFFF;
        for (int i=T;i!=S;i=g[fa[i]].x)
          if (g[fa[i]].c        for (int i=T;i!=S;i=g[fa[i]].x){
            g[fa[i]].c-=nf;
            g[fa[i]^1].c+=nf;
        }
        Flow+=nf;
    }

    void sap(){
        Flow=0;
        int i;
        for (i=1;i<=T;i++){
            d[i]=num[i]=0;
            cur[i]=ls[i];
        }
        i=S;
        while (d[S]            int &t=cur[i];
            for (;t;t=g[t].next)
              if (g[t].c && d[g[t].y]+1==d[g[t].x]) break;
            if (t){
                fa[g[t].y]=t;
                i=g[t].y;
                if (i==T){
                    change();
                    i=S;
                }
            }
            else{
                if (!–num[d[i]]) break;
                relabel(i);
                ++num[d[i]];
                if (i!=S) i=g[fa[i]].x;
            }
        }
    }
}Network;

int n,m,SF;
int din[N],dout[N],Type[E],C[E];

void init(){
    Network.init();
    scanf("%d%d",&n,&m);
    SF=0;
    for (int x,y,c,t,i=1;i<=m;i++){
      scanf("%d%d%d%d",&x,&y,&c,&t);
      if (t){
          din[y]+=c;
          dout[x]+=c;
          SF+=c;
      }
      else Network.addedge(x,y,c);
      Type[i]=t;
      C[i]=c;
    }
}

void build(){
    Network.S=n+1; Network.T=n+2;
    int i;
    for (i=1;i<=n;i++){
        if (din[i]) Network.addedge(n+1,i,din[i]);
        if (dout[i]) Network.addedge(i,n+2,dout[i]);
    }
    Network.addedge(n,1,0x7FFFFFFF);
}

void output(){
    int cnt=1;
    for (int i=1;i<=m;i++){
      if (Type[i]) printf("%d",C[i]);
      else printf("%d",Network.g[cnt+=2].c);
      if (i==m) puts("");
           else putchar(‘ ’);
    }
}

void solve(){
    Network.sap();
    if (Network.Flow!=SF){
        puts("Impossible");
        return;
    }
    int l,r,mid;
    l=0; r=Network.g[Network.e].c;
    while (l        mid=(l+r)/2;
        Network.clr();
        Network.g[Network.e-1].c=mid;
        Network.sap();
        if (Network.Flow==SF) r=mid;
                         else l=mid+1;
    }
    Network.clr();
    Network.g[Network.e-1].c=l;
    Network.sap();
    printf("%dn",l);
    output();
}

int main(){
    init();
    build();
    solve();
    return 0;
}