翻车笔记_ 太空飞行计划问题 [网络流24, 最大流, 翻车]

常见套路还是要熟练的

懵逼的 题目

传送至 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这个名字是不是很社会?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
// 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