网络流24题 -洛谷 P2762 太空飞行计划问题

P2762 太空飞行计划问题

题意

给你n个实验 m个仪器（原题中n和m反了一下）第i个实验会给一个赞助费\(c[i]\) 每个实验都有相应的实验仪器 买第m个实验器材要\(c_2[i]\)的钱
问怎么选实验和器材才能达到收益最高

思路

选了一个实验我们就必须选择相应的器材 所以实验和相应器材的边权应该设为正无穷这样才不会被割掉
对于一组实验和器材 我们必须选择一个花费损失 即要么不选这个实验就要损失c[i],要么就选这个实验那么我们就要损失该实验需要买的器材的总和
可以利用最小割 被割掉的边权就是我们相对损失的钱
源点和所有实验连边 边权c[i] 所有器材和汇点连边 边权\(c_2[i]\) 中间实验和器材的边就是inf
先将所有实验的赞助费都加起来 减去最大流就是答案了
其中与源点联通的点是我们选的 与汇点连接的点则不是我们选的 最后根据dis[i]判断是否选即可

（图来自洛谷题解）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define int ll

const int N = 1e5 + 1;
const int M = 1e5 + 1;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;

int n, m;
int s, t, vtot;
int head[N], cur[N];
int dis[N], etot;
struct edge {
	int v, nxt;
	int f;
}e[M * 2];
//复杂度 O(n^2*m)
//存图用前向星比较方便 有边的信息 
void addedge(int u, int v, int f) {
	//边序号从零开始
	e[etot] = { v, head[u], f }; head[u] = etot++;
	e[etot] = { u, head[v], 0}; head[v] = etot++;
}

//s到t是否还有路径
bool bfs() {
	for (int i = 1; i <= vtot; i++) {
		dis[i] = 0;
		cur[i] = head[i];
	}
	queue<int>q;
	q.push(s); dis[s] = 1;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; ~i; i = e[i].nxt) {
			//有剩余流量且未被访问过
			if (e[i].f && !dis[e[i].v]) {
				int v = e[i].v;
				dis[v] = dis[u] + 1;
				if (v == t) return true;
				q.push(v);
			}
		}
	}
	return false;
}

//找最优路径
int dfs(int u, int m) {
	if (u == t) return m;
	int flow = 0;
	//cur[]当前弧优化 保证增广过了不再增广
	for (int i = cur[u]; ~i; cur[u] = i = e[i].nxt) {
		//如果流量还有剩余 且该边方向是对的
		if (e[i].f && dis[e[i].v] == dis[u] + 1) {
			int f = dfs(e[i].v, min(m, e[i].f));
			e[i].f -= f;
			e[i ^ 1].f += f;
			m -= f;
			flow += f;
			if (!m) break;//保证复杂度
		}
	}
	if (!flow) dis[u] = -1;
	return flow;
}

int dinic() {
	int flow = 0;
	while (bfs()) flow += dfs(s, INF);
	return flow;
}

void init(int s_, int t_, int vtot_) {
	s = s_;
	t = t_;
	vtot = vtot_;
	for (int i = 1; i <= vtot; i++) head[i] = -1;
}

int c[N], c2[N];
void solve() {
    cin >> n >> m;
	string str;
	getline(cin, str);
	vector<int>vec[105];
	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		getline(cin, str);

		stringstream ss;
		ss << str;

		int x;
		ss >> x;
		c[i] = x;
		sum += x;

		while (!ss.eof()) {
			ss >> x;
			vec[i].push_back(x);
		}
	}

	for (int i = 1; i <= m; i++) cin >> c2[i];

    int u, v;
	vector<pair<int, int>>ve1, ve2;

    init(n + m + 1, n + m + 2, n + m + 2);
	for (int i = 1; i <= n; i++) addedge(s, i, c[i]), ve1.push_back({ etot, i });
	for (int i = 1; i <= m; i++) addedge(i + n, t, c2[i]), ve2.push_back({ etot, i });
	for (int i = 1; i <= n; i++)
		for (auto x : vec[i]) addedge(i, x + n, inf);

	int ans = dinic();
	for (int i = 1; i <= n; i++)
		if (dis[i] > 0) cout << i << " ";
	cout << "\n";
	for (int i = 1; i <= m; i++)
		if (dis[i + n] > 0) cout << i << " ";
	cout << "\n";

	cout <<  sum - ans << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int _t = 1;
    //cin >> _t;
    while (_t--)
        solve();
    return 0;
}