ISAP最大流

思路

这道题需要收益最大,也就是求出最小割,应使用最大流求解。

读入

对于一整行不知道有多少个数据,并且结尾还是\r\n,我们可以使用C++的stringstream,把整行用getline读进一个string,然后放入stringstream,从里面读取数据

建图

  • 我们设$0$为超级源点,$n + m + 1$为超级汇点,每个实验对应$[1, m]$,每个仪器对应$[m + 1, n]$
  • 对于$\forall i \in [1, m]$

    • 从$0$向$i$连边,容量为费用
    • 对于$\forall j \in R_i$,从$i$向$m + j$连边,容量为$\infty$
  • 对于$\forall j \in [1, n]$

    • 从$j + m$向$n + m + 1$连边,容量为费用

输出

显然,最终输出的那个数是总费用减最大流。

那么如何输出方案?

根据ISAP的分层原理,我们把gap优化去掉(貌似这就成普通的SAP了),使得最终流完的深度区分更明显。这样,跑完一遍最大流后,被割掉的点深度趋近于$0$,没被割掉的点深度趋近于$n + m$,那么我们取中间值作为分界线,深度大于这个值的点就是我们留下来的点,输出即可

程序实现

// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <string>
#include <sstream>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 55;
const int INF = 0x3f3f3f3f;

int n, m;

struct Edge{
    int to, val;
    Edge *next, *ops;
    Edge(int to, int val, Edge *next): to(to), val(val), next(next){}
};

Edge *head[MAXN << 1];

inline void AddEdge(int u, int v, int w) {
    head[u] = new Edge(v, w, head[u]);
    head[v] = new Edge(u, 0, head[v]);
    head[u]->ops = head[v]; head[v]->ops = head[u];
}

int s, t, dep[MAXN << 1], /*gap[MAXN << 1], */res;

void Bfs() {
    memset(dep, -1, sizeof(dep));
    //memset(gap, 0, sizeof(gap));
    dep[t] = 0; //gap[dep[t]]++;
    queue<int> q; q.push(t);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (Edge *e = head[u]; e; e = e->next) {
            int v = e->to;
            if (dep[v] != -1) continue;
            dep[v] = dep[u] + 1;
            //gap[dep[v]]++;
            q.push(v);
        }
    }
}

int Dfs(int u, int flow) {
    if (u == t) {
        res += flow;
        return flow;
    }
    int used = 0;
    for (Edge *e = head[u]; e; e = e->next) {
        int v = e->to;
        if (e->val && dep[v] == dep[u] - 1) {
            int mi = Dfs(v, std :: min(e->val, flow - used));
            if (mi) {
                e->val -= mi;
                e->ops->val += mi;
                used += mi;
            }
            if (used == flow) return used;
        }
    }
    //gap[dep[u]]--;
    //if (gap[dep[u]] == 0) dep[s] = n + m + 3;
    dep[u]++;
    //gap[dep[u]]++;
    return used;
}

void Work() {
    res = 0;
    Bfs();
    while (dep[s] <= n + m + 2) Dfs(s, INF);
}

int main() {
    cin >> m >> n;
    s = 0; t = n + m + 1;
    int tot = 0;
    string str;
    stringstream ss;
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        tot += x;
        AddEdge(s, i, x);
        ss.clear();
        getline(cin, str);
        ss << str;
        while (ss >> x) AddEdge(i, x + m, INF);
    }
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        AddEdge(i + m, t, x);
    }
    Work();
    /*for (int i = 1; i <= m; i++) cout << dep[i] << ' ';
    cout << endl;
    for (int i = m + 1; i <= n + m; i++) cout << dep[i] << ' ';
    cout << endl;*/
    for (int i = 1; i <= m; i++) {
        if (dep[i] > n + m >> 1) cout << i << ' ';
    }
    cout << endl;
    for (int i = m + 1; i <= n + m; i++) {
        if (dep[i] > n + m >> 1) cout << i - m << ' ';
    }
    cout << endl;
    cout << tot - res << endl;
    return 0;
}

PS:虽然本代码可以AC此题,但是由于最后输出方案的方法有一点点玄学成分,所以如果针对这份代码刻意制造毒瘤数据,有可能是可以HACK掉的