bzoj2502: 清理雪道 | jeffswt: the ac moments

Description

滑雪场坐落在 FJ 省西北部的若干座山上.

从空中鸟瞰, 滑雪场可以看作一个有向无环图, 每条弧代表一个斜坡 (即雪道), 弧的方向代表斜坡下降的方向.

你的团队负责每周定时清理雪道. 你们拥有一架直升飞机, 每次飞行可以从总部带一个人降落到滑雪场的某个地点, 然后再飞回总部. 从降落的地点出发, 这个人可以顺着斜坡向下滑行, 并清理他所经过的雪道.

由于每次飞行的耗费是固定的, 为了最小化耗费, 你想知道如何用最少的飞行次数才能完成清理雪道的任务.

Input

输入文件的第一行包含一个整数 \(n (2 \leq n \leq 100)\)----代表滑雪场的地点的数量.

接下来的 \(n\) 行, 描述 \(1 \sim n\) 号地点出发的斜坡, 第 \(i\) 行的第一个数为 \(m_i (0 \leq m_i \lt n)\), 后面共有 \(m_i\) 个整数, 由空格隔开, 每个整数 \(a_{i,j}\) 互不相同, 代表从地点 \(i\) 下降到地点 \(a_{i,j}\) 的斜坡. 每个地点至少有一个斜坡与之相连.

Output

输出文件的第一行是一个整数 \(k\)----直升飞机的最少飞行次数.

Sample Input

Sample Output

Explanation

每条雪道拆成俩个结点

就是通过上下界限制每条雪道至少通过 1 次

可能我的做法不是很正常, 因为 @Burst_Zero 大神告诉我其实这道题用最小流两个方向各跑一遍就可以出来了~

话说我为什么调了两天呢...... 因为我每一次跑最大流的时候都会把总流量设成 0, 然后从头跑一遍一点意思都没有, 所以就不停地死循环加边~ 突然脑洞一开发现了这个 bug

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
typedef int lli;
const int maxn = 30010, maxm = 500100;
// const lli infinit = 0x007f7f7f7f7f7f7fll;
const int infinit = 0x7fffffff;

class Dinic
{
public:
    struct edge
    {
        int u, v;
        lli flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm], *edges_bak[maxn];
    int level[maxn];
    void add_edge(int u, int v, lli flow)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        memset(level, 0, sizeof(level));
        queue<int> que;
        que.push(s);
        level[s] = 1;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && !level[ep->v]) {
                    level[ep->v] = level[p] + 1;
                    que.push(ep->v);
                }
        }
        if (level[t] > 0)
            return true;
        return false;
    }
    lli find(int p, lli mn)
    {
        if (p == t)
            return mn;
        lli sum = 0;
        for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                lli tmp = find(ep->v, min(mn - sum, ep->flow));
                if (tmp > 0) {
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                    sum += tmp;
                }
            }
        if (sum <= 0)
            level[p] = 0;
        return sum;
    }
    lli max_flow;
    lli eval(void)
    {
        // Backing up
        for (int i = 0; i <= n; i++)
            edges_bak[i] = edges[i];
        // Evaluating
        while (make_level()) {
            // Restoring stuff
            for (int i = 0; i <= n; i++)
                edges[i] = edges_bak[i];
            // Deep first searching, literally.
            lli tmp = find(s, infinit);
            if (tmp <= 0)
                break;
            max_flow += tmp;
        }
        return max_flow;
    }
} graph;

int n, m;
int degree[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x); // How many linkages
        for (int j = 1, y; j <= x; j++) {
            scanf("%d", &y); // Target
            m += 1;
            graph.add_edge(i, n + 2*m - 1, infinit);
            graph.add_edge(n + 2*m, y, infinit);
        }
    }
    graph.n = n + 2*m + 2;//3;
    int S =   n + 2*m + 1; // Source
    graph.s = 0;//2; // Super-source
    graph.t = n + 2*m + 2;//3; // Sink
    // Adding connections in edges
    for (int i = 1; i <= m; i++) {
        graph.add_edge(n + 2*i - 1, n + 2*i, infinit);
        degree[n + 2*i - 1] -= 1;
        degree[n + 2*i] += 1;
    }
    // Begin, from source to arbitrary hilltop
    for (int i = 1; i <= n; i++)
        graph.add_edge(S, i, infinit);
    // Limiting flow with degrees
    for (int i = n+1; i <= n + 2*m; i++) {
        if (degree[i] > 0)
            graph.add_edge(graph.s, i, degree[i]);
        else
            graph.add_edge(i, graph.t, -degree[i]);
    }
    // Testing and flowing
    for (int i = 1; i >= 1; i++) {
        // break;
        graph.add_edge(graph.s, S, 1);
        lli res = graph.eval();
        if (res >= m) {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}