有向图破坏问题

解题思路

本题给定一个有向图，每次可以指定一个点，然后将这个点出发的所有边删掉或者将这个点到达的所有边删掉。对于每个点都有这样两种操作。每个点的两种操作都会有不同的花费。

然后问我们将所有边删除需要的最小花费。

这里和最小权点覆盖集的证明有点出入，证明中讨论的是无向图，本题则是有向图。对于每一条有向边 $a$ -> $b$，都有两种选择，一种是删除从 $a$ 出发的所有边时删掉，花费是 $W_a^-$；一种是删除到达 $b$ 的所有边时删掉，花费是 $W_b^+$。因此对于每条边来说，这两个操作至少要选择一个。这个要求和点覆盖问题非常像。

到这已经和最小权点覆盖集问题有关联了，但是每个点有两种操作，因此可以将每个点进行拆点处理，左部节点是所有费用为 $W^+$ 的点，即删除到达的边，右部节点是所有费用为 $W^-$ 的点，即删除出去的边。对于一条边 $a$ -> $b$，这条边对应的两个点至少要选一个，所以对应的从 $b^+$ 向 $a^-$ 连一条边，这样就能构造出一个二分图，对于原问题来说，$a^-$ 和 $b^+$ 至少选一个；对于二分图中对应的这条边来说，两个端点至少选一个。所以这两个问题是完全一致的。然后还需要考虑数量关系，原问题每个操作都有一个权值，对应到二分图中每个点都有一个点权，且点权非负，因此这就完全转化成了一个二分图的点权非负的最小权点覆盖问题，按照固定的求法解决即可。

然后还需要求出操作方案，而原问题的每个操作都对应到二分图中的每个点，所以求操作方案其实等价于求最小权的点覆盖集。这里结合证明过程中根据最小割构造点覆盖集的方法。先从源点开始往下搜，所有能走到的点在 $S$ 集合，所有走不到的点在 $T$ 集合，然后枚举所有正向边，找出所有割边（起点在 $S$，终点在 $T$ 的边），然后将所有割边中除了源点、汇点的点都找出来，就是最小权的点覆盖集。

具体可参考 最小权点覆盖集的相关证明

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210, M = 10410, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧
bool st[N]; //记录每个点能否从源点被搜到，能搜到属于 S 集合，不能搜到属于 T 集合

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

void dfs(int u) //爆搜找出最小割，能从源点搜到的点属于 S 集合，反之属于 T 集合
{
    st[u] = true;

    //在残量网络中沿着容量 > 0 的边往下搜
    for(int i = h[u]; i != -1; i = ne[i])
        if(w[i])
        {
            int j = e[i];
            if(!st[j]) dfs(j);
        }
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //统计从 u 往汇点能传输的最大流量，流量上限为 flow
{
    if(u == T) return flow;

    int rest = 0;
    for(int i = cur[u]; i != -1 && rest < flow; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(d[j] == d[u] + 1 && w[i])
        {
            int k = find(j, min(w[i], flow - rest));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest += k;
        }
    }
    return rest;
}

int dinic() //求最小割
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h); //初始化邻接表

    //左部节点为 +，编号 1 ~ n，右部节点为 -，编号 n + 1 ~ 2 * n
    S = 0, T = 2 * n + 1; //源点、汇点
    for(int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        add(S, i, x); //从源点向所有左部节点连一条容量为 w+ 的边
    }
    for(int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        add(i + n, T, x); //从所有右部节点向汇点连一条容量为 w- 的边
    }

    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a + n, INF); //从 b+ 向 a- 连一条容量为 INF 的边
    }

    printf("%d\n", dinic()); //最小权点覆盖 = 最小割

    dfs(S); //爆搜找出最小割

    int cnt = 0; //记录操作数量
    for(int i = 0; i < idx; i += 2)
    {
        int a = e[i ^ 1], b = e[i];
        if(st[a] && !st[b]) cnt++; //当前边为割边，说明找到一次操作
    }
    printf("%d\n", cnt);

    //输出 + 操作
    for(int i = 0; i < idx; i += 2)
    {
        int a = e[i ^ 1], b = e[i];
        if(st[a] && !st[b] && a == S) printf("%d +\n", b); //当前边是割边且起点是源点，说明是 + 操作
    }

    //输出 - 操作
    for(int i = 0; i < idx; i += 2)
    {
        int a = e[i ^ 1], b = e[i];
        if(st[a] && !st[b] && b == T) printf("%d -\n", a - n); //当前边是割边且起点是汇点，说明是 - 操作
    }

    return 0;
}