【算法】最大权闭合子图

日常安利两篇文章[网络流]最大权闭合图(转载)
hiho 第119周 最大权闭合子图
闭合图是啥,就是说所有的点连出去的边都指向我们所选的点集,这就是闭合图
那么我们现在要求一个最大权的闭合图,可以通过网络流来解决
我们首先转化模型,我们将所有的正权点与源点s相连,所有的负权点与汇点t相连,原来的图流量我们都换成无穷大
首先我们来证明这么一张图上最小割是简单割
简单割的定义就是割上每条边都与起点或者汇点相连
那么首先我们可以将与起点相连的边都割掉,这些边里面没有无穷大的边,当然这种割法并不一定是最小割
那么对于最小割,它付出的代价一定小于等于刚才那种方案的代价,这就要求最小割不存在无穷大的边。因此,最小割所有的边都会与起点或者终点相连
第二步,我们要证明简单割即为闭合图,闭合图即为简单割。
如果闭合图不是简单割,必然存在一条无穷大的边,那么这个图还保持联通,与割断不相合
如果简单割不是闭合图,那么一定有无穷大的边连向另一个集合,那么这个图也是不连通的,不符合前提
那么到了最关键的一步,最大权闭合子图的权值w = 所有正权点权值之和w0 – 最小割c
证明
设最小割将点集分为两半,有源点的为点集s,有汇点的为点集t,那么最小割容量c = t内原图正权点点权之和 + s中负权点点权绝对值之和,w = s内所有正权点点权之和 – s内所有负权点绝对值之和
所以c + w = 所有正权点点权和
所以w = 所有正权点点权和
例题
luogu P2762 太空飞行计划问题
这个题就是一个比较典型的最大权闭合子图问题,我们可以将实验和仪器划分到两个集合,分别以点权的绝对值向起点/汇点建边,我们割掉与起点相连的边,说明这个实验不够优,不足以让我们去购买相应的仪器,我们割掉与终点相连的边,就说明仪器的代价要小于收益

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int
using namespace std;

const int mo = 1000000007;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

char a;

bool flag;

inline void re(int &x)
{
    x = 0;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
    if(a == '\r' || a == '\n')
        flag = 1;
}

int n, m, t, he, ta, lx, ans, tot = -1;

int q[500], v1[110], v2[110], de[110], head[110], hea[110];

struct in
{
    int to, ne, co;
}ter[10010];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

inline bool bfs()
{
    memset(de, 0, sizeof(de));
    q[he = ta = 0] = 0, de[0] = 1;
    while(he <= ta)
    {
        int qaq = q[he ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(de[to] == 0 && ter[i].co > 0)
                de[to] = de[qaq] + 1, q[++ ta] = to;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t || fl == 0)
        return fl;
    for(ri &i = hea[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(de[to] == de[no] + 1 && ter[i].co)
        {
            int rt = dfs(to, min(fl, ter[i].co));
            if(rt > 0)
            {
                ter[i].co -= rt, ter[i ^ 1].co += rt; return rt;
            }
        }
    }
    return 0;
}

int main()
{
    memset(head, -1, sizeof(head));
    re(m), re(n), t = n + m + 1;
    for(ri i = 1; i <= m; i ++)
    {
        re(v1[i]), ans += v1[i], flag = 0, build(0, i, v1[i]);
        while(!flag)
            re(lx), build(i, lx + m, mo);
    }
    for(ri i = 1; i <= n; i ++)
        re(v2[i]), build(i + m, t, v2[i]);
    while(bfs())
    {
        for(ri i = 0; i <= t; i ++)
            hea[i] = head[i];
        while(int ret = dfs(0, mo))
             ans -= ret;
    }
    for(ri i = 1; i <= m; i ++)
        if(de[i] > 0)
            printf("%d ", i);
    printf("\n");
    for(ri i = 1; i <= n; i ++)
        if(de[i + m] > 0)
            printf("%d ", i);
    printf("\n%d", ans);
}

luogu P2805 [NOI2009]植物大战僵尸

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = gch()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

int h, t, ta, n, m, lx, ly, lz, tot = -1, ans, pri;

int q[1010], de[1010], num[1010], v[1010], he[1010], head[1010];

struct in
{
    int to, ne, co;
}edge[1600010], ter[1600010];

bool flag[1010];

inline int ask(int x, int y)
{
    return (x - 1) * m + y;
}

inline void build(int f, int l, int c)
{
    num[l] ++, edge[++ tot] = (in){l, he[f], c}, he[f] = tot;
}

inline void rebuild(int f, int l, int c)
{
    //cout << f << ' ' << l << ' ' << c << '\n';
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

inline void init()
{
    h = 1;
    for(ri i = 1; i <= n * m; i ++)
        if(num[i] == 0)
            q[++ t] = i;
    while(h <= t)
    {
        int qaq = q[h ++]; flag[qaq] = 1;
        for(ri i = he[qaq]; i >= 0; i = edge[i].ne)
        {
            int to = edge[i].to; num[to] --;
            if(num[to] == 0)
                q[++ t] = to;
        }
    }
    t = 0;
    for(ri i = 1; i <= n * m; i ++)
        if(flag[i] == 0)
            q[++ t] = i;
    while(h <= t)
    {
        int qaq = q[h ++]; flag[qaq] = 0;
        for(ri i = he[qaq]; i >= 0; i = edge[i].ne)
        {
            int to = edge[i].to;
            if(flag[to] == 1)
                q[++ t] = to;
        }
    } 
    tot = -1, t = n * m + 1;
    for(ri i = 1; i <= n * m; i ++)
        if(flag[i] == 1)
        {
            if(v[i] > 0)
                ans += v[i], rebuild(i, t, v[i]);
            else
                rebuild(0, i, - v[i]);
            for(ri j = he[i]; j >= 0; j = edge[j].ne)
            {
                int to = edge[j].to;
                if(flag[to] == 1)
                    rebuild(i, to, 1e9 + 7);
            }
        }
}

inline bool bfs()
{
    memset(de, 0, sizeof(de)), de[q[h = ta = 0] = 0] = 1;
    while(h <= ta)
    {
        int qaq = q[h ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(de[to] == 0 && ter[i].co > 0)
                de[q[++ ta] = to] = de[qaq] + 1;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int lin = 0;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(de[to] == de[no] + 1 && ter[i].co > 0)
        {
            int rt = dfs(to, min(fl - lin, ter[i].co));
            ter[i].co -= rt, ter[i ^ 1].co += rt, lin += rt;
            if(lin == fl)
                return lin;
        }
    }
    return lin;
}

/*
这个题其实是一个比较板子的最大权闭合子图,但是之前没有认真了解过
闭合子图:图内所有点的出边,都指向图内所有点构成的集合中的一个点
这个东西我们可以转化成原图正权点点权之和减去新图最小割
新图怎么建
我们现在考虑植物之间的关系,它是由一堆保护和被保护这样的东西组成的
那么对于一对这样的关系,我们从保护植物向被保护的植物建边
然后跑拓扑排序,将图中的环和受环庇护的植物去掉
那么现在就剩下了一堆一定可以被删除掉的植物
那么我们就需要考虑删除哪些植物划算哪些植物不划算了
现在还是按照保护和被保护的关系建图,流量无限 
但是我们加入一个汇点和一个源点,所有正权点向汇点连边,流量为点权
负权点向源点建边,流量为点权的绝对值
然后跑最小割,答案就是所有正点点权之和减去最小割
至于为什么这么干 我们现在最小割只会割两种边 ,与起点相连和与终点相连的边
那么对于割掉与起点有关系的点,就表示我们现在决定割掉某个植物获取更大的利益
割掉与终点有关系的点,就表示我们现在决定不要某种植物的点权来减少损失 
*/ 

int main()
{
    //freopen("qwq.out", "w", stdout);
    re(n), re(m), memset(he, -1, sizeof(he)), memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
        {
            re(lx), v[ask(i, j)] = lx, re(lz);
            while(lz --)
                re(lx), re(ly), lx ++, ly ++, build(ask(i, j), ask(lx, ly), 1);
        }
    for(ri i = 1; i <= n; i ++)
        for(ri j = m; j > 1; j --)
            build(ask(i, j), ask(i, j - 1), 1);
    init(); 
    while(bfs())
        memcpy(he, head, sizeof(he)), ans -= dfs(0, 1e9 + 7);
    printf("%d", ans);
    return 0;
} 

发表评论

电子邮件地址不会被公开。 必填项已用*标注