飞行员配对方案问题
题目链接。二分图匹配模板。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 105;
int n, m, match[N];
int head[N], numE = 0;
bool vis[N];
struct E{
int next, v;
} e[N * N];
void add(int u, int v) {
e[++numE] = (E) { head[u], v };
head[u] = numE;
}
bool find(int u) {
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (vis[v]) continue;
vis[v] = true;
if (!match[v] || find(match[v])) {
match[v] = u; return true;
}
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
int u, v;
while (scanf("%d%d", &u, &v), v != -1)
add(u, v - n);
int ans = 0;
for (int i = 1; i <= n; i++) {
memset(vis, false, sizeof vis);
if (find(i)) ans++;
}
printf("%d
", ans);
for (int i = 1; i <= m; i++)
if (match[i]) printf("%d %d
", match[i], i + n);
}
太空飞行计划问题
题目链接。是一个最大权闭合图问题。这问题的证明真是太神仙了，构造网络的方式：
- 起点向实验连一条流量为费用的边
- 实验向仪器连流量为无限的边
- 仪器向终点连流量为费用的边
由于证明很抽象，自己有一个突发奇想感性的理解：
-
由于中间连的是无限流量，所以限制肯定在两边。
-
假如一个实验它的流量流完了，说明他的费用不比它小，那么留着它就是祸患，所以可以它的答案有删除的贡献
-
加入一个实验留了一部分，这一部分失去的其实就是仪器费用，有删除的贡献
-
由于最大流 / 最小割是个实时更新残余网络的算法，所以可以实时解决问题。
所以答案就是实验总费用 (-) 最小割。输出方案源自证明的过程，即起点这边联通块实际就是一个最大权闭合图。
#include <cstdio>
#include <iostream>
#include <sstream>
#include <string>
#include <cstring>
using namespace std;
const int N = 55, L = N * 2, INF = 1e9;
int m, n, s, t, p[N], c[N], d[L], q[L], sum;
int head[L], numE = 1, flow, maxflow;
string g;
struct E{
int next, v, w;
} e[N * N + 4 * N];
void add(int u, int v, int w) {
e[++numE] = (E) { head[u], v, w };
head[u] = numE;
}
void addEdge(int u, int v, int w) {
add(u, v, w); add(v, u, 0);
}
bool bfs() {
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
d[s] = 1, q[0] = s;
while (hh <= tt) {
int u = q[hh++];
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (!d[v] && e[i].w) {
d[v] = d[u] + 1;
q[++tt] = v;
if (v == t) return true;
}
}
}
return false;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int rest = flow;
for (int i = head[u]; i && rest; i = e[i].next) {
int v = e[i].v;
if (e[i].w && d[v] == d[u] + 1) {
int k = dinic(v, min(rest, e[i].w));
if (!k) d[v] = 0;
e[i].w -= k, e[i ^ 1].w += k;
rest -= k;
}
}
return flow - rest;
}
int main() {
scanf("%d%d
", &m, &n);
s = n + m + 1, t = n + m + 2;
for (int i = 1; i <= m; i++) {
getline(cin, g); stringstream sin(g);
sin >> p[i]; addEdge(s, i, p[i]); sum += p[i];
int x;
while (sin >> x) addEdge(i, x + m, INF);
}
for (int i = 1; i <= n; i++)
scanf("%d", c + i), addEdge(i + m, t, c[i]);
while (bfs())
while(flow = dinic(s, INF)) maxflow += flow;
for (int i = 1; i <= m; i++) if(d[i]) printf("%d ", i);
puts("");
for (int i = 1; i <= n; i++) if(d[i + m]) printf("%d ", i);
printf("
%d
", sum - maxflow);
return 0;
}
最小路径覆盖问题
题目链接 能用二分图算法就不用网络流。根据定理，在拆点二分图上 最小路径覆盖 $= $ 总数 (-) 二分图最大匹配。
输出路径，这次不能用那个技巧了，但通过定理的推导我们知道左侧非匹配点和路径终点是一一对应的，我们只要从非匹配点出发倒序递推每条路径就行了。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 155, M = 6005;
int n, m, match[N];
int head[N], numE = 0;
bool vis[N], st[N];
struct E{
int next, v;
} e[M];
void add(int u, int v) {
e[++numE] = (E) { head[u], v };
head[u] = numE;
}
bool find(int u) {
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (vis[v]) continue;
vis[v] = true;
if (!match[v] || find(match[v])) {
match[v] = u; return true;
}
}
return false;
}
void print(int x) {
if (x == 0) return;
print(match[x]);
printf("%d ", x);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, u, v; i <= m; i++)
scanf("%d%d", &u, &v), add(u, v);
int ans = n;
for (int i = 1; i <= n; i++) {
memset(vis, false, sizeof vis);
if (find(i)) ans--;
else st[i] = true;
}
for (int i = 1; i <= n; i++)
if (st[i]) print(i), puts("");
printf("%d
", ans);
}
魔术球问题
题目链接。 模拟题意，每次扩大编号，尝试是否可行。转换模型，将编号中两点间是完全平方数的，由编号大的向小的连一条边，很显然这是个 DAG。
即在 DAG 上用最少的路径（不相交）覆盖所有的点。根据定理，在拆点二分图上 最小路径覆盖 $= $ 总数 (-) 二分图最大匹配，当路径覆盖 $ > n$ 时，即可停止。输出方案，因为我们找增广路都是从新增的往前找，所以每条路径的终点一定是最小的，从小到大一次考虑没访问的点，不断递归它的匹配点（由定理的证明过程我们知道匹配边都是一条路径的边）直到无法跳为止。
那个点边的最大值是自测最大数据找的极值。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 1570, M = 18000;
int K, n, res = 0, match[N];
int head[N], numE = 0;
bool vis[N];
struct E{
int next, v;
} e[M];
void add(int u, int v) {
e[++numE] = (E) { head[u], v };
head[u] = numE;
}
bool find(int u) {
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (vis[v]) continue;
vis[v] = true;
if (!match[v] || find(match[v])) {
match[v] = u; return true;
}
}
return false;
}
int main() {
int cnt = 0;
scanf("%d", &K);
for (n = 1; ; n++) {
for (int i = sqrt(n) + 1; i * i < 2 * n; i++) add(n, i * i - n);
if (find(n)) res++;
memset(vis, false, sizeof vis);
if (n - res > K) break;
}
printf("%d
", --n);
for (int i = 1; i <= n; i++)
if (!vis[i]) {
for (int j = i; j; j = match[j]) printf("%d ", j), vis[j] = true;
puts("");
}
return 0;
}
圆桌问题
题目链接。二分图多重匹配问题：
- 让起点连单位代表，流量为 (r)
- 由于同一单位不能再同一餐桌，所以每个单位朝每个餐桌连边，流量为 (1)
- 餐桌向终点连边，流量为 (c)
输出方案：看一下单位向餐桌的边哪条空了即可（流完了）。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int M = 155, N = 275, INF = 1e9;
int m, n, s, t, q[M + N], d[M + N], sum;
int head[M + N], numE = 1;
struct E{
int next, v, w;
} e[(M * N + M + N) * 2];
void add(int u, int v, int w) {
e[++numE] = (E) { head[u], v, w };
head[u] = numE;
}
void addEdge(int u, int v, int w) {
add(u, v, w), add(v, u, 0);
}
bool bfs() {
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = s, d[s] = 1;
while (hh <= tt) {
int u = q[hh++];
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (!d[v] && e[i].w) {
d[v] = d[u] + 1;
q[++tt] = v;
if (v == t) return true;
}
}
}
return false;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int rest = flow;
for (int i = head[u]; i && rest; i = e[i].next) {
int v = e[i].v;
if (d[v] == d[u] + 1 && e[i].w) {
int k = dinic(v, min(rest, e[i].w));
if (!k) d[v] = 0;
e[i].w -= k, e[i ^ 1].w += k;
rest -= k;
}
}
return flow - rest;
}
int main() {
scanf("%d%d", &m, &n);
s = m + n + 1, t = m + n + 2;
for (int i = 1, r; i <= m; i++)
scanf("%d", &r), sum += r, addEdge(s, i, r);
for (int i = 1, c; i <= n; i++)
scanf("%d", &c), addEdge(i + m, t, c);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) addEdge(i, j + m, 1);
int flow, maxflow = 0;
while (bfs())
while (flow = dinic(s, INF)) maxflow += flow;
if (maxflow != sum) puts("0");
else {
puts("1");
for (int u = 1; u <= m; u++) {
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (v != s && !e[i].w) printf("%d ", v - m);
}
puts("");
}
}
}
最长不下降子序列问题
题目链接。（第一次见这种题不会建图。。只好看题解，然后发现是我题读错了。）
第一问
设 (f[i]) 以 (i) 结尾的最长不下降子序列，dp即可。
第二问
用分层图的思想，把 (f[i]) 按照值划分成 (s) 个不同的值。
-
由于每个点只能在一个序列的原则，拆点限制，把 (i) 拆成一个入点和一个出点，入点向出点连流量为 (1) 的边
-
由起点向每一个 (f[i] = 1) 的点连 (1) 的流量。
-
由每一个 (f[i] = s) 的点向终点连 (1) 的流量。
-
将能够转移的 (i, j) （即 (i < j, f[i] + 1 = f[j]) ）连一条边
每一条从起点到终点的路径都是一个长度为 (s) 的最长不下降子序列。
这样去除最多的序列等价于找到最多的从 (s, t) 互不干扰的路径，这里流量为 (1)，最大流和它们是等价的。
第三问
与第二问不同的就是两个可以反复使用，所以把 (1, n) 所在内部入点出点的边流量设为无限，并且如果它们与起点终点连过边，流量也设为无限。这样既设计为除了 (1, n)，剩下点只能经过一次，和题目等价。 有个小技巧，改变流量可以直接加流量，跑最大流不用重新跑一遍，加一条边可以在上次的残余网络上跑。
并且要注意一个特例就是 (n = 1) 的情况，这时候不能起点向 (1) 连边，否则就输出 (INF) 了。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 505, L = N * 2, M = N * (N - 1) + N * 2, INF = 1e9;
int n, S, s, t, a[N], f[N], d[L], q[L], maxflow, flow;
int head[L], numE = 1;
struct E{
int next, v, w;
} e[M];
void add(int u, int v, int w) {
e[++numE] = (E) { head[u], v, w };
head[u] = numE;
}
void addEdge(int u, int v, int w) {
add(u, v, w), add(v, u, 0);
}
bool bfs() {
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = s, d[s] = 1;
while (hh <= tt) {
int u = q[hh++];
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (!d[v] && e[i].w) {
d[v] = d[u] + 1;
q[++tt] = v;
if (v == t) return true;
}
}
}
return false;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int rest = flow;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (d[v] == d[u] + 1 && e[i].w) {
int k = dinic(v, min(rest, e[i].w));
if (!k) d[v] = 0;
e[i].w -= k, e[i ^ 1].w += k;
rest -= k;
}
}
return flow - rest;
}
int main() {
scanf("%d", &n);
s = 2 * n + 1, t = 2 * n + 2;
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 1; i <= n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++)
if (a[j] <= a[i]) f[i] = max(f[i], f[j] + 1);
S = max(S, f[i]);
}
printf("%d
", S);
for (int i = 1; i <= n; i++) {
addEdge(i, i + n, 1);
if (f[i] == 1) addEdge(s, i, 1);
if (f[i] == S) addEdge(i + n, t, 1);
for (int j = 1; j < i; j++)
if (a[j] <= a[i] && f[j] + 1 == f[i]) addEdge(j + n, i, 1);
}
while (bfs())
while (flow = dinic(s, INF)) maxflow += flow;
printf("%d
", maxflow);
if (S != 1) addEdge(s, 1, INF), addEdge(1, 1 + n, INF);
if (f[n] == S) addEdge(n * 2, t, INF), addEdge(n, n * 2, INF);
while (bfs())
while (flow = dinic(s, INF)) maxflow += flow;
printf("%d
", maxflow);
}
试题库问题
题目链接。把题和类别分别放左右两边，把能匹配的题和类型中间连边，是二分图，我们求的是二分图的多重匹配。多重匹配最优解法即建网络，根据题意设计起点到题的流量为 (1)，题和类型的流量也是 (1)，类型到终点的流量是读入要选出的题数，跑最大流即可。输出方案，看二分图中间的边哪条被流过的即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1025, S = 25, INF = 1e9;
int K, n, m, s, t, d[N], q[N], maxflow, flow;
int head[N], numE = 1;
vector<int> ans[S];
struct E{
int next, v, w;
} e[(N * S + N + S) << 1];
void add(int u, int v, int w) {
e[++numE] = (E) { head[u], v, w };
head[u] = numE;
}
void addEdge(int u, int v, int w) {
add(u, v, w), add(v, u, 0);
}
bool bfs() {
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
d[s] = 1, q[0] = s;
while (hh <= tt) {
int u = q[hh++];
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w && !d[v]) {
d[v] = d[u] + 1;
q[++tt] = v;
if (v == t) return true;
}
}
}
return false;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int rest = flow;
for (int i = head[u]; i && rest; i = e[i].next) {
int v = e[i].v;
if (e[i].w && d[v] == d[u] + 1) {
int k = dinic(v, min(flow, e[i].w));
if (!k) d[v] = 0;
e[i].w -= k, e[i ^ 1].w += k;
rest -= k;
}
}
return flow - rest;
}
int main() {
scanf("%d%d", &K, &n);
s = n + K + 1, t = n + K + 2;
for (int i = 1, x; i <= K; i++)
scanf("%d", &x), addEdge(n + i, t, x), m += x;
for (int i = 1, p, x; i <= n; i++) {
scanf("%d", &p); addEdge(s, i, 1);
while (p--) scanf("%d", &x), addEdge(i, n + x, 1);
}
while (bfs())
while (flow = dinic(s, INF)) maxflow += flow;
if (maxflow != m) puts("No Solution!");
else {
for (int u = 1; u <= n; u++) {
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (v != s && !e[i].w) ans[v - n].push_back(u);
}
}
for (int i = 1; i <= K; i++) {
printf("%d:", i);
for (int j = 0; j < ans[i].size(); j++) printf(" %d", ans[i][j]);
puts("");
}
}
}
机器人路径规划问题
题目链接。据说是一道假题？
方格取数问题
这个构造方式也是始料不及的。把相邻有矛盾的点连上边，这显然是一个二分图。考虑答案求的是删除最少的带权点使得二分图没有边。即可以建网络，一个点到起点 / 终点的流量是他本身的权值。
要取出的数总权最大，就要让删的最少。 要删除点的数量总权值最少 (Leftrightarrow) 最小割 (Leftrightarrow) 最大流。最后用总数减最大流即可。
复杂度：边数 (n * m) 级别，点数 (n * m) 级别，跑 Dinic 复杂度 (O(NMsqrt{NM}))
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 105;
typedef long long LL;
const LL INF = 1e18;
int n, m, s, t, a[N][N], d[N * N], q[N * N];
int head[N * N], numE = 1;
LL flow, maxflow, sum;
struct E{
int next, v;
LL w;
} e[N * N * 4];
void add(int u, int v, LL w) {
e[++numE] = (E) { head[u], v, w };
head[u] = numE;
}
void addEdge(int u, int v, LL w) {
add(u, v, w); add(v, u, 0);
}
bool bfs() {
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = s, d[s] = 1;
while (hh <= tt) {
int u = q[hh++];
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (!d[v] && e[i].w) {
d[v] = d[u] + 1;
q[++tt] = v;
if (v == t) return true;
}
}
}
return false;
}
LL dinic(int u, LL flow) {
if (u == t) return flow;
LL rest = flow;
for (int i = head[u]; i && rest; i = e[i].next) {
int v = e[i].v;
if (e[i].w && d[v] == d[u] + 1) {
LL k = dinic(v, min(rest, e[i].w));
if (!k) d[v] = 0;
e[i].w -= k, e[i ^ 1].w += k;
rest -= k;
}
}
return flow - rest;
}
int num(int i, int j) { return (i - 1) * m + j; }
int main() {
scanf("%d%d", &n, &m);
s = n * m + 1, t = n * m + 2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]); sum += a[i][j];
if ((i + j) & 1) {
addEdge(s, num(i, j), a[i][j]);
if (i > 1) addEdge(num(i, j), num(i - 1, j), INF);
if (i < n) addEdge(num(i, j), num(i + 1, j), INF);
if (j > 1) addEdge(num(i, j), num(i, j - 1), INF);
if (j < m) addEdge(num(i, j), num(i, j + 1), INF);
} else {
addEdge(num(i, j), t, a[i][j]);
}
}
}
while (bfs())
while (flow = dinic(s, INF)) maxflow += flow;
printf("%lld
", sum - maxflow);
}
餐巾计划问题
题目链接。瞪眼半天还是不会，我枯了。
显然每天有两个状态转移时刻，一个是一个是每天开始前 (a_0)（需求干净毛巾），每天结束时 (a_1)（提供脏毛巾的处理）：
-
买新毛巾 (s) → (a_0)，流量无限，费用为 (p)
-
快洗 (a_1) → ((a + m)_0)，流量无限，费用为 (f)
-
慢洗 (a_1) → ((a + n)_0)，流量无限，费用为 (s)
-
延期送洗 (a_1) → ((a + 1)_1)，流量无限，费用为 (0)
-
每天结束后，餐厅会生产和求等量的脏餐巾：(s) → (a_1)，流量为 (r[a])，费用为 (0)
-
每天开始时，需要提交 (r[i]) 个餐巾，提交方式给汇点： (a_0) 箭头 (t)，流量为 (r[a])，费用为 (0)
在任何边上的流量，相当于一个餐巾被执行了相应的过程，并且花费一定的费用，要求是跑完最大流（满足所有条件），且费用最小。显然肯定有能满足所有条件（不够可以买买买），所以我们跑最小费用最大流。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef long long LL;
const int N = 2005, INF = 2e9;
typedef pair<LL, int> PII;
int n, s, t, c[N], c0, m1, c1, m2, c2;
LL ans, incf[N << 1], dis[N << 1];
int pre[N << 1];
int head[N << 1], numE = 1;
bool vis[N << 1];
priority_queue<PII, vector<PII>, greater<PII> > q;
struct E{
int next, v, w, c;
} e[N * 12];
void add(int u, int v, int w, int c) {
e[++numE] = (E) { head[u], v, w, c };
head[u] = numE;
}
void addEdge(int u, int v, int w, int c) {
add(u, v, w, c), add(v, u, 0, -c);
}
bool dijkstra() {
memset(dis, 0x3f, sizeof dis);
memset(vis, false, sizeof vis);
while (!q.empty()) q.pop();
dis[s] = 0, q.push(make_pair(0, s));
incf[s] = INF;
while (!q.empty()) {
PII u = q.top(); q.pop();
if (vis[u.y]) continue;
vis[u.y] = true;
for (int i = head[u.y]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w && dis[u.y] + e[i].c < dis[v]) {
dis[v] = dis[u.y] + e[i].c;
incf[v] = min((LL)e[i].w, incf[u.y]);
pre[v] = i;
q.push(make_pair(dis[v], v));
if (v == t) return true;
}
}
}
return false;
}
void update() {
int x = t;
while (x != s) {
int i = pre[x];
e[i].w -= incf[t], e[i ^ 1].w += incf[t];
x = e[i ^ 1].v;
}
ans += incf[t] * dis[t];
}
int main() {
scanf("%d", &n);
s = n * 2 + 1, t = n * 2 + 2;
for (int i = 1; i <= n; i++) scanf("%d", c + i);
scanf("%d%d%d%d%d", &c0, &m1, &c1, &m2, &c2);
for (int i = 1; i <= n; i++) {
addEdge(s, i, INF, c0);
if (i + m1 <= n) addEdge(i + n, i + m1, INF, c1);
if (i + m2 <= n) addEdge(i + n, i + m2, INF, c2);
if (i < n) addEdge(i + n, i + n + 1, INF, 0);
addEdge(s, i + n, c[i], 0);
addEdge(i, t, c[i], 0);
}
while (dijkstra()) update();
printf("%lld
", ans);
}
航空路线问题
这题的限制是每个点只能经过一次，而网络流做到的是边的限制，考虑点边转换把每个点拆成入点 (A_i)和出点 (B_i)：
找到一条 (1) → (n) → (1) 路径，等价于两条 (1) → (n) 的不相交路径，要求经过点最多，建立费用流模型：
- (A_i) → (B_i) 流量为 1（若 (i = 1) 或 (n) 流量为 (2))，费用为 (1)
- 一条边 ((u, v))，(B_u) → (A_v) 流量为 (1)（若 (1) → (n) 则为 (2)），费用为 (0)
方案 (dfs) 跑零流边求解。（ (dfs) 复杂度 (O(n)) 的，找到一条路径就 break）
我太菜了，循环队列写不对。。
#include <cstdio>
#include <iostream>
#include <string>
#include <unordered_map>
#include <cstring>
using namespace std;
const int N = 105, L = N << 1, INF = 0x3f3f3f3f;
unordered_map<string, int> S;
int n, m, s, t, q[L], dis[L], incf[L], pre[L];
int ans[L], tot = 0, maxflow = 0;
string a, b, g[N];
int head[L], numE = 1, sum = 0;
bool vis[L];
struct E{
int next, v, w, c;
} e[N * N + N * 2];
void add(int u, int v, int w, int c) {
e[++numE] = (E) { head[u], v, w, c };
head[u] = numE;
}
void inline addEdge(int u, int v, int w, int c) {
add(u, v, w, c); add(v, u, 0, -c);
}
bool spfa() {
memset(dis, -0x3f, sizeof dis);
int hh = 0, tt = 1;
q[0] = s, dis[s] = 0, incf[s] = INF;
while (hh != tt) {
int u = q[hh++];
if (hh == L) hh = 0;
vis[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w && dis[u] + e[i].c > dis[v]) {
dis[v] = dis[u] + e[i].c;
incf[v] = min(incf[u], e[i].w);
pre[v] = i;
if (!vis[v]) {
vis[v] = true, q[tt++] = v;
if (tt == L) tt = 0;
}
}
}
}
return dis[t] != dis[0];
}
void update() {
int x = t;
while (x != s) {
int i = pre[x];
e[i].w -= incf[t], e[i ^ 1].w += incf[t];
x = e[i ^ 1].v;
}
sum += dis[t] * incf[t];
maxflow += incf[t];
}
void dfs(int u) {
vis[u] = true;
ans[++tot] = u;
for (int i = head[u + n]; i; i = e[i].next) {
int v = e[i].v;
if (v <= n && !vis[v] && !e[i].w) {
dfs(v);
break;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
s = 1, t = n * 2;
for (int i = 1; i <= n; i++) cin >> g[i], S[g[i]] = i;
for (int i = 1; i <= n; i++) addEdge(i, i + n, (i == 1 || i == n) ? 2 : 1, 1);
for (int i = 1; i <= m; i++) {
cin >> a >> b;
int x = S[a], y = S[b];
if (x > y) swap(x, y);
addEdge(x + n, y, (x == 1 && y == n) ? 2 : 1, 0);
}
while (spfa()) update();
if (maxflow < 2) {
cout << "No Solution!" << endl;
return 0;
}
cout << sum - 2 << endl;
dfs(1);
for (int i = 1; i <= tot; i++) cout << g[ans[i]] << endl;
tot = 0;
dfs(1);
for (int i = tot; i; i--) cout << g[ans[i]] << endl;
return 0;
}
软件补丁问题
题目链接。我自闭了，题目都没看懂，样例一脸懵逼，后来发现是把 B1, B2 看反了。
看到 (n <= 20)，想到装压，可以设一个二进制状态 (S) ，若当前这一位是 (1) 则修复成功状态，反之则是错误，即起始状态是 (0)，目标状态为 (111111111...)
对于一个状态 (S)，枚举每一个操作 (i)：
-
根据定义，若 (B1[i] cup S = 0) 且 (B2[i] cup S = B2[i])，则可以进行这次操作:
即 状态 (S) 转移至 (S cup complement_cup F21[i] cap F1[i])，代价为 (t)。
显然每一种成功的操作等价于一条从起点到终点的路径，要求代价最少，最短路即可（网络流与这题的关系：让每条路径流量为 (1) 即为网络流。。）
复杂度玄学。（第一次建边 (MLE) 了）
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 20, M = 100, L = 1 << N, INF = 0x3f3f3f3f;
int n, m, s = 0, t, q[1 << N], dis[1 << N], B1[M], B2[M], F1[M], F2[M], c[M];
int head[1 << N], numE = 0;
bool vis[1 << N];
char g[N];
// + 属于 a, - 属于 b
void work(int &a, int &b) {
for (int i = 0; i < n; i++)
if (g[i] == '+') a |= 1 << i;
else if(g[i] == '-') b |= 1 << i;
}
int spfa() {
int hh = 0, tt = 1;
memset(dis, 0x3f, sizeof dis);
q[0] = s, dis[s] = 0;
while (hh != tt) {
int u = q[hh++]; vis[u] = false;
if (u == L) hh = 0;
for (int j = 0; j < m; j++) {
if ((u & B1[j]) == 0 && (u & B2[j]) == B2[j]) {
int v = ((u & (~F2[j] & t)) | F1[j]), w = c[j];
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
if (!vis[v]) {
vis[v] = true, q[tt++] = v;
if (tt == L) tt = 0;
}
}
}
}
}
return dis[t] == INF ? 0 : dis[t];
}
int main() {
scanf("%d%d", &n, &m);
t = (1 << n) - 1;
for (int i = 0; i < m; i++) {
scanf("%d%s", c + i, g);
work(B1[i], B2[i]);
scanf("%s", g);
work(F2[i], F1[i]);
}
printf("%d
", spfa());
}
星际转移问题
题目链接。太菜了不会又去看题解。
隐约的感知到，每个人从地球到月球从图论的角度上来说构成一条路径，每个人又可以抽象成单位 (1) 的流，所以这题就是网络流？但是由于天数时间轴的影响不能直接建图。所以这题解启示我们建立分层图，即某天的一个位置抽象为为一个图中的节点。
题意中的两种决策乘坐飞船、下船等待可以抽象成两种边（由于具有传递性所以只需连接一步操作的节点）。不过还要注意的是每天地球和月球的边要注意和源点和汇点进行联系，进而达到图题一体的模式。
- 乘坐飞船走：对于一条飞船上的路径，一天对应位置的节点 (Rightarrow) 后一天对应位置的节点，流量为 (H[i]) ，表示通过这种方式最多可以送走 (H[i]) 人
- 下船等待：某位置一天的节点 (Rightarrow) 下一天同一位置的节点，流量无限
- 源点向每天的地球连边无限，每天月球向汇点连接无限
发现二分复杂度是冗余的，不妨从小到大枚举时间。
考虑存在情况的最坏情况下的时间，一条路径肯定没有环（不然可以不走环），所以一条链最长有 (m + 2) 个点， (m + 1) 条边，可能一个循环才能跑一次，所以每转移一条边 (n + 2) 个时间。所以时间最多 ((m + 2) * (n + 2) <= 330)，所以枚举到 (330) 就行了。。总复杂度 ((N + M + 11500 * sqrt{4950}))，一看就跑得很快。（这里的复杂度由于边加边边在残余网络上跑，所以貌似是这个复杂度 # 我也不确定）
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 14, M = 21, S = 55, L = 5000, INF = 1e9, LM = 23500;
int n, m, s, t, K, p[M], r[M], h[M][N + 2], q[L], d[L], maxflow, flow;
int head[L], numE = 1;
struct E{
int next, v, w;
} e[LM];
void add(int u, int v, int w) {
e[++numE] = (E) { head[u], v, w };
head[u] = numE;
}
void addEdge(int u, int v, int w) {
add(u, v, w); add(v, u, 0);
}
bool bfs() {
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = s, d[s] = 1;
while (hh <= tt) {
int u = q[hh++];
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w && !d[v]) {
d[v] = d[u] + 1;
q[++tt] = v;
if (v == t) return true;
}
}
}
return false;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int rest = flow;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w && d[v] == d[u] + 1) {
int k = dinic(v, min(rest, e[i].w));
if (!k) d[v] = 0;
e[i].w -= k, e[i ^ 1].w += k;
rest -= k;
}
}
return flow - rest;
}
// 第 i 天，第 j 号飞船
int get(int i, int j) {
if (j == 0) return 3 + i * (n + 2);
else if(j == -1) return 4 + i * (n + 2);
return 4 + i * (n + 2) + j;
}
void build(int i) {
int cnt = 2 + i * (n + 2);
int st = cnt + 1, ed = cnt + 2;
addEdge(s, st, INF), addEdge(ed, t, INF);
for (int j = 1; j <= n; j++) addEdge(get(i - 1, j), get(i, j), INF);
for (int j = 0; j < m; j++) {
int u = h[j][(i - 1) % r[j]], v = h[j][i % r[j]];
addEdge(get(i - 1, u), get(i, v), p[j]);
}
}
int main() {
scanf("%d%d%d", &n, &m, &K);
s = 1, t = 2;
// 第 0 天的地球和月亮连边
addEdge(1, 3, INF), addEdge(4, 2, INF);
for (int i = 0; i < m; i++) {
scanf("%d%d", p + i, r + i);
for (int j = 0; j < r[i]; j++) scanf("%d", &h[i][j]);
}
for (int t = 1; t <= 330; t++) {
build(t);
while (bfs())
while(flow = dinic(s, INF)) maxflow += flow;
if (maxflow >= K) {
printf("%d
", t);
return 0;
}
}
puts("0");
return 0;
}
孤岛营救问题
这次跑分层图 (bfs) 即可。
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 2e9;
const int N = 11;
int n, m, P, K, S, g[N][N];
int w[N][N][4], dis[N][N][1 << N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
bool vis[N][N][1 << N];
struct Node{
int x, y, s, d;
bool operator < (const Node &x) const {
return d > x.d;
}
};
priority_queue<Node> q;
// { 上下左右 }
int inline dijkstra() {
memset(dis, 0x3f, sizeof dis);
dis[1][1][g[1][1]] = 0;
q.push((Node){1, 1, g[1][1], 0});
while(!q.empty()) {
Node u = q.top(); q.pop();
if(vis[u.x][u.y][u.s]) continue;
if(u.x == n && u.y == m) return u.d;
for (int i = 0; i < 4; i++) {
int nx = u.x + dx[i], ny = u.y + dy[i];
if(nx < 1 || nx > n || ny < 1 || ny > m || w[u.x][u.y][i] == INF) continue;
if(w[u.x][u.y][i] && ((u.s >> w[u.x][u.y][i] & 1) == 0)) continue;
int d = u.d + 1, s = u.s | g[nx][ny];
if(d < dis[nx][ny][s]) {
dis[nx][ny][s] = d;
q.push((Node){nx, ny, s, d});
}
}
}
return -1;
}
int main() {
scanf("%d%d%d%d", &n, &m, &P, &K);
for (int i = 1, x1, y1, x2, y2, v; i <= K; i++) {
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &v);
if(!v) v = INF;
if(x1 > x2) swap(x1, x2), swap(y1, y2);
if(y1 > y2) swap(x1, x2), swap(y1, y2);
if(x1 < x2) {
w[x1][y1][1] = v;
w[x2][y2][0] = v;
} else {
w[x1][y1][3] = v;
w[x2][y2][2] = v;
}
}
scanf("%d", &S);
for (int i = 1, x, y, v; i <= S; i++) {
scanf("%d%d%d", &x, &y, &v);
g[x][y] |= 1 << v;
}
printf("%d
", dijkstra());
return 0;
}
汽车加油行驶问题
大概是 Acwing 176. 装满的油箱 的拓展版，一个简单的分层最短路的模型。
把每个节点、还能走多少步作为一个节点，建一个 (N * N * K) 个节点的图，可以设三元组（一个节点） ((x, y, k)) 表示在 ((x, y))，还能走 (k) 步。
对于题目中的每种操作方式可对应一种带权有向边（或进行限制）：
- ((x, y, k) Rightarrow (Next_x, Next_y, k - 1)) 其中 ((Next_x, Next_y)) 表示一步能走到的位置，若 (x, y) 一个变小，边权为 (B)，否则为 (0)
- 强制加油，若遇到油库，强制让加一个 (A) 的费用并让 (k = K)。
- 手动加油：((x, y, k) Rightarrow (x, y, K)) 边权为 (A + C) （注意这里要先建加油站然后再加油。。）
最小费用 (Leftrightarrow) 最短路
还有一些细节，比如起点 ((1, 1, K)) 终点满足坐标为 ((N, N)) 即可。
最多 (N ^2 K = 100000) 个点，(5N ^2K = 500000) 条边，故 Dijkstra (O(N^2Klog{(N^2K)})) 顺利跑过
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 105, S = 15, L = N * N * S, M = L * 5;
int n, K, A, B, C, dis[N][N][S], g[N][N];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
bool vis[N][N][S];
struct Node{
int x, y, k, step;
bool operator < (const Node &b) const {
return step > b.step;
}
};
priority_queue<Node> q;
int dijkstra() {
memset(dis, 0x3f, sizeof dis);
dis[1][1][K] = 0; q.push((Node) { 1, 1, K, 0 });
while (!q.empty()) {
Node u = q.top(); q.pop();
if (vis[u.x][u.y][u.k]) continue;
vis[u.x][u.y][u.k] = true;
if (u.x == n && u.y == n) return u.step;
if (u.k) {
for (int i = 0; i < 4; i++) {
int nx = u.x + dx[i], ny = u.y + dy[i], nk = u.k - 1;
if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
int w = i < 2 ? 0 : B;
if (g[nx][ny]) w += A, nk = K;
if (u.step + w < dis[nx][ny][nk]) {
dis[nx][ny][nk] = u.step + w;
q.push((Node){ nx, ny, nk, u.step + w });
}
}
} else {
if (u.step + A + C < dis[u.x][u.y][K]) {
dis[u.x][u.y][K] = u.step + A + C;
q.push((Node) { u.x, u.y, K, u.step + A + C });
}
}
}
return -1;
}
int main() {
scanf("%d%d%d%d%d", &n, &K, &A, &B, &C);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) scanf("%d", &g[i][j]);
printf("%d
", dijkstra());
return 0;
}
数字梯形问题
题目链接。互不相交点，直接套路把点拆成入点和出点，建网络，把费用搞在入点和出点的边上。
源点向第一行连流量为 (1)，费用 (0) 的边。
最后一行向汇点连流量无限，费用 (0) 的边。
规则 1
所有边流量为 (1)
规则 2
- 入点 (Rightarrow) 出点的流量为无限
- 不同节点的连边流量为 (1)
规则 3
所有边的流量为无限
每个规则重新建图跑一遍最大费用最大流。（注意这里不能向求最大流一样在残余网络上跑，因为 EK 是基于贪心，并且当前其实最大流已经被限制了。）
复杂度
节点数 ((M + N) * N le 400)，边数同阶，(O(NM^2)) 轻松跑过。
Tips：点的编号可以用等差数列搞一下。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 25, S = 1205, INF = 0x3f3f3f3f;
int m, n, L, a[N][N << 1], s, t, pre[S], dis[S], incf[S], q[S];
int head[S], numE = 1, ans;
bool vis[S];
struct E{
int next, v, w, c;
} e[N * 6 + S * 6];
void add(int u, int v, int w, int c) {
e[++numE] = (E) { head[u], v, w, c };
head[u] = numE;
}
void addEdge(int u, int v, int w, int c) {
add(u, v, w, c); add(v, u, 0, -c);
}
bool spfa() {
memset(dis, 0xcf, sizeof dis);
memset(vis, false, sizeof vis);
int hh = 0, tt = 1;
q[0] = s, dis[s] = 0, incf[s] = INF;
while (hh != tt) {
int u = q[hh++]; vis[u] = false;
if (hh == S) hh = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w && dis[u] + e[i].c > dis[v]) {
dis[v] = dis[u] + e[i].c;
pre[v] = i;
incf[v] = min(incf[u], e[i].w);
if (!vis[v]) {
q[tt++] = v, vis[v] = true;
if (tt == S) tt = 0;
}
}
}
}
return dis[t] != 0xcfcfcfcf;
}
void update() {
int x = t;
while (x != s) {
int i = pre[x];
e[i].w -= incf[t];
e[i ^ 1].w += incf[t];
x = e[i ^ 1].v;
}
ans += dis[t] * incf[t];
}
// 第 i 行，第 j 列的编号
int get(int i, int j) {
return (m + m + i - 2) * (i - 1) / 2 + j;
}
void rebuild(int id) {
memset(head, 0, sizeof head);
ans = 0, numE = 1;
for (int i = 1; i <= m; i++) addEdge(s, i, 1, 0);
for (int i = 1; i < m + n; i++) addEdge(get(n, i) + L, t, INF, 0);
for (int i = 1; i <= n; i++)
for (int j = 1; j < m + i; j++)
addEdge(get(i, j), get(i, j) + L, id >= 2 ? INF : 1, a[i][j]);
for (int i = 1; i < n; i++) {
for (int j = 1; j < m + i; j++) {
addEdge(get(i, j) + L, get(i + 1, j), id == 3 ? INF : 1, 0);
addEdge(get(i, j) + L, get(i + 1, j + 1), id == 3 ? INF : 1, 0);
}
}
}
int main() {
scanf("%d%d", &m, &n);
L = (m * 2 + n - 1) * n / 2;
// 入点 x, 出点 x + L
s = 2 * L + 1, t = 2 * L + 2;
for (int i = 1; i <= n; i++)
for (int j = 1; j < m + i; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= 3; i++) {
rebuild(i);
while (spfa()) update();
printf("%d
", ans);
}
return 0;
}
运输问题
题目链接。二分图最大权多重匹配问题。
建网络：
- (S Rightarrow a_i)，流量为 (a_i)，无费用
- (a_i Rightarrow b_j)，流量为无限（这个数只要大于 (a_i) 就行），费用为 (c_{i, j})
- (b_j Rightarrow T)，流量为 (b_j)，无费用
两次建图跑最小 / 最大费用最大流即可。
时间复杂度 (O(NMsqrt{N + M}))
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 105, L = N << 1, INF = 0x3f3f3f3f;
int m, n, s, t, a[N], b[N], c[N][N], dis[L], incf[L], pre[L], q[L];
int head[L], numE, ans;
bool vis[L];
struct E{
int next, v, w, c;
} e[(N * N + N * 2) * 2];
void add(int u, int v, int w, int c) {
e[++numE] = (E) { head[u], v, w, c };
head[u] = numE;
}
void addEdge(int u, int v, int w, int c) {
add(u, v, w, c); add(v, u, 0, -c);
}
bool spfa(int id) {
memset(dis, id == 1 ? 0x3f : 0xcf, sizeof dis);
int hh = 0, tt = 1;
dis[s] = 0, q[0] = s, incf[s] = INF;
while (hh != tt) {
int u = q[hh++]; vis[u] = false;
if (hh == L) hh = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
bool t = id == 1 ? dis[u] + e[i].c < dis[v] : dis[u] + e[i].c > dis[v];
if (e[i].w && t) {
dis[v] = dis[u] + e[i].c;
pre[v] = i, incf[v] = min(incf[u], e[i].w);
if (!vis[v]) {
vis[v] = true, q[tt++] = v;
if (tt == L) tt = 0;
}
}
}
}
return dis[t] != dis[0];
}
void update() {
int x = t;
while (x != s) {
int i = pre[x];
e[i].w -= incf[t], e[i ^ 1].w += incf[t];
x = e[i ^ 1].v;
}
ans += incf[t] * dis[t];
}
void work(int id) {
numE = 1, ans = 0;
memset(head, 0, sizeof head);
for (int i = 1; i <= m; i++) addEdge(s, i, a[i], 0);
for (int i = 1; i <= n; i++) addEdge(i + m, t, b[i], 0);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) addEdge(i, j + m, INF, c[i][j]);
while (spfa(id)) update();
printf("%d
", ans);
}
int main() {
scanf("%d%d", &m, &n);
s = m + n + 1, t = m + n + 2;
for (int i = 1; i <= m; i++) scanf("%d", a + i);
for (int i = 1; i <= n; i++) scanf("%d", b + i);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) scanf("%d", &c[i][j]);
work(1); work(2);
return 0;
}
分配问题
题目链接。KM 算法模板一练。（话说有返回值不返回就 (TLE) 的吗。。）
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 105, INF = 1e9;
int n, match[N], c[N][N], w[N][N], la[N], lb[N], upd[N];
bool va[N], vb[N];
bool find(int u) {
va[u] = true;
for (int v = 1; v <= n; v++) {
if (vb[v]) continue;
if (la[u] + lb[v] - w[u][v] == 0) {
vb[v] = true;
if (!match[v] || find(match[v])) {
match[v] = u; return true;
}
} else upd[v] = min(upd[v], la[u] + lb[v] - w[u][v]);
}
return false;
}
void KM() {
for (int i = 1; i <= n; i++) {
la[i] = -INF, lb[i] = 0, match[i] = 0;
for (int j = 1; j <= n; j++) la[i] = max(la[i], w[i][j]);
}
for (int i = 1; i <= n; i++) {
while (true) {
for (int j = 1; j <= n; j++) upd[j] = INF, va[j] = vb[j] = false;
if (find(i)) break;
int delta = INF;
for (int j = 1; j <= n; j++)
if (!vb[j]) delta = min(delta, upd[j]);
for (int j = 1; j <= n; j++) {
if (va[j]) la[j] -= delta;
if (vb[j]) lb[j] += delta;
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans += c[match[i]][i];
printf("%d
", ans);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) scanf("%d", &c[i][j]), w[i][j] = -c[i][j];
KM();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) w[i][j] = c[i][j];
KM();
return 0;
}
负载平衡问题
题目链接。$100% = $ 糖果传递弱化版 (=) 环形均分纸牌。
显然一定有两个仓库相邻之间没有传递（否则即形成了一个环，可以在环上所有边减去值会更优）。
枚举那个断点，设为 (k)，即 (k) 与 (k - 1) 之间没有传递。
然后就是贪心问题，把所有的值减去平均值以后，即相邻交换使每一个为 (0)。从左向右考虑每一个数，为了让他变成 (0)，他必须向相邻右侧的兄弟送走（正数） / 索取（负数），这种交换方式都是绝对值的，所以算一遍新数组的前缀和，即左边的一伙兄弟对当前这个小可爱的施压。
即代价为 (|s[k + 1] - s[k]| + ... + |s[n] - s[n - 1]| + |s[n] + s[1] - s[k]| + ... + |s[n] + s[k - 1] - s[k]|)，因为 (s[n] = 0)，所以即找 (min(sum_{i=1}^{n}s[k] -s[i]))，中位数，完事（这题数据很小，可以直接暴力）。
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 105;
int n, a[N], v = 0;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", a + i), v += a[i];
v /= n;
for (int i = 1; i <= n; i++) a[i] = a[i - 1] + a[i] - v;
sort(a + 1, a + 1 + n);
int ans = 0;
for (int i = 1; i <= n; i++) ans += abs(a[i] - a[(n + 1) >> 1]);
printf("%d
", ans);
return 0;
}
深海机器人问题
题目链接。看了好久看不懂题意棒棒
原来就是语文阅读题，按照题意建网络，跑最大费用最大流即可。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 20, L = N * N, INF = 0x3f3f3f3f;
int A, B, s, t, n, m, pre[L], q[L], dis[L], incf[L];
int head[L], numE = 1, ans;
bool vis[L];
struct E{
int next, v, w, c;
} e[30 + L * 8];
void add(int u, int v, int w, int c) {
e[++numE] = (E) { head[u], v, w, c };
head[u] = numE;
}
void addEdge(int u, int v, int w, int c) {
add(u, v, w, c); add(v, u, 0, -c);
}
bool spfa() {
memset(dis, 0xcf, sizeof dis);
int hh = 0, tt = 1;
q[0] = s, incf[s] = INF, dis[s] = 0;
while (hh != tt) {
int u = q[hh++]; vis[u] = false;
if (hh == L) hh = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w && dis[u] + e[i].c > dis[v]) {
dis[v] = dis[u] + e[i].c;
pre[v] = i, incf[v] = min(incf[u], e[i].w);
if (!vis[v]) {
vis[v] = true, q[tt++] = v;
if (tt == L) tt = 0;
}
}
}
}
return dis[t] != dis[0];
}
void update() {
int x = t;
while (x != s) {
int i = pre[x];
e[i].w -= incf[t], e[i ^ 1].w += incf[t];
x = e[i ^ 1].v;
}
ans += incf[t] * dis[t];
}
int get(int i, int j) {
return i * (m + 1) + j + 1;
}
int main() {
scanf("%d%d%d%d", &A, &B, &n, &m);
s = (n + 1) * (m + 1) + 1, t = (n + 1) * (m + 1) + 2;
for (int i = 0, x; i <= n; i++)
for (int j = 0; j < m; j++) {
scanf("%d", &x), addEdge(get(i, j), get(i, j + 1), 1, x);
addEdge(get(i, j), get(i, j + 1), INF, 0);
}
for (int j = 0, x; j <= m; j++)
for (int i = 0; i < n; i++) {
scanf("%d", &x), addEdge(get(i, j), get(i + 1, j), 1, x);
addEdge(get(i, j), get(i + 1, j), INF, 0);
}
for (int i = 1, k, x, y; i <= A; i++) {
scanf("%d%d%d", &k, &x, &y), addEdge(s, get(x, y), k, 0);
}
for (int i = 1, k, x, y; i <= B; i++) {
scanf("%d%d%d", &k, &x, &y), addEdge(get(x, y), t, k, 0);
}
while (spfa()) update();
printf("%d
", ans);
return 0;
}
最长k可重区间集问题
题目链接。不会做，题解看不懂，自闭了。
(k) 可重区间集 (Leftrightarrow) (k) 个内部不相交的区间集合。
自闭证明
右推左很简单，只需要把 (k) 个集合叠加起来，每个集合对一个点的贡献不超过 (1)，必然每个点最后不超过 (K)。
左推右比较难受，可以考虑构造一种方式，想了半天还是只会感性证明：
- 考虑现在已知 (k) 可重区间集，考虑转化为一个内部区间不相交的集合 (+ k - 1) 可重区间集：即选出一些互不相交的区间，然后把点上代价 (=K) 的去掉一层，对于一段连续的 (K)，显然它的组成也是连续严丝合缝的（否则不满足 (k) 可重区间集的性质）。
然后转化以后就会做了，注意离散化、端点相交不算重合，构建出网络，假设全局边界为 ([1, N])：
- (S Rightarrow 1) 流量为 (K)， 费用为 (0)
- (NRightarrow T)，流量为 (K)，费用为 (0)
- (i Rightarrow i + 1)，流量为 (inf)，费用为 (0)
- (l Rightarrow r)，流量为 (1)，费用为区间长度。
这样，考虑每一条流量为 (1) 的路径都是一个互不相交的区间的集合，并且我们设定了每个只能通过一次，所以此建图方式与所求等效，跑出最大费用最大流即答案。
时间复杂度：
点数 (N <= 1000)，边数 (M <= 3000)，(O(NM^2))，跑的真快（网络流不需要分析复杂度）
坑点
- 区间 ([l, r]) 长度定义：(r - l)
- 不一定保证 (l < r)，如果不行要翻转
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 505, S = N << 1, INF = 1e9;
int n, K, s, t, L[N], R[N], d[S], tot;
int dis[S], pre[S], q[S], incf[S], ans;
int head[S], numE = 1;
bool vis[S];
struct E{
int next, v, w, c;
} e[S * 3];
void add(int u, int v, int w, int c) {
e[++numE] = (E) { head[u], v, w, c };
head[u] = numE;
}
void addEdge(int u, int v, int w, int c) {
add(u, v, w, c); add(v, u, 0, -c);
}
bool spfa() {
memset(dis, 0xcf, sizeof dis);
int hh = 0, tt = 1;
q[0] = s, incf[s] = INF, dis[s] = 0;
while (hh != tt) {
int u = q[hh++]; vis[u] = false;
if (hh == S) hh = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w && dis[u] + e[i].c > dis[v]) {
dis[v] = dis[u] + e[i].c;
pre[v] = i, incf[v] = min(incf[u], e[i].w);
if (!vis[v]) {
vis[v] = true, q[tt++] = v;
if (tt == S) tt = 0;
}
}
}
}
return dis[t] != dis[0];
}
void update() {
int x = t;
while (x != s) {
int i = pre[x];
e[i].w -= incf[t], e[i ^ 1].w += incf[t];
x = e[i ^ 1].v;
}
ans += incf[t] * dis[t];
}
int get(int x) {
return lower_bound(d + 1, d + 1 + tot, x) - d;
}
int main() {
scanf("%d%d", &n, &K);
for (int i = 1; i <= n; i++) {
scanf("%d%d", L + i, R + i);
if (L[i] > R[i]) swap(L[i], R[i]);
d[++tot] = L[i], d[++tot] = R[i];
}
sort(d + 1, d + 1 + tot);
tot = unique(d + 1, d + 1 + tot) - d - 1;
s = tot + 1, t = tot + 2;
addEdge(s, 1, K, 0), addEdge(tot, t, K, 0);
for (int i = 1; i < tot; i++) addEdge(i, i + 1, INF, 0);
for (int i = 1; i <= n; i++) addEdge(get(L[i]), get(R[i]), 1, R[i] - L[i]);
while (spfa()) update();
printf("%d
", ans);
}
最长k可重线段集问题
题目链接。与上一道题类似，一段线段的 ([x_0, y_1]) 可以看做一维意义下的一段区间。但是要注意线段垂直于 ( ext{X}) 轴的情况，若按照正常建边会导致正权自环（且 SPFA 最长路），所以会炸掉，所以考虑特判，可以把每个点拆成一个入点一个出点进行连接即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 505, S = N << 2, INF = 1e9;
int n, K, s, t, w[N], L[N], R[N], d[S], tot;
int dis[S], pre[S], q[S], incf[S], ans;
int head[S], numE = 1;
bool vis[S];
struct E{
int next, v, w, c;
} e[S * 5];
void add(int u, int v, int w, int c) {
e[++numE] = (E) { head[u], v, w, c };
head[u] = numE;
}
void addEdge(int u, int v, int w, int c) {
add(u, v, w, c); add(v, u, 0, -c);
}
bool spfa() {
memset(dis, 0xcf, sizeof dis);
int hh = 0, tt = 1;
q[0] = s, incf[s] = INF, dis[s] = 0;
while (hh != tt) {
int u = q[hh++]; vis[u] = false;
if (hh == S) hh = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w && dis[u] + e[i].c > dis[v]) {
dis[v] = dis[u] + e[i].c;
pre[v] = i, incf[v] = min(incf[u], e[i].w);
if (!vis[v]) {
vis[v] = true, q[tt++] = v;
if (tt == S) tt = 0;
}
}
}
}
return dis[t] != dis[0];
}
void update() {
int x = t;
while (x != s) {
int i = pre[x];
e[i].w -= incf[t], e[i ^ 1].w += incf[t];
x = e[i ^ 1].v;
}
ans += incf[t] * dis[t];
}
int get(int x) {
return lower_bound(d + 1, d + 1 + tot, x) - d;
}
int main() {
scanf("%d%d", &n, &K);
for (int i = 1, p, q; i <= n; i++) {
scanf("%d%d%d%d", L + i, &p, R + i, &q);
if (L[i] > R[i]) swap(L[i], R[i]);
d[++tot] = L[i], d[++tot] = R[i];
w[i] = sqrt(((LL)R[i] - L[i]) * (R[i] - L[i]) + ((LL)p - q) * (p - q));
}
sort(d + 1, d + 1 + tot);
tot = unique(d + 1, d + 1 + tot) - d - 1;
s = tot * 2 + 1, t = tot * 2 + 2;
addEdge(s, 1, K, 0), addEdge(tot * 2, t, K, 0);
for (int i = 1; i <= tot; i++) addEdge(i, i + tot, INF, 0);
for (int i = 1; i < tot; i++) addEdge(i + tot, i + 1, INF, 0);
for (int i = 1; i <= n; i++) {
if (L[i] == R[i]) addEdge(get(L[i]), get(R[i]) + tot, 1, w[i]);
else addEdge(get(L[i]) + tot, get(R[i]), 1, w[i]);
}
while (spfa()) update();
printf("%d
", ans);
}
火星探险问题
题目链接。这题 (approx) (K) 取方格数，建图比较显然：
- 为了强行加上费用，套路拆点
- 第一次收集石头（仅对石头有效）：入点 (Rightarrow) 出点连边，流量费用都为 (1)
- 经过无费用：入点 (Rightarrow) 出点连边，流量无限，费用为 (0)
- 移动（仅当下一个无障碍），一个位置出点向下、右的位置对应入点连边，流量无限，费用为 (0)
从 ((1, 1)) 入点作为源点， ((n, m)) 出点作为汇点，跑最大费用最大流即可
唯一不同的就是输出方案，循环 (n) 次每一次找一条流量为 (1) 的路径，网络流的反向边即流过的流量，DFS + BREAK 即可时间复杂度 (O(npq)) 很够。
需要注意的是找路径的时候必须保证 (x, y) 递增的，否则可能往回跑，就不符合路径的约定了。
#include <cstdio>
#include <iostream>
#include <cstring>
#define num(i, j, k) ((i - 1) * m + j + k * m * n)
using namespace std;
typedef pair<int, int> PII;
const int N = 40, L = N * N * 2, INF = 1e9;
int n, m, K, g[N][N], s, t, ans, q[L], d[L], incf[L], pre[L];
bool vis[L];
int head[L], numE = 1;
PII o[L];
struct E{
int next, v, w, c, d;
} e[L * 8];
void inline add(int u, int v, int w, int c, int d) {
e[++numE] = (E) { head[u], v, w, c, d };
head[u] = numE;
}
void inline addEdge(int u, int v, int w, int c, int d) {
add(u, v, w, c, d); add(v, u, 0, -c, d);
}
bool spfa() {
memset(d, 0xcf, sizeof d);
memset(vis, false, sizeof vis);
int hh = 0, tt = 1;
q[0] = s, d[s] = 0, incf[s] = INF;
while (hh != tt) {
int u = q[hh++]; vis[u] = false;
if (hh == L) hh = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w && d[u] + e[i].c > d[v]) {
d[v] = d[u] + e[i].c;
pre[v] = i;
incf[v] = min(incf[u], e[i].w);
if (!vis[v]) {
vis[v] = true, q[tt++] = v;
if (tt == L) tt = 0;
}
}
}
}
return d[t] != 0xcfcfcfcf;
}
void update() {
int x = t;
while (x != s) {
int i = pre[x];
e[i].w -= incf[t], e[i ^ 1].w += incf[t];
x = e[i ^ 1].v;
}
ans += incf[t] * d[t];
}
void dfs(int u, int id) {
vis[u] = true;
int x = o[u].first, y = o[u].second;
if (u == t) return;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
int nx = o[v].first, ny = o[v].second;
if (!vis[v] && e[i ^ 1].w && x <= nx && y <= ny) {
if (e[i ^ 1].d != -1) printf("%d %d
", id, e[i ^ 1].d);
e[i ^ 1].w --;
dfs(v, id);
break;
}
}
}
int main() {
scanf("%d%d%d", &K, &m, &n);
s = m * n * 2 + 1, t = m * n * 2 + 2;
addEdge(s, num(1, 1, 0), K, 0, -1); addEdge(num(n, m, 1), t, K, 0, -1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
o[num(i, j, 0)] = o[num(i, j, 1)] = make_pair(i, j);
scanf("%d", &g[i][j]);
addEdge(num(i, j, 0), num(i, j, 1), INF, 0, -1);
if (g[i][j] == 2) addEdge(num(i, j, 0), num(i, j, 1), 1, 1, -1);
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (i < n && g[i + 1][j] != 1) addEdge(num(i, j, 1), num(i + 1, j, 0), INF, 0, 0);
if (j < m && g[i][j + 1] != 1) addEdge(num(i, j, 1), num(i, j + 1, 0), INF, 0, 1);
}
while (spfa()) update();
for (int i = 1; i <= K; i++) {
memset(vis, false, sizeof vis);
dfs(s, i);
}
return 0;
}
骑士共存问题
显然把每个位置当做一个节点，矛盾的（即日字的对角）连边，构成一个二分图（横纵坐标之和的奇偶性染色显然为二分图），要求最大独立集。随便证一下，就是去掉最少的点，让剩下的点之间没有边。所以用最少的点覆盖所有的边 (=) 最小点覆盖 (=) 最大匹配数。所以最大独立集 (=) 总数 (-) 最大匹配数。
二分图最大匹配可以用匈牙利，虽然时间复杂度玄学，鬼知道为什么奇数作为左边跑 (AC)，反过来 TLE。
#include <cstdio>
#include <iostream>
#include <cstring>
#define rint register int
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 205;
int n, T, ans;
bool g[N][N];
PII match[N][N];
bool st[N][N];
int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[8] = {-2, 2, 2, -2, 1, -1, 1, -1};
bool find(int x, int y) {
for (rint i = 0; i < 8; i++) {
int nx = x + dx[i], ny = y + dy[i];
if(nx < 1 || nx > n || ny < 1 || ny > n || g[nx][ny] || st[nx][ny]) continue;
st[nx][ny] = true;
PII v = match[nx][ny];
if(!v.x || find(v.x, v.y)) {
match[nx][ny] = make_pair(x, y);
return true;
}
}
return false;
}
int main() {
scanf("%d%d", &n, &T);
for (rint i = 1; i <= T; i++) {
int x, y; scanf("%d%d", &x, &y);
g[x][y] = true;
}
for (rint i = 1; i <= n; i++)
for (rint j = 1; j <= n; j++) {
if((i + j) % 2 == 0 || g[i][j]) continue;
memset(st, 0, sizeof st);
if (find(i, j)) ans++;
}
printf("%d
", n * n - T - ans);
return 0;
}