P3872 [TJOI2010]电影迷题解

pldzy · 2022-02-25 13:51:27 · 题解

传送门：P3872 [TJOI2010]电影迷

以最大权闭合子图为基础，再加上一点小拓展。

本题解主要是想细讲一下最大权闭合子图。

最大权闭合子图

1. 概念

闭合子图：在原图 G 的闭合子图中，每一个节点，它在 G 中所能到达的所有节点都包含在这个子图中。
最大权闭合子图：即原图 G 中点权之和最大的闭合子图。

2. 运用

目标：求一图的最大权闭合子图。

<1>

先建立一超级源点和超级汇点。

对于每个带权值的节点：

若节点为正，则与超级源点相连，流量为该点权值；
反之，则与超级汇点相连，流量为该点权值相反数。

很明显，在不考虑“每个点在 G 中所能到达的所有节点都包含在这个子图中”这个限制条件时，最大权“闭合子图”肯定是所有正权值之和，也就是现在与源点相连的所有边流量之和。

此时，上述的建边方式的原因就清楚明了了：区分开来正负权值的点。

<2>

然后再加上限制，在点和点之间建边。

此时可以隐约发现：我们会使用最小割去求出最大权子图。

割去一些边，使源点与汇点不相连，最后源点所在的那个子图即为原图的最大权闭合子图。

回过头来：这些边的流量是什么？

这些边的流量为 inf。因为“每个点在 G 中所能到达的所有节点都包含在这个子图中”，所以要保证这些边不会被割去。

<3>

此时可以发现，被割去的边都是与源点或者汇点相连的边。

若一负权值节点与汇点相连的边被割去：

说明此时它放在最大权闭合子图中是最优的状态，但最大权闭合子图的权值和要减去该点权值的绝对值。
若一正权值节点与汇点相连的边被割去：

说明此时它不放在最大权闭合子图中是最优的状态，但最大权闭合子图的权值和要减去该点权值。

这样一来，最大权闭合子图的权值和就是：正权值之和 - 最小割。

然后最小割转化为最大流去求解即可。

回归本题

可以看到，最大权闭合子图模板中，原图中的边不能删去，但本题可以删去。

只是删去这条边也需要代价，那就将此边的流量设为代价而不是 inf 即可。

剩下的就是最大权闭合子图的模板了。

AC Code

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

#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define inf 10000000
#define maxn 700
#define maxm 1000005

int n, m;
int sa[maxn];
int cnt = 1, hd[maxn];
struct node{
    int to, nxt;
    int flw;
}e[maxm];
int in[maxn];
vector <int> out[maxn];
int dep[maxn], vis[maxn];
int sum, ans;
int s, t;

inline int id(int i, int j)
{
    return (i - 1) * m + j;
}

inline void add(int u, int v, int f)
{
    e[++cnt] = (node){v, hd[u], f};
    hd[u] = cnt;
    e[++cnt] = (node){u, hd[v], 0};
    hd[v] = cnt;
}

inline void topo()
{
    queue <int> q;
    rep(i, 1, n * m)
    {
        if(!in[i])
            vis[i] = 1, q.push(i);
    }
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = 0; i < out[u].size(); ++i)
        {   
            int v = out[u][i];
            in[v] -= 1;
            if(!vis[v] and !in[v])
                vis[v] = 1, q.push(v);
        }
    }
}

inline bool bfs()
{
    queue <int> q;
    memset(dep, 0, sizeof dep);
    dep[s] = 1, q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = hd[u], v; i; i = e[i].nxt)
        {
            if(!dep[v = e[i].to] and e[i].flw)
                dep[v] = dep[u] + 1, 
                q.push(v);
        }
    }
    return dep[t] ? 1 : 0;
}

inline int dfs(int u, int cm)
{
    if(u == t or !cm) return cm;
    int lv = 0;
    for(int i = hd[u], v; i and cm; i = e[i].nxt)
    {
        if(!e[i].flw) continue;
        if(dep[v = e[i].to] != dep[u] + 1) continue;
        int res = dfs(v, min(cm, e[i].flw));
        e[i].flw -= res; 
        e[i ^ 1].flw += res;
        cm -= res, lv += res;
    }
    if(!lv) dep[u] = 0;
    return lv;
}

inline int dinic()
{
    while(bfs())
        ans += dfs(s, inf);
    return ans;
}

signed main()
{
    scanf("%d%d", &n, &m);
    s = n + 1, t = s + 1;
    rep(i, 1, n) 
    {
        scanf("%d", &sa[i]);
        if(sa[i] < 0) add(i, t, -sa[i]);
        else add(s, i, sa[i]), sum += sa[i];
    }
    rep(i, 1, m)
    {
        int ut, vt, dt;
        scanf("%d%d%d", &ut, &vt, &dt);
        add(ut, vt, dt);
    }
    printf("%d\n", sum - dinic());
    return 0;
}

感谢阅读。

辛苦管理员审核，若有问题烦请指出。

P3872 [TJOI2010]电影迷 题解