闲话
啊啊啊数数题的式子和含义怎么也对不上啊啊啊
有好心人给我具体讲讲他在说啥吗?
感觉最近这两天的闲话比较低质量
在我啃明白这个前不是很可能高质量(
对了顺便问个(可能很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;
}