[心之碎片] - 图论建模
本帖最后由 柿子饼同学 于 2024-8-30 13:00 编辑包括
网络流初步, 差分约束, 同余最短路, Kruskal重构树
最大流板子都是一样的, 关键在于建模和连边, 限制比较多并且问你匹配的时候要想到
拆点是按照状态来拆的, 例如不同时间的门...
建图要按照如何解决问题来建, 不同的行为可以抽象成连边放进图
差分约束解决一些不等式问题, 求最短路意味着 a b 之间的差值最大为多少... 来判断可行性唯一性之类的
同余最短路解决构成问题, 选取一个最小的数字, 按照她取模分类, 跑最短路可以得到一系列最小的模她为定值的数字
遇到图上路径最大值不超过/不小于之类问题要想到重构树图论注意连通性
网络流 Dinic 算法板子 + 前向星:
int st, ed;
struct Graph {
struct Edge {
int v, cap, nxt;
} e;
int tot, H;
Graph() {
memset(H, -1, sizeof(H));
tot = 0;
}
void Add(int u, int v, int w) {
e = { v, w, H };
H = tot++;
e = { u, 0, H };
H = tot++;
}
} g;
struct Max_Flow {
int dep, cur;
bool bfs() {
queue<int> q;
memset(dep, 0, sizeof(int) * (ed + 1));
dep = 1;
q.emplace(st);
while (!q.empty()) {
int u = q.front(), v, c;
q.pop();
for (int i = g.H; ~i; i = g.e.nxt) {
v = g.e.v, c = g.e.cap;
if (c && !dep) {
dep = dep + 1;
q.emplace(v);
}
}
}
return dep;
}
int dfs(int u, int mf) {
if (u == ed || !mf)
return mf;
int v, c, d;
for (int& i = cur; ~i; i = g.e.nxt) {
v = g.e.v, c = g.e.cap;
if (dep == dep + 1 && c) {
if (d = dfs(v, min(mf, c))) {
g.e.cap -= d;
g.e.cap += d;
return d;
}
}
}
return 0;
}
int Dinic() {
int res = 0, flow;
while (bfs()) {
for (int i = 0; i <= ed; i++) {
cur = g.H;
}
while (1) {
flow = dfs(st, INT_MAX);
if (!flow)
break;
res += flow;
}
}
return res;
}
} mf;
B - 圆桌问题
把每个单位向各个桌子连一道流量为1的边
由源点向每个单位连上 连上单位人数的边
由每个圆桌向汇点连上 圆桌人数的边
然后跑一下最大匹配 如果最大匹配数等于所有单位的人数和
C - 发抖的牛
二分时间, 连边
D - dining
注意每个牛只能吃一种食物饮料, 所以需要把每头牛拆成两个点, 中间连权值为 1 的边
E - 紧急疏散
二分时间, 把门拆成每个时间的门,
bfs 预处理每个人到每个门的时间, 二分之后建图就把人到门建边, 但是如何解决很多人同时进门?
我们把每个门向她的 时间+1 的门连一个 inf 流量的边, 就表示如果当前时间有人进门了, 同时来到门前的人需要顺位进入下一个时间的门
差分约束系统
F - 狡猾的商人
带权并查集维护区间和, 每次询问 s - s
H - FES
首先连边, 她问的唯一, 考虑 scc 中才具有唯一性, 不同 scc 只有大小关系
所以缩点然后跑最长路, 求出这个 scc 中的最小差值,
因为只可以 相等或 >= 1, 所以这个差值就是取值范围
每个 scc 这样搞就行了
I - 天平
求出两个砝码最大最小差多少, 然后按照不等式把和柿改成差判断就行
注意只需要满足一对即可
同余最短路
J - 等式
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
const int M = 14;
// 同余最短路
// 假设 mn 是 a[] 中的一个, 如果一个数字 x 能被表示出来, 那么 y = (x + mn*k) 也可以被表示出来
// 而 x = y (mod mn)
// 用 dis 表示最小的 x 使得 x % mn = i, i 属于
// 跑最短路, 起点是 0 保证 x 一定能被表示出来
// i 向 i + a 连边, 边权是 a
// 然后算答案就行了
struct Edge {
ll v, w;
Edge(ll x, ll y) { v = x, w = y; }
};
int n;
ll l, r, a, mn = 1e9;
// spfa
vector<Edge> g;
ll dis;
bitset<N> vis;
void Spfa() {
memset(dis, 0x3f, sizeof(dis));
queue<int> q;
dis = 0;
q.emplace(0);
while (!q.empty()) {
auto u = q.front();
q.pop();
vis = 0;
for (auto y : g) {
auto v = y.v, w = y.w;
if (dis > dis + w) {
dis = dis + w;
if (vis)
continue;
vis = 1;
q.emplace(v);
}
}
}
}
ll Query(ll x) {
ll res = 0;
for (int i = 0; i < mn; i++) {
if (dis > x)
continue;
res += (x - dis) / mn + 1;
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> l >> r;
for (int i = 1; i <= n; i++) {
cin >> a;
// 可能有 0, 跳过
if (a)
mn = min(mn, a);
}
for (int i = 0; i < mn; i++) {
for (int j = 1; j <= n; j++) {
if (!a || a == mn)
continue;
g.emplace_back((i + a) % mn, a);
}
}
Spfa();
cout << Query(r) - Query(l - 1);
return 0;
}
Kruskal 重构树
求最小/最大生成树的时候合并边上的两个点, 新建一个点, 权值是边权, 连向这两个点
最后形成了二叉树, 就可以套用树上问题做了
注意连通性
K - 货车运输
最大生成树 或者 重构树求 lca
还有一些奇妙的解法:
跟第一种写法差不多，只不过构建最大生成树时我们不路径压缩，用按秩合并的方法，把深度小的点合并到大的点上面。
注意了，此时连边并不是把两个点直接连边，而是把它们的祖先连边（边权还是一样）。
可以证明：因为我们是按边从大到小加的，而要查询路径上的边权最小值。
此时，这条边把两个集合合并在了一起，那么一个集合到另一个集合必定要经过这条边，而这条边又是目前最小的（其它边可以不管了），所以我们只用确保路径经过了这条边即可。
按照这样构成的生成树深度最多只有log(n)，因此找路径暴力遍历即可。
L - 删边
给一个图, 每次询问 k 个点, 求最小的 x 使得小于等于 x 的边删掉之后 k 个点互相不连通
建生成树, 把 k 个点按照 dfn 排序, 每次求相邻点的 lca 取 min 即可
我去。。。只看懂了一个链式前向星。。。
本帖最后由 柿子饼同学 于 2024-8-30 13:00 编辑
学习编程中的Ben 发表于 2024-8-30 12:31
我去。。。只看懂了一个链式前向星。。。
基本都是提高组的 柿子饼同学 发表于 2024-8-30 12:59
基本都是提高组的
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
老了，跟不上时代的节奏了{:10_266:} 小小问一下，你为啥要专门来发这些帖子，真正看得人很少，编辑帖子也很麻烦 学习编程中的Ben 发表于 2024-8-30 14:17
小小问一下，你为啥要专门来发这些帖子，真正看得人很少，编辑帖子也很麻烦
相当于一个错题本的作用, 时不时回来看看复习总结 柿子饼同学 发表于 2024-8-30 16:41
相当于一个错题本的作用, 时不时回来看看复习总结
orz!!! {:10_256:}{:10_256:} {:7_113:} 看看{:10_254:} 谢谢 没币解锁课后作业了 {:10_254:}{:10_254:}{:10_254:}{:10_254:}{:10_254:}{:10_254:}
页:
[1]