[USACO07OPEN]Dining 题解

前言

如果有人不会网络流，那么安利一下我网络最大流Dinic的博客

关于网络流，我多久没有碰这个算法了...

这是一道网络流好题。

题解

这道题目难点主要是构图。

这道题的构图一开始很容易想到建一个超级源点连食物，食物连牛，牛连饮料，饮料连汇点。

最后跑一遍最大流求出答案。

但是实际上这个算法是错误的

比如下面这组数据

1 3 3

3 3 1 2 3 1 2 3

答案应该是1，但当前的算法输出是3，算法的错误是中间的牛被重复利用了。

于是我们想到了一个技巧，拆点。

把一头牛拆成两个点，中间连接一条流量为1的边，这样保证了一头牛最多只会被利用一次。

于是重新构图：

建一个超级源点连房间，食物连牛1，牛1连牛2，牛2连饮料，饮料连汇点。

注:其中牛1和牛2实际上是指同一头牛。

然后接着跑一遍网络流求出答案即可。

代码

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

const long long MAX = (1ll << 62);

int read(){

    int x = 0; int zf = 1; char ch = ' ';

    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

    if (ch == '-') zf = -1, ch = getchar();

    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;

}

struct Edge{

    int to, next;

    long long dis;

} edges[210000];

int cur[10010], head[10010], edge_num = -1;

void addEdge2(int from, int to, long long dis){

    edges[++edge_num].to = to;

    edges[edge_num].dis = dis;

    edges[edge_num].next = head[from];

    head[from] = edge_num;

}

void addEdge(int from, int to, long long dis){

    addEdge2(from, to, dis), addEdge2(to, from, 0);

}

int d[10010];

int s, t;

long long DFS(int u, long long flow){

    if (u == t) return flow;

    long long _flow = 0, __flow;

    for (int& c_e = cur[u]; c_e != -1; c_e = edges[c_e].next){

        int v = edges[c_e].to;

        if (d[v] == d[u] + 1 && edges[c_e].dis > 0){

            __flow = DFS(v, min(flow, edges[c_e].dis));

            flow -= __flow;

            edges[c_e].dis -= __flow;

            _flow += __flow;

            edges[c_e ^ 1].dis += __flow;

            if (!flow)

                break;

        }

    }

    if (!_flow) d[u] = -1;

    return _flow;

}

bool BFS(){

    memset(d, -1, sizeof(d));

    queue<int> que; que.push(s);

    d[s] = 0; int u, _new;

    while (!que.empty()){

        u = que.front(), que.pop();

        for (int c_e = head[u]; c_e != -1; c_e = edges[c_e].next){

            _new = edges[c_e].to;

            if (d[_new] == -1 && edges[c_e].dis > 0){

                d[_new] = d[u] + 1;

                que.push(_new);

            }

        }

    }

    return (d[t] != -1);

}

int n;

void dinic(){

    long long max_flow = 0;

    while (BFS()){

        for (int i = 0; i <= n; ++i) cur[i] = head[i];

        max_flow += DFS(s, MAX);

    }

    printf("%lld", max_flow);

}

int main(){

    memset(head, -1, sizeof(head));

    int N = read(), f = read(), d = read();

    s = 0;

    for (int j = 1; j <= f; ++j)

        addEdge(s, j, 1);

    for (int i = 1; i <= N; ++i){

        int fi = read(), di = read();

        for (int j = 1; j <= fi; ++j){

            int ff = read();

            addEdge(ff, f + d + i, 1);

        }

        addEdge(f + d + i, f + d + N + i, 1);

        for (int j = 1; j <= di; ++j){

            int dd = read();

            addEdge(f + d + N + i, f + dd, 1);

        }

    }

    n = t = f + d + N * 2 + 1;

    for (int j = 1; j <= d; ++j)

        addEdge(f + j, t, 1);

    dinic();

    return 0;

}

巴特西

[USACO07OPEN]Dining 题解

前言

题解

代码

最新文章

热门文章