2018-team4-modules-无原汇上下界可行流

从 Trac 迁移的文章

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

原文章内容如下：

{{{
int head[N],d[N],lim[M],sp[M],p[N],n,m,S,T,cnt=1;
struct Edge{ int a,b,v,next; }e[M];

void init() {
    cnt = 1;
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    memset(sp,0,sizeof(p));
    memset(d,0,sizeof(d));
    memset(lim,0,sizeof(lim));
}

void add(int a,int b,int v,int id) {
    e[++cnt].a = a;
    e[cnt].b = b;
    e[cnt].v = v;
    e[cnt].next = head[a];
    head[a] = cnt;
    sp[id] = cnt;
}

inline void add_Node(int a,int b,int v,int id) { add(a,b,v,id); add(b,a,0,0); }

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

bool BFS() {
    bool flag = false;
    memset(p,0,sizeof(p)); p[S] = 1;
    queue<int> q; q.push(S); 
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == T) flag = true;
        for (int i=head[u];i;i=e[i].next) 
            if (e[i].v>0 && !p[B]) {
                p[B] = p[u]+1;
                q.push(B);
            }
    }
    return flag;
}

int DFS(int u,int flow) {
    if (u == T) return flow;
    int f = flow , g = 0 , tmp = 0;
    for (int i=head[u];i;i=e[i].next) {
        if (cp>0 && p[B]==p[u]+1 && ( tmp=DFS(B,min(cp,f)) ) > 0) {
            e[i  ].v -= tmp; 
            e[i^1].v += tmp;
            f -= tmp; g += tmp;
        }
    }
    return g;
}

int main() {
    scanf("%d%d",&n,&m);
    init(); S = n+1; T = n+2;
    for (int i=1;i<=m;i++) {
        int a,b,l,r;
        scanf("%d%d%d%d",&a,&b,&l,&r);
        add_Node(a,b,r-l,i);
        d[a] -= l; d[b] += l; lim[i] = l;
    }
    for (int i=1;i<=n;i++) {
        if (d[i] > 0) add_Node(S,i,d[i],0);
        if (d[i] < 0) add_Node(i,T,-d[i],0);
    }

    int flow = 0; bool flag = true;
    while (BFS()) flow += DFS(S,INF);
    for (int i=head[S];i;i=e[i].next)
        if (e[i].v) flag = false;
    if (flag) {
        puts("YES");
        for (int i=1;i<=m;i++) 
            printf("%d\n",lim[i]+e[sp[i]^1].v);
    } else puts("NO");
    printf("\n");
    return 0;
} 
}}}

int head[N],d[N],lim[M],sp[M],p[N],n,m,S,T,cnt=1;
struct Edge{ int a,b,v,next; }e[M];
void init() {
    cnt = 1;
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    memset(sp,0,sizeof(p));
    memset(d,0,sizeof(d));
    memset(lim,0,sizeof(lim));
}
void add(int a,int b,int v,int id) {
    e[++cnt].a = a;
    e[cnt].b = b;
    e[cnt].v = v;
    e[cnt].next = head[a];
    head[a] = cnt;
    sp[id] = cnt;
}
inline void add_Node(int a,int b,int v,int id) { add(a,b,v,id); add(b,a,0,0); }
#define cp e[i].v
#define B e[i].b
bool BFS() {
    bool flag = false;
    memset(p,0,sizeof(p)); p[S] = 1;
    queue<int> q; q.push(S); 
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == T) flag = true;
        for (int i=head[u];i;i=e[i].next) 
            if (e[i].v>0 && !p[B]) {
                p[B] = p[u]+1;
                q.push(B);
            }
    }
    return flag;
}
int DFS(int u,int flow) {
    if (u == T) return flow;
    int f = flow , g = 0 , tmp = 0;
    for (int i=head[u];i;i=e[i].next) {
        if (cp>0 && p[B]==p[u]+1 && ( tmp=DFS(B,min(cp,f)) ) > 0) {
            e[i  ].v -= tmp; 
            e[i^1].v += tmp;
            f -= tmp; g += tmp;
        }
    }
    return g;
}
int main() {
    scanf("%d%d",&n,&m);
    init(); S = n+1; T = n+2;
    for (int i=1;i<=m;i++) {
        int a,b,l,r;
        scanf("%d%d%d%d",&a,&b,&l,&r);
        add_Node(a,b,r-l,i);
        d[a] -= l; d[b] += l; lim[i] = l;
    }
    for (int i=1;i<=n;i++) {
        if (d[i] > 0) add_Node(S,i,d[i],0);
        if (d[i] < 0) add_Node(i,T,-d[i],0);
    }
    int flow = 0; bool flag = true;
    while (BFS()) flow += DFS(S,INF);
    for (int i=head[S];i;i=e[i].next)
        if (e[i].v) flag = false;
    if (flag) {
        puts("YES");
        for (int i=1;i<=m;i++) 
            printf("%d\n",lim[i]+e[sp[i]^1].v);
    } else puts("NO");
    printf("\n");
    return 0;
}