[网络流24题] P2762 太空飞行计划
最大权闭合子图，需要方案
https://www.luogu.com.cn/problem/P2762
没啥好说的，裸的最大权闭合子图。
需要注意的是最后是否连通可以用 dep[v]判断
点击查看代码
#include
#define endl '\n'
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0)
#define P pair
typedef long long ll;
using namespace std;
const int N = 100 + 5;
const int M = N * N + 5;
const int INF = 0x3f3f3f3f;
struct edge {
int v, w, to;
} e[M * 2];
int pre[N], cnt_edge, dep[N];
int S, T, z, head[N], sum;
int n, m, q[N], cur[N];
void add(int u, int v, int w) {
e[cnt_edge] = {v, w, head[u]};
head[u] = cnt_edge++;
e[cnt_edge] = {u, 0, head[v]};
head[v] = cnt_edge++;
}
bool bfs() {
for (int i = 0; i <= T; i++) dep[i] = 0;
dep[S] = 1;
int l = 0, r = 1;
q[r] = S;
while (l < r) {
int u = q[++l];
for (int i = head[u]; i != -1; i = e[i].to) {
int v = e[i].v;
if (!dep[v] && e[i].w) dep[v] = dep[u] + 1, q[++r] = v;
}
}
return dep[T];
}
int dfs(int u, int mi) {
int res = 0;
if (mi == 0 || u == T) return mi;
for (int &i = cur[u]; i != -1; i = e[i].to) {
int v = e[i].v;
if (dep[u] + 1 == dep[v] && e[i].w) {
int minn = dfs(v, min(mi - res, e[i].w));
e[i].w -= minn;
e[i ^ 1].w += minn;
res += minn;
if (res == mi) return res;
}
}
if (res == 0) dep[u] = 0;
return res;
}
int dinic() {
ll res = 0;
while (bfs()) {
memcpy(cur, head, sizeof(head));
// cout<> n >> m;
memset(head, -1, sizeof head);
S = n + m + 1, T = S + 1;
int val;
ll sum = 0;
for (int i = 1; i <= n; i++) {
cin >> val;
val = val > 0 ? val : -val;
vals[i] = val;
sum += val;
add(S, id(i, 0), val);
char tools[10000];
memset(tools, 0, sizeof tools);
cin.getline(tools, 10000);
int ulen = 0, tool;
while (sscanf(tools + ulen, "%d", &tool) == 1)
//之前已经用scanf读完了赞助商同意支付该实验的费用
{ // tool是该实验所需仪器的其中一个
//这一行，你可以将读进来的编号进行储存、处理，如连边。
// cout << "add: " << i << " " << tool << endl;
add(id(i, 0), id(tool, 1), INF);
if (tool == 0)
ulen++;
else {
while (tool) {
tool /= 10;
ulen++;
}
}
ulen++;
}
}
for (int i = 1; i <= m; i++) {
cin >> val;
val = val > 0 ? val : -val;
vals[i + n] = val;
add(id(i, 1), T, val);
}
int ans = sum - dinic();
// puts("-----------");
for (int i = 1; i <= n; i++) {
if (dep[i]) cout << i << " ";
}
cout << endl;
for (int i = 1; i <= m; i++) {
if (dep[i + n]) cout << i << " ";
}
cout << endl;
cout << ans << endl;
return 0;
}
放一下我最大权闭合子图的笔记
? 有一个有向图，每一个点都有一个权值（可以为正或负或0），选择一个权值和最大的子图，使得每个点的后继都在子图里面，这个子图就叫最大权闭合子图。
? 解决方法：
? 从源点s向每个正权点连一条容量为权值的边，每个负权点向汇点t连一条容量为权值的绝对值的边，原边容量全部为无限大。
? 求它的最小割，割掉后，与源点s连通的点构成最大权闭合子图，权值为正权值之和-最小割。
PS 用 \(Dinic\) 来写，是否与源点s连通可以用分层时的 \(dep\) 判断，其他写法可以用 \(dist\) 等
for (int i = 1; i <= n; i++) {
if (dep[i]) cout << i << " ";//连通则输出
}
如：https://nanti.jisuanke.com/t/41096
点击查看代码
#include
#include
#include
#include