Solution to POJ2125 Destroying The Graph

2021/01/02

题目翻译:《有向图破坏》

爱丽丝和鲍勃正在玩以下游戏。

首先,爱丽丝绘制一个 \(N\) 个点 \(M\) 条边的有向图。

然后,鲍勃试图毁掉它。

在每一步操作中,鲍勃都可以选取一个点,并将所有射入该点的边移除或者将所有从该点射出的边移除。

已知,对于第 \(i\) 个点,将所有射入该点的边移除所需的花费为 \(W_i^+\),将所有从该点射出的边移除所需的花费为 \(W_i^-\)。

鲍勃需要将图中的所有边移除,并且还要使花费尽可能少。请帮助鲍勃计算最少花费。

输入格式:

第一行包含 \(N\) 和 \(M\)。

第二行包含 \(N\) 个正整数,第 \(i\) 个为 \(W_i^+\)。

第三行包含 \(N\) 个正整数,第 \(i\) 个为 \(W_i^-\)。

接下来 \(M\) 行,每行包含两个整数 \(a\), \(b\),表示从点 \(a\) 到点 \(b\) 存在一条有向边。

所有点编号从 \(1\) 到 \(N\),图中可能由重边或自环。

输出格式:

第一行输出整数 \(W\),表示鲍勃所需的最少花费。

第二行输出整数 \(K\),表示鲍勃需要进行的操作步数。

接下来 \(K\) 行,每行输出一个鲍勃的具体操作。

如果操作为将所有射入点 \(i\) 的边移除,则输出格式为i +

如果操作为将所有从点 \(i\) 射出的边移除,则输出格式为i -

如果答案不唯一,则输出任意一种即可。

数据范围:

\(1 \le N \le 100\),

\(1 \le M \le 5000\),

\(1 \le W_i^+,W_i^- \le 10^6\),

时/空限制:\(1s / 64MB\)

输入样例:

3 6
1 2 3
4 2 1
1 2
1 1
3 2
1 2
3 1
2 3

输出样例:

5
3
1 +
2 -
2 +

思路:

覆盖集:一个点集,可以覆盖所有的边,覆盖是指一个边至少有一个端点在这个点集中。

对于普通的无向图,求覆盖集是一个 \(NPC\) 1 问题,没有多项式复杂度的算法可以解决,但是对于二分图,网络流算法可以多项式复杂度内解决,如果不是二分图,就只能暴力搜索了。此题的背景是二分图。

二分图最小点权覆盖集,首先对于点权都是非负的情况分析,因为网络流不能解决负值流量。 左边集合的所有点与虚拟源点 \(S\) 连边,边权为点权,右边集合的所有点和汇点 \(T\) 连边,边权为点权。 中间所有点保持自己原来的连边,边权 \(INF\),这样的目的是最小割一定不会包含中间的边。

对于有负权值点的二分图,既然要最小点权覆盖,那么负权点直接先全部选上,然后删去这些点以及已经被这些点覆盖的边,剩下的问题就用上述非负点权的做法解决即可。

最小割的边要么和 \(S\) 相连,要么和 \(T\) 相连,对于中间的一条“线段”的两个端点,这两个端点和 \(S\) 与 \(T\) 的连边,最小割肯定只会有一条,因为只需要一条就可以断掉路径。而被选的这条,对应线段的那个端点,就是覆盖当前“线段”的点,而边权等于点权,所以最小割的值就是最小点权覆盖集的点权和。

对于本题,建立二分图是关键。 假设一条有向边是 \(a\)\(\rightarrow\)\(b\) 那么可以花费代价 \(a-\) 删去这条边,也可以花费代价 \(b+\) 删去这条边,所以所有 \(+\) 号的点是一个点集,\(-\) 号是一个点集,然后 \(b+\) 向 \(a-\) 连边,边权 \(INF\),这样就是二分图的最小点权覆盖问题。

注意建图是一个点只会在图中最多出现 \(2\) 次,既有入边也有出边,那么就会在左右边都出现这个点, 这个点的所有出边或者所有入边都在二分图中间显现出来,注意题意:一次删掉所有的出边或者入边,但是这个点没有被删掉,可以一次删掉出边,接着删掉入边,一个点是可以被操作 \(2\) 次的,然后求最小割就是点权和的答案。

输出操作方案:从虚拟源点 \(S\) 出发,沿容量大于 \(0\) 的边走,所有能到的点是一个割集,到不了的是另外一个割集。 假设 \(2\) 个割集是 \(S\) 和 \(T\),那么只考虑 \(S\) 到 \(T\) 的有向边就可以了,因为建图是双向建边。 遍历所有的边,如果一个边是割边,和 \(S\) 连通但是和 \(T\) 不连通,那么就是 \(+\) 号操作, 同样和 \(T\) 连通和 \(S\) 不连通就是 \(-\) 号操作。

这个解释在此题建立了虚拟源汇点的二分图中,就是左侧不可达的点表示被操作 \(1\) 的流选中了,右侧可达的点表示从左侧开始无论如何也没有被流选中,只能留给操作 \(2\),另外还要注意的一点是割边的方向始终是从割集 \(S\) 指向割集 \(T\) 的。

代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 210, M = (N + 5010) * 2 + 10, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

bool bfs() {
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i]) {
            int ver = e[i];
            if (d[ver] == -1 && f[i]) {
                d[ver] = d[t] + 1; //层数
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit) { //当前u 从S到u最大的可增加流量是limit
    if (u == T) return limit;
    int flow = 0; //从当前点往后流的流量最多是多少
    for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {
        cur[u] = i; //当前搜的弧
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i]) { //只搜下一层的点 防止环的干扰
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1; //当前边到终点没有增广路 就层数设为-1,之后不会再搜到了
            f[i] -= t, f[i ^ 1] += t, flow += t; //存在增广路 就更新残留网络
        }
    }
    return flow;
}

int dinic() {
    int r = 0, flow;
    while (bfs())  //bfs同时建立分层图 以及返回是否有增广路
        while (flow = find(S, INF)) r += flow; //所有能够增广的流量累加

    return r;
}

void dfs(int u) {
    st[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
        if (f[i] && !st[e[i]])
            dfs(e[i]);
}

int main() {
    scanf("%d%d", &n, &m);
    //左边+号点是1-n, 右边-号点是n+1到2n
    S = 0, T = n * 2 + 1;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) { //+号点
        int w;
        scanf("%d", &w);
        add(S, i, w);
    }

    for (int i = 1; i <= n; i++) { //-号点
        int w;
        scanf("%d", &w);
        add(n + i, T, w);
    }

    while (m --) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, n + a, INF); //从左边b+向右边a-连边
    }

    printf("%d\n", dinic());

    //方案
    dfs(S);

    //统计操作数量
    int count = 0;
    for (int i = 0; i < idx; i += 2) {
        int a = e[i ^ 1]; //起点 就是反向边的终点
        int b = e[i]; //终点

        if (st[a] && !st[b]) //只能搜到一个端点,那就是一条割边
            count++;
    }

    printf("%d\n", count);

    //所有+号操作
    for (int i = 0; i < idx; i += 2) {
        int a = e[i ^ 1], b = e[i];
        if (st[a] && !st[b]) {
            if (a == S) printf("%d +\n", b); //该边的起点是S同时是割边,那么就是加号操作
        }
    }
    //-号操作
    for (int i = 0; i < idx; i += 2) {
        int a = e[i ^ 1], b = e[i];
        if (st[a] && !st[b]) {
            if (b == T) printf("%d -\n", a - n); //该边的终点是S同时是割边,那么就是减号操作
        }
    }

    return 0;
}

 

参考: