题解 P2711 【小行星】

· · 题解

看到数据范围，以及“消除”、“最少次数”的字样，就知道与最小割有关。问题在于怎么割呢？

要消除一颗小行星，可以从三个面来消除。x 面，y 面和 z 面。不难想到，将这三个面上的每一个坐标建两个点——入点和出点。由入点向出点连一条容量为 1 的边。当入点和出点之间的这条边被割掉时，就说明是在这个面的这一个点消除了一次。

我们想要消除所有的小行星，就说明每一颗小行星在 x 面，y 面或 z 面这三个面中，至少有一个面把它消除了。也就是说，不存在一条连通 x-y-z 的路径，这就是割了。

于是我们对于每一颗小行星，从 x 面的出点向 y 面的入点连一条容量为 INF 的边（仅为保证点之间的连通性），从 y 面的出点向 z 面的入点连容量为 INF 的边。再从超级源向每个 x 面的入点连容量为 INF 的边，从每个 z 面的出点向超级汇连容量为 INF 的边。

建出来的图大致如下（样例）：

根据上面的分析，显然地，就是求 s-t 最小割，这样就能保证每颗小行星都被消在某个面上。

但是……图好乱……

不难发现，这张图是可以简化的。注意到从超级源 S 向每一个 x 连出的边，下一条边都是从 x 的入点向 x 的出点连的一条容量为 1 的边。根据 Total Flow 一题可知，这两条边就类似于串联的关系，是可以合并的。

于是我们简化了这张图，改为直接从超级源 S 向每个 x （入点就可以不要了，于是就没有出入点之分了）连一条权值为 1 的边。从 z 面的边到终点同理，也可以简化。

简化后的图大致如下：

这样只要拆 y 面的点就好了。是不是清爽多了？

最后求解该图的最小割即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 500, INF = 0x7F7F7F7F;

struct edge {
    int to, cap, rev;
};

int n, k;
vector <edge> G[MAXN*4+2];

edge make_edge(int to, int cap, int rev) {
    edge x;
    x.to = to, x.cap = cap, x.rev = rev;
    return x;
}

void add_edge(int from, int to, int cap) {
    G[from].push_back( make_edge(to, cap, G[to].size()) );
    G[to].push_back( make_edge(from, 0, G[from].size() - 1) );
}

void init() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        add_edge(x, y + 500, INF);
        add_edge(y + 500, y + 1000, 1);
        add_edge(y + 1000, z + 1500, INF);
    }
    for (int i = 1; i <= 500; ++i) {
        add_edge(0, i, 1);
        add_edge(i + 1500, 2001, 1);
    }
}

namespace Dinic {
    int level[MAXN*4+2];
    int iter[MAXN*4+2];

    void bfs(int s) {
        bool mark[MAXN*4+2];
        queue <int> q;
        memset(mark, 0, sizeof mark);
        memset(level, -1, sizeof level);

        q.push(s);
        mark[s] = true;
        level[s] = 0;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            mark[u] = false;

            for (int i = 0; i < G[u].size(); ++i) {
                edge &e = G[u][i];
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[u] + 1;
                    if (!mark[e.to]) {
                        mark[e.to] = true;
                        q.push(e.to);
                    }
                }
            }
        }
    }

    int dfs(int u, int t, int f) {
        if (u == t)
            return f;
        for (int &i = iter[u]; i < G[u].size(); ++i) {
            edge &e = G[u][i];
            if (e.cap > 0 && level[e.to] > level[u]) {
                int d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    int max_flow(int s, int t) {
        int flow = 0;
        for (;;) {
            bfs(s);
            if (level[t] < 0)
                return flow;
            memset(iter, 0, sizeof iter);
            int f;
            while ( (f = dfs(s, t, INF)) > 0 )
                flow += f;
        }
    }
}

int main() {
    init();
    printf("%d\n", Dinic::max_flow(0, 2001));
    return 0;
}