Codeforces 270E Flawed Flow 网络流问题

题意：给出一些边，给出边的容量。让你为所有边确定一个方向使得流量最大。

题目不用求最大流，而是求每条边的流向，这题是考察网络流的基本规律。

若某图有最大，则有与源点相连的边必然都是流出的，与汇点相连的边必然是流入的，其它所有点流入和流出的流量是相等的。

我们可以根据这一规律来求解。

先求出所有点（除了源点和汇点）的总流量（表示流入的流量的2倍），每次流过该边，更新的时候减去流入流量的2倍。

从源点出发广搜每个点，搜的过程可以确定经过边的流向，当某个点的剩余总流量为0时，表示流入该点的流量边已经都处理完毕，将这点入栈。

特别注意：当这个点是汇点时不要入栈，不然会从汇点回流过来，不符合基本规律。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = ;

const int MAXM = MAXN * ;

struct Edge {

    int u,v,w;

    int next;

    int type,id;

}edge[MAXM];

int head[MAXN],tot;

void init() {tot = ; memset(head,-,sizeof(head));}

void add_edge(int u,int v,int w,int type,int id) {

    edge[tot].u = u;

    edge[tot].v = v;

    edge[tot].w = w;

    edge[tot].type = type;

    edge[tot].id = id;

    edge[tot].next = head[u];

    head[u] = tot++;

}

queue<int>q;

int N,M;

bool vis[MAXN];

int ans[MAXN],val[MAXN];

int main() {

    while (scanf("%d%d",&N,&M) != EOF) {

        init();

        memset(val,,sizeof(val));

        for (int i =  ; i < M ; i++) {

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            add_edge(u,v,w,,i + );

            add_edge(v,u,w,,i + );

            val[u] += w;

            val[v] += w;

        }

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

        vis[] = true; q.push();

        while (!q.empty()) {

            int u = q.front(); q.pop();

            for (int i = head[u] ; i != -  ; i = edge[i].next) {

                int v = edge[i].v;

                if (vis[v]) continue;

                val[v] -=  * edge[i].w;

                ans[edge[i].id] = edge[i].type;

                if (val[v] ==  && v != N) {

                    vis[v] = true;

                    q.push(v);

                }

            }

        }

        for (int i =  ; i <= M ; i++) printf("%d\n",ans[i]);

    }

    return ;

}

巴特西

Codeforces 270E Flawed Flow 网络流问题

最新文章

热门文章