2018-team4-modules-有原汇上下界费用流

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
int n,m,S,T,ss,tt,cnt=1,tot=0;
int head[N],d[N],p[N];
int map[P][P],sc[P],sr[P],r[P],c[P],dis[N];
int ans,tl;
struct Edge{ int a,b,v,cost,next; }e[10*N];
void add(int a,int b,int v,int cost) {
    e[++cnt].a = a;
    e[cnt].b = b;
    e[cnt].v = v;
    e[cnt].cost = cost;
    e[cnt].next = head[a];
    head[a] = cnt;
}

inline void add_Node(int a,int b,int vl,int vr,int cost) {
    //printf("Node %d %d %d %d\n",a,b,vl,vr);
    d[a] -= vl; d[b] += vl;
    add(a,b,vr-vl,cost); add(b,a,0,-cost);
}
void paul() {
    ss = tot+1; tt = tot+2;
    for (int _=1;_<=tot;_++) {
        if (d[_] < 0) add(_,tt,-d[_],0) , add(tt,_,0,0);
        if (d[_] > 0) add(ss,_, d[_],0) , add(_,ss,0,0); 
    }
}

#define cp e[i].v
#define B e[i].b

bool SPFA() {
    bool flag = false;
    memset(p,0,sizeof(p));
    memset(dis,127/3,sizeof(dis));
    dis[ss] = 0;
    queue<int> q; q.push(ss);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == tt) flag = true; 
        for (int i=head[u];i;i=e[i].next)
            if (cp > 0 && dis[u] + e[i].cost < dis[B]) {
                dis[B] = dis[u] + e[i].cost;
                p[B] = i;
                q.push(B);
            } 
    }
    return flag;
}

void mcf() {
    int g = p[tt] , flow = INF;
    while (g) {
        flow = min(flow , e[g].v);
        g = p[ e[g].a ];
    }
    g = p[tt];
    while (g) {
        e[g  ].v -= flow;
        e[g^1].v += flow;
        ans += e[g].cost * flow;
        g = p[ e[g].a ];
    }
    tl += flow;
}

void init() {
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    memset(d,0,sizeof(d));

    memset(sc,0,sizeof(sc));
    memset(sr,0,sizeof(sr));
    memset(c,0,sizeof(c));
    memset(r,0,sizeof(r));
    memset(map,0,sizeof(map));
    cnt = 1; tot = 0;
    S = ++tot; T = ++tot; add_Node(T,S,0,INF,0);
    ans = tl = 0;
}


int main() {    
    init();//请注意cnt赋值为1 
    paul(); //补上所有拆的边 

    while (SPFA()) 
        mcf();

    for (int i=head[ss];i;i=e[i].next) if (e[i].v) ans = -1;//判断是否有解
    if (ans == -1) puts("-1"); else printf("%d\n",ans);
    return 0;
}
}}}

int n,m,S,T,ss,tt,cnt=1,tot=0;
int head[N],d[N],p[N];
int map[P][P],sc[P],sr[P],r[P],c[P],dis[N];
int ans,tl;
struct Edge{ int a,b,v,cost,next; }e[10*N];
void add(int a,int b,int v,int cost) {
    e[++cnt].a = a;
    e[cnt].b = b;
    e[cnt].v = v;
    e[cnt].cost = cost;
    e[cnt].next = head[a];
    head[a] = cnt;
}
inline void add_Node(int a,int b,int vl,int vr,int cost) {
    //printf("Node %d %d %d %d\n",a,b,vl,vr);
    d[a] -= vl; d[b] += vl;
    add(a,b,vr-vl,cost); add(b,a,0,-cost);
}
void paul() {
    ss = tot+1; tt = tot+2;
    for (int _=1;_<=tot;_++) {
        if (d[_] < 0) add(_,tt,-d[_],0) , add(tt,_,0,0);
        if (d[_] > 0) add(ss,_, d[_],0) , add(_,ss,0,0); 
    }
}
#define cp e[i].v
#define B e[i].b
bool SPFA() {
    bool flag = false;
    memset(p,0,sizeof(p));
    memset(dis,127/3,sizeof(dis));
    dis[ss] = 0;
    queue<int> q; q.push(ss);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == tt) flag = true; 
        for (int i=head[u];i;i=e[i].next)
            if (cp > 0 && dis[u] + e[i].cost < dis[B]) {
                dis[B] = dis[u] + e[i].cost;
                p[B] = i;
                q.push(B);
            } 
    }
    return flag;
}
void mcf() {
    int g = p[tt] , flow = INF;
    while (g) {
        flow = min(flow , e[g].v);
        g = p[ e[g].a ];
    }
    g = p[tt];
    while (g) {
        e[g  ].v -= flow;
        e[g^1].v += flow;
        ans += e[g].cost * flow;
        g = p[ e[g].a ];
    }
    tl += flow;
}
void init() {
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    memset(d,0,sizeof(d));
    memset(sc,0,sizeof(sc));
    memset(sr,0,sizeof(sr));
    memset(c,0,sizeof(c));
    memset(r,0,sizeof(r));
    memset(map,0,sizeof(map));
    cnt = 1; tot = 0;
    S = ++tot; T = ++tot; add_Node(T,S,0,INF,0);
    ans = tl = 0;
}
int main() {    
    init();//请注意cnt赋值为1 
    paul(); //补上所有拆的边 
    while (SPFA()) 
        mcf();
    for (int i=head[ss];i;i=e[i].next) if (e[i].v) ans = -1;//判断是否有解
    if (ans == -1) puts("-1"); else printf("%d\n",ans);
    return 0;
}