闲话
啊啊啊数数题的式子和含义怎么也对不上啊啊啊
有好心人给我具体讲讲他在说啥吗？
感觉最近这两天的闲话比较低质量
在我啃明白这个前不是很可能高质量（
对了顺便问个（可能很sb）的问题
为啥这要乘 \((i-1)!\) 啊
翻旧闲话好像看到 CF1515E 能代数工业 \(O(n\log n)\)？
求大佬浇浇
杂题
星际竞速
感觉这题挺刻意的。
每个星球恰好经过一次：拆出入点，点间连边 \(1\) 流量，\(0\) 费用
空间跳跃：源点跳跃到每个星球流量是 \(1\)，费用是跳跃的费用，每个星球都能直接跳到汇点，费用是 \(0\)。
高速航行：直接连边就行。
建完边跑最小费用最大流即可。
挺板的一题的。注意 \(u < v\)，要不然你连样例都过不去。
code
int M, s, t, n, m, t1, t2, t3, t4;
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
M = n * 2;
s = ++ M, t = ++ M;
rep(i,1,n) cin >> t1, adde(s, (i << 1) - 1, 1, t1);
rep(i,1,n) adde(s, (i << 1), 1, 0), adde((i << 1) - 1, t, 1, 0);
rep(i,1,m) {
cin >> t1 >> t2 >> t3; if (t1 > t2) swap(t1, t2);
adde(t1 << 1, (t2 << 1) - 1, 1, t3);
}
Dinic(s, t);
cout << min_cost << '\n';
}
狼抓兔子
一眼最小割模型。但是数据加强一点你的多路增广 Dinic 就过不去了。因此考虑最小割的含义。
这是个平面图，因此最小割退化，我们可以用一条曲线穿过极多的最小割对应边的中点，这条曲线将整张图分为两部分。同样的，这条曲线是从左下到右上穿过平面图时所穿过的边权的最小值。这让我们想到最短路。
引入对偶图概念。我们将图上每个面构成一个点，点间的边是原图的边顺时针旋转 \(90°\) 得到的边。以左下角和右上角的无限大平面为源汇点，我们跑最短路就能得到答案。
听说很恶心？所以没实现。海拔我写了。
志愿者招募
挺好玩的一道题欸。
费用流比较一眼。然后我们 \(s\to 1\to 2\to \cdots\to n+1\to t\) 顺次连起来，\(i\to i+1\) 连 \(\inf - a_i\) 流，\(0\) 费用的边，起点终点都连 \(\inf\) 流 \(0\) 费的边。
然后是招人。招人 \([l,r,w]\) 就 \(l\to r\) 连 \(\inf\) 流 \(w\) 费的边。
看懂为啥都要连边权那么大的边了吗？最大流所以肯定 \(\inf\) 是要跑满的，但是想不花钱跑到 \(\inf\) 是不可能的，这就转化成了经典费用流了，正确性显然。
“但这并不是我的特长！”
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
int M, s, t, n, m, t1, t2, t3, t4;
const int N = 1e6, inf = 1e18;
signed main() {
cin >> n >> m;
M = n + 1; s = ++ M, t = ++ M;
adde(s, 1, inf, 0);
rep(i,1,n) cin >> t1, adde(i, i + 1, inf - t1, 0);
adde(n + 1, t, inf, 0);
rep(i,1,m) cin >> t1 >> t2 >> t3, adde(t1, t2 + 1, inf, t3);
Dinic(s, t);
cout << min_cost << endl;
}