bzoj 2502 清理雪道

内容

Description

滑雪场坐落在FJ省西北部的若干座山上。
从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。
你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。
由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。

Input

输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。接下来的n行，描述1~n号地点出发的斜坡，第i行的第一个数为mi (0 <= mi < n) ，后面共有mi个整数，由空格隔开，每个整数aij互不相同，代表从地点i下降到地点aij的斜坡。每个地点至少有一个斜坡与之相连。

Output

输出文件的第一行是一个整数k – 直升飞机的最少飞行次数。

Sample Input

1 3

1 7

2 4 5

1 8

2 6 5

Sample Output

题解

就是建成有上下界一组无限流量源汇点的最小流问题

没啥好说的

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#define N 100010
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, S, T, s, t, l, r, x, d[N];
struct flows {
    struct node {
        int to, next, flow;
    } e[N];
    int tot, st[N], dis[N], cur[N];
    void init() {
        tot = -1, memset(e, -1, sizeof e),
        memset(st, -1, sizeof st);
        memset(d, 0, sizeof d);
    }
    void add(int x, int y, int z) {
        e[++tot].to = y;
        e[tot].flow = z;
        e[tot].next = st[x];
        st[x] = tot;
    }
    void add_edge(int x, int y, int z) {
//      printf("add %d %d %d\n", x, y, z);
        add(x, y, z), add(y, x, 0);
    }
    queue <int> que;
    int bfs(int S, int T) {
        memcpy(cur, st, sizeof st);
        memset(dis, 0, sizeof dis);
        while (!que.empty()) que.pop();
        que.push(S);
        dis[S] = 1;
        while(!que.empty()) {
            int now = que.front();
            que.pop();
            for (int i = st[now]; ~i; i = e[i].next)
                if (e[i].flow && !dis[e[i].to]) {
                    dis[e[i].to] = dis[now] + 1;
                    if (e[i].to == T) return 1;
                    que.push(e[i].to);
                }
        }
        return 0;
    }
    int finds(int now, int T, int flow) {
        if (now == T)
            return flow;
        int f;
        for (int i = cur[now]; ~i; i = e[i].next) {
            cur[now] = i;
            if (e[i].flow && dis[e[i].to] == dis[now] + 1 &&
                (f = finds(e[i].to, T, min(flow, e[i].flow)))) {
                e[i].flow -= f;
                e[i^1].flow += f;
                return f;
            }
        }
        return 0;
    }
    int dinic(int S, int T) {
        int flow = 0, x;
        while(bfs(S, T)) {
            while(x = finds(S, T, inf)) {
                flow += x;
            }
        }
        return flow;
    }
    void del(int x) {
        for (int i = st[x]; ~i; i = e[i].next)
            e[i].flow = e[i ^ 1].flow = 0;
    }
}flow;
main() {
    int in = 0, out = 0;
    scanf("%d", &n);
    flow.init();
    s = n + 1, t = s + 1, S = t + 1, T = S + 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &m);
        for (int j = 1; j <= m; ++j)
            scanf("%d", &x), d[i]--, d[x]++,
            flow.add_edge(i, x, inf);
    }
    for (int i = 1; i <= n; ++i)
        flow.add_edge(s, i, inf),
        flow.add_edge(i, t, inf);
    for (int i = 1; i <= n; ++i)
        if (d[i] > 0)
            flow.add_edge(S, i, d[i]), in += d[i];
        else if (d[i] < 0)
            flow.add_edge(i, T, -d[i]), out -= d[i];
    flow.add_edge(t, s, inf);
    flow.dinic(S, T);
    int ans = flow.e[flow.tot].flow;
    flow.e[flow.tot - 1].flow = flow.e[flow.tot].flow = 0;
    flow.del(S), flow.del(T);
    ans -= flow.dinic(t, s);
    printf("%d\n", ans);
}