常见套路还是要熟练的

懵逼的 题目

传送至 Luogu

扯淡的 题解

不会, 抄的题解…

一开始想的是把仪器和实验分成类似于二分图的图, X放实验, Y放仪器, S向实验连一条费用为实验收益, 流量为1的边, 实验向仪器连边, 仪器向T连费用为负花费 流量为1的边, 然后再向S压流, 枚举选几个实验, 找最大值…然后测完样例才发现错到西伯利亚了(语出: 昊哥)…

正解是最大权闭合子图…
最大权闭合子图: 在一个有向图中找一个子图, 使子图中每一个节点的出边都在这个子图中…应该比较适合解决有依赖的最优化问题…

求解:

  • 转化为二分图, X全是是from, Y全是to (好像必须X里都是正权, Y里都是负权?)
  • 连边…
    • 原图里的该怎么连怎么连(from -> to)…
    • S向X里的节点全部连边, 容量为要连接的X节点的权值
    • X向Y中的节点连边, 容量为INF(其实最大不会超过X的权值)
    • Y向T连边, 容量为Y的权值的绝对值
  • 跑最大流
  • 答案是: X中节点的权值总和 - 最大流流量

虽然不是很懂但好像好有道理的样子

看了看来自dalao的证明(她里面的黄字好像写错了), 似乎好像大概也许懂了…

以Luogu的样例为例建图如下, 左侧的节点1, 2是正权点, 右侧的1, 2, 3是负权点

青色的两条粗线是割边(满流的边)

这里写图片描述

首先一个闭合子图肯定对应一个割, 而且这个割是简单割(要么和$S$直接相连, 要么和$T$直接相连)

  • 然后因为割是满流的边, 所以闭合子图肯定对应一个割集(注意, 这里既不是闭合子图所有的边都在割集里, 也不是能够盈利的闭合子图(比如正权值那边的割就是不会盈利的))
  • 因为在正权和负权节点之间的边是INF, 所以不是正权那一片的边满流了就是负权那一边满流了, 所以割一定和$S$或者$T$直接相连, 而且费用是有限的(废话, $\infty$的的边并不能直接连接$S, T$)

这里写图片描述

一个网络中的节点肯定被割分为两部分, 一部分靠近S, 记为S, 一部分靠近T, 记为T

如上, 最小割为深蓝的那条细线, 所有的节点被分为S(红色)和T(青色)两部分

然后又因为建图(看这个脑回路多么巧妙),
割的容量 = T中正节点的权值和(割边在正权值点和S的连边中, 是正权值点的边满流) + S中负节点的权值和的绝对值(割边在负权值点到T的连边中, 负权值点的边满流): 因为割总是满流的, 所以割的容量就可以分为两种满流: 正权值点一侧满流的容量 + 负权值一侧点满流的容量

而最大权闭合子图呢? 他的权值是S中正权值的和(选择实验的收益)(注: S中的边并不一定是满流的) - S中负权值和的绝对值(选中这些收益所需要的亏损, 成本)(负权点只有满流才能说是选了这个仪器)
而且只有这样才算一个完整的闭合子图: 割边不可能在中间INF的边上, 所以如果实验满流而仪器不满就不会选这个实验

我们发现…两个东西加起来…

最大权闭合子图的权值 + 对应割的容量 = T中正节点的权值和 + S中负节点的权值和的绝对值 + S中正节点的权值和 - S中负节点的权值和的绝对值 = T中正节点的权值和 + S中正节点的权值和 = 所有正权点的权值和…

Emmmmmm…所以最大权闭合子图的权值就是 所有正权节点的权值和 - 最小割的容量

妈耶不容易…看了1Week终于懂了…

沙茶的 代码

Clion不允许中文名字…Dev又㕛叒叕崩了…fly_in_univ这个名字是不是很社会?

// fly_in_univ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <queue>
#define MAXN (200 + 5)
#define MAXM (40000 + 5)
#define MAXE (50 + 5)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define rev(a) ((((a) - 1) ^ 1) + 1)
#define bh(a) ((a) + MAXE)
#define ubh(a) (((a) > MAXE) ? ((a) - MAXE) : (a))
using namespace std;
const int s = 0, t = MAXN - 1;
struct edg
{
    int from;
    int to;
    int next;
    int cap;
    int flow;
    edg(){}
    edg(int a, int b, int c, int d, int e): from(a), to(b), next(c), cap(d), flow(e) {}
}b[MAXM << 1];
int cntb;
int g[MAXN];

int en, yyn;
int cost[MAXE];
int ans;
int dis[MAXN];
vector<int> oute;
vector<int> outy;
void adn(int, int, int);//
void init(); //
void solve(); //
bool bfs();
void print();
int dinic(int, int);
int main()
{
    init();
    solve();
    print();
    return 0;
}
void adn(int from, int to, int cap)
{
    b[++cntb] = edg(from, to, g[from], cap, 0);
    g[from] = cntb;
}
void init()
{
    cin >> en >> yyn;
    string sra[MAXE];
    int srx[MAXE][MAXE];
    memset(srx, 0, sizeof(srx));
    getchar();
    for (int i = 1; i <= en; i++)
    {
        getline(cin, sra[i], '\r');
    }
    for (int i = 1; i <= en; i++)
    {
        int dqn = sra[i].length();
        int dqwz = 0;
        for (srx[i][0] = 1; dqwz < dqn; ++srx[i][0])
        {
            bool zf = false;
            while (dqwz < dqn && (sra[i][dqwz] < '0' || sra[i][dqwz] > '9'))
            {
                if (sra[i][dqwz] == '-')
                    zf = true;
                ++dqwz;
            }
            while (dqwz < dqn && (sra[i][dqwz] >= '0' && sra[i][dqwz] <= '9'))
            {
                srx[i][srx[i][0]] *= 10;
                srx[i][srx[i][0]] += sra[i][dqwz++] - '0';
            }
            srx[i][srx[i][0]] = ((zf) ? (-srx[i][srx[i][0]]) : (srx[i][srx[i][0]]));
        }
        --srx[i][0];
    }

    for (int i = 1; i <= en; i++)
    {
        ans += srx[i][1];
        adn(s, i, srx[i][1]);
        adn(i, s, 0);
        for (int j = 2; j <= srx[i][0]; j++)
        {
            adn(i, bh(srx[i][j]), srx[i][1]);
            adn(bh(srx[i][j]), i, 0);
        }
    }
    for (int i = 1; i <= yyn; i++)
    {
        cin >> cost[i];
        adn(bh(i), t, cost[i]);
        adn(t, bh(i), 0);
    }

}
void solve()
{
    while (bfs())
    {
        int zl = dinic(s, INF);
        if (!zl)
            break;
        ans -= zl;
    }
    for (int i = 1; i <= en; i++)
    {
        if (dis[i])
            oute.push_back(i);
    }
    for (int i = 1; i <= yyn; i++)
    {
        if (dis[bh(i)])
            outy.push_back(i);
    }
}
bool bfs()
{
    memset(dis, 0, sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s] = 1;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (int i = g[dq]; i; i = b[i].next)
        {
            if (b[i].cap > b[i].flow && !dis[b[i].to])
            {
                dis[b[i].to] = dis[dq] + 1;
                q.push(b[i].to);
            }
        }
    }
    return dis[t];
}
void print()
{
    for (int i = 0; i < oute.size(); i++)
    {
        cout << oute[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < outy.size(); i++)
    {
        cout << outy[i] << " ";
    }
    cout << endl << ans;
}
int dinic(int dq, int maxf)
{
    if (dq == t || (!maxf))
        return maxf;
    int re = 0;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (b[i].cap > b[i].flow && dis[b[i].to] == dis[dq] + 1)
        {
            int zl = dinic(b[i].to, min(b[i].cap - b[i].flow, maxf));
            maxf -= zl;
            re += zl;
            b[i].flow += zl;
            b[rev(i)].flow -= zl;
        }
    }
    return re;
}

/*
2 3
10 1 2
25 2 3
5 6 7
*/

By 怯懦的 Cansult