题解 CF1082G 【Petya and Graph】

· · 题解

题解区的一些大佬解释的有点难以理解，我来发表一下比较通俗易懂的另一种思路。

一、题意解释

从给定的图中选出一个子图，使得该子图中所有边的权值和减去所有点的权值和最大。

二、为什么是最小割？

大家都说这种题要用最小割——但是为什么呢？

我们要知道，对于任何一道（看起来不像是最小割的）题，它能用最小割算法来解决，有两个显著的特征：

（注：并不是说满足以上条件的都能用最小割求解，只是说发现以上两个性质时，思路可以往最小割靠拢一点）

我们知道，根据题意，图中所有的点要么被选择，要么没被选择，只有两种可能的状态，所以条件(1)是满足的；那么条件(2)呢？我们知道所有点的选择状态，就能推断出问题的答案吗？

答案是肯定的！因为你会发现，知道了点的选择状态，也就知道了边的选择状态。

这是因为，所有边的权值都是大于 0 的。所以，对于任何一条边，如果它连接的点都被选中了，那么把它选上，一定会对答案产生贡献。

既然条件(1)和条件(2)都能满足，那么我们就可以尝试一下，从最小割这条路径来解题。

三、如何解决？

第一步：理清逻辑关系（贡献/损失）

我们将问题转化成如果...，则能对答案产生...的贡献/损失的形式。

注意：理清逻辑关系的时候，首先，主语必须是你之前选定的那种物体（在这道题目中，它是图中的点）；其次，一定要概括全面！如果不能同时满足以上两点，那么这道题就几乎无法进行最小割（或你选择的这种物体无法进行最小割）

我们来理一下这道题的逻辑：

不难发现，以上就是这道题的全部内容了。

第二步：将损失转化为贡献，将最大值转化为最小值

只要第一步进行成功，这道题就完成了一半了。不过题目要求的是最大值，而最小割是用来求最小值的。所以我们要转化问题，将贡献最大转化成损失最小。

为了求最小损失，我们先要假设贡献达到了最大值，也就是说，先假设所有点都没有选，而所有的边都被选择（虽然这种情况是不存在的），此时不难看出，ans=\sum\limits_{i=1}^mw_i.

接着就可以把把这道题的逻辑转换成：

求出来最小损失之后，再把之前求得的极端情况下的最大值减去求出来的最小损失即可。

第三步：根据逻辑关系建图，求最小割（最大流）

根据网络流套路，我们先设置一个源点 s 和一个汇点 t.

对于一个点 i ，若 i\in s ，则代表节点 i 被选择，否则（即当 i\in t 时）则代表节点 i 没被选择。

接下来我们看：

如果选择了一个点 i ，则对答案产生 a_i 的损失。

这个很好建图，直接从 i 向 t 连一条权值为 a_i 的边即可，这样子，当 i\in s 的时候，就必须要把这条边割掉。

难点在这里：

如果没有同时选择 u_i 和 v_i ，则对答案产生 w_i 的损失。

要做到这一点，还需要再创建一个额外的节点 p ，然后 s\to p 连一条边， p\to u_i 连一条边， p\to v_i 连一条边，这三条边的权值都是 w_i.

画画图模拟一下，你会发现确实可以实现。

到这里图就建好了，我们求一遍最小割（最大流）即可。

别忘了最后要拿理想情况去减哦

Code

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define MAXN 500000
#define MAXM 500000
#define INF 0x7fffffff
struct Edge
{
    long long next, to, dis;
} bian[MAXM];
long long h[MAXN], used[MAXN], dep[MAXN];
long long s, t;
long long temp = 1;
void add(long long from, long long to, long long dis)
{
    temp++;
    bian[temp].dis = dis;
    bian[temp].next = h[from];
    bian[temp].to = to;
    h[from] = temp;
}
void addE(long long from, long long to, long long dis)
{
    add(from, to, dis);
    add(to, from, 0);
}
bool bfs()
{
    long long x, i;
    queue<long long> Q;
    Q.push(s);
    memset(dep, 0, sizeof(dep));
    dep[s] = 1;
    while (!Q.empty())
    {
        x = Q.front();
        Q.pop();
        for (i = h[x]; i; i = bian[i].next)
            if (bian[i].dis != 0 && dep[bian[i].to] == 0)
            {
                dep[bian[i].to] = dep[x] + 1;
                Q.push(bian[i].to);
            }
    }
    return dep[t] != 0;
}
long long dfs(long long x, long long in)
{
    long long out = 0, i, k;
    if (x == t)
        return in;
    for (i = used[x]; i && in != 0; i = bian[i].next, used[x] = i)
    {
        if (bian[i].dis != 0 && dep[bian[i].to] == dep[x] + 1)
        {
            k = dfs(bian[i].to, min(bian[i].dis, in));
            bian[i].dis -= k;
            bian[i ^ 1].dis += k;
            in -= k;
            out += k;
        }
    }
    if (out == 0)
        dep[x] = 0;
    return out;
}
long long getId(long long depth, long long x)
{
    return (depth - 1) * 5000 + x;
}
long long n, m;
int main()
{
    scanf("%lld%lld", &n, &m);
    long long i, j;
    long long x, y, z;
    long long tot = 0;
    s = MAXN - 1;
    t = MAXN - 2;
    for (i = 1; i <= n; i++)
    {
        scanf("%lld", &x);
        addE(getId(1, i), t, x);
    }
    for (i = 1; i <= m; i++)
    {
        scanf("%lld%lld%lld", &x, &y, &z);
        addE(s, getId(2, i), z);
        addE(getId(2, i), getId(1, x), z);
        addE(getId(2, i), getId(1, y), z);
        tot += z;
    }
    long long ans = 0;
    while (bfs())
    {
        memcpy(used, h, sizeof(h));
        ans += dfs(s, INF);
    }
    printf("%lld", tot - ans);
    return 0;
}