鱼C论坛

 找回密码
 立即注册
查看: 2493|回复: 12

[心之碎片] - 图论建模

[复制链接]
回帖奖励 9 鱼币 回复本帖可获得 3 鱼币奖励! 每人限 1 次
发表于 2024-8-30 11:39:48 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 柿子饼同学 于 2024-8-30 13:00 编辑
包括
网络流初步, 差分约束, 同余最短路, Kruskal重构树


最大流板子都是一样的, 关键在于建模和连边, 限制比较多并且问你匹配的时候要想到
拆点是按照状态来拆的, 例如不同时间的门...
建图要按照如何解决问题来建, 不同的行为可以抽象成连边放进图
差分约束解决一些不等式问题, 求最短路意味着 a b 之间的差值最大为多少... 来判断可行性唯一性之类的
同余最短路解决构成问题, 选取一个最小的数字, 按照她取模分类, 跑最短路可以得到一系列最小的模她为定值的数字
遇到图上路径最大值不超过/不小于之类问题要想到重构树
图论注意连通性

网络流 Dinic 算法板子 + 前向星:
  1. int st, ed;

  2. struct Graph {
  3.     struct Edge {
  4.         int v, cap, nxt;
  5.     } e[K];
  6.     int tot, H[M];

  7.     Graph() {
  8.         memset(H, -1, sizeof(H));
  9.         tot = 0;
  10.     }

  11.     void Add(int u, int v, int w) {
  12.         e[tot] = { v, w, H[u] };
  13.         H[u] = tot++;
  14.         e[tot] = { u, 0, H[v] };
  15.         H[v] = tot++;
  16.     }
  17. } g;

  18. struct Max_Flow {
  19.     int dep[M], cur[M];

  20.     bool bfs() {
  21.         queue<int> q;
  22.         memset(dep, 0, sizeof(int) * (ed + 1));

  23.         dep[st] = 1;
  24.         q.emplace(st);

  25.         while (!q.empty()) {
  26.             int u = q.front(), v, c;
  27.             q.pop();

  28.             for (int i = g.H[u]; ~i; i = g.e[i].nxt) {
  29.                 v = g.e[i].v, c = g.e[i].cap;
  30.                 if (c && !dep[v]) {
  31.                     dep[v] = dep[u] + 1;
  32.                     q.emplace(v);
  33.                 }
  34.             }
  35.         }

  36.         return dep[ed];
  37.     }

  38.     int dfs(int u, int mf) {
  39.         if (u == ed || !mf)
  40.             return mf;

  41.         int v, c, d;
  42.         for (int& i = cur[u]; ~i; i = g.e[i].nxt) {
  43.             v = g.e[i].v, c = g.e[i].cap;

  44.             if (dep[v] == dep[u] + 1 && c) {
  45.                 if (d = dfs(v, min(mf, c))) {
  46.                     g.e[i].cap -= d;
  47.                     g.e[i ^ 1].cap += d;

  48.                     return d;
  49.                 }
  50.             }
  51.         }

  52.         return 0;
  53.     }

  54.     int Dinic() {
  55.         int res = 0, flow;
  56.         while (bfs()) {
  57.             for (int i = 0; i <= ed; i++) {
  58.                 cur[i] = g.H[i];
  59.             }

  60.             while (1) {
  61.                 flow = dfs(st, INT_MAX);
  62.                 if (!flow)
  63.                     break;
  64.                 res += flow;
  65.             }
  66.         }

  67.         return res;
  68.     }
  69. } mf;
复制代码


B - 圆桌问题
把每个单位向各个桌子连一道流量为1的边
由源点向每个单位连上 连上单位人数的边
由每个圆桌向汇点连上 圆桌人数的边
然后跑一下最大匹配 如果最大匹配数等于所有单位的人数和


C - 发抖的牛
二分时间, 连边

D - dining
注意每个牛只能吃一种食物饮料, 所以需要把每头牛拆成两个点, 中间连权值为 1 的边

E - 紧急疏散
二分时间, 把门拆成每个时间的门,
bfs 预处理每个人到每个门的时间, 二分之后建图就把人到门建边, 但是如何解决很多人同时进门?
我们把每个门向她的 时间+1 的门连一个 inf 流量的边, 就表示如果当前时间有人进门了, 同时来到门前的人需要顺位进入下一个时间的门


差分约束系统
F - 狡猾的商人
带权并查集维护区间和, 每次询问 s[r] - s[l - 1]

H - FES
首先连边, 她问的唯一, 考虑 scc 中才具有唯一性, 不同 scc 只有大小关系
所以缩点然后跑最长路, 求出这个 scc 中的最小差值,
因为只可以 相等或 >= 1, 所以这个差值就是取值范围
每个 scc 这样搞就行了


I - 天平
求出两个砝码最大最小差多少, 然后按照不等式把和柿改成差判断就行
注意只需要满足一对即可


同余最短路
J - 等式
  1. #include <bits/stdc++.h>
  2. using namespace std;

  3. typedef long long ll;

  4. const int N = 5e5 + 5;
  5. const int M = 14;

  6. // 同余最短路
  7. // 假设 mn 是 a[] 中的一个, 如果一个数字 x 能被表示出来, 那么 y = (x + mn*k) 也可以被表示出来
  8. // 而 x = y (mod mn)
  9. // 用 dis[i] 表示最小的 x 使得 x % mn = i, i 属于 [0, mn - 1]
  10. // 跑最短路, 起点是 0 保证 x 一定能被表示出来
  11. // i 向 i + a[j] 连边, 边权是 a[j]
  12. // 然后算答案就行了

  13. struct Edge {
  14.     ll v, w;

  15.     Edge(ll x, ll y) { v = x, w = y; }
  16. };

  17. int n;
  18. ll l, r, a[M], mn = 1e9;

  19. // spfa
  20. vector<Edge> g[N];
  21. ll dis[N];
  22. bitset<N> vis;

  23. void Spfa() {
  24.     memset(dis, 0x3f, sizeof(dis));
  25.     queue<int> q;

  26.     dis[0] = 0;
  27.     q.emplace(0);

  28.     while (!q.empty()) {
  29.         auto u = q.front();
  30.         q.pop();

  31.         vis[u] = 0;

  32.         for (auto y : g[u]) {
  33.             auto v = y.v, w = y.w;

  34.             if (dis[v] > dis[u] + w) {
  35.                 dis[v] = dis[u] + w;

  36.                 if (vis[v])
  37.                     continue;
  38.                 vis[v] = 1;
  39.                 q.emplace(v);
  40.             }
  41.         }
  42.     }
  43. }

  44. ll Query(ll x) {
  45.     ll res = 0;

  46.     for (int i = 0; i < mn; i++) {
  47.         if (dis[i] > x)
  48.             continue;
  49.         res += (x - dis[i]) / mn + 1;
  50.     }

  51.     return res;
  52. }

  53. int main() {
  54.     ios::sync_with_stdio(0);
  55.     cin.tie(0);

  56.     cin >> n >> l >> r;
  57.     for (int i = 1; i <= n; i++) {
  58.         cin >> a[i];

  59.         // 可能有 0, 跳过
  60.         if (a[i])
  61.             mn = min(mn, a[i]);
  62.     }

  63.     for (int i = 0; i < mn; i++) {
  64.         for (int j = 1; j <= n; j++) {
  65.             if (!a[j] || a[j] == mn)
  66.                 continue;

  67.             g[i].emplace_back((i + a[j]) % mn, a[j]);
  68.         }
  69.     }

  70.     Spfa();

  71.     cout << Query(r) - Query(l - 1);

  72.     return 0;
  73. }
复制代码


Kruskal 重构树
求最小/最大生成树的时候合并边上的两个点, 新建一个点, 权值是边权, 连向这两个点
最后形成了二叉树, 就可以套用树上问题做了
注意连通性


K - 货车运输
最大生成树 或者 重构树求 lca
还有一些奇妙的解法:
跟第一种写法差不多,只不过构建最大生成树时我们不路径压缩,用按秩合并的方法,把深度小的点合并到大的点上面。
注意了,此时连边并不是把两个点直接连边,而是把它们的祖先连边(边权还是一样)。
可以证明:因为我们是按边从大到小加的,而要查询路径上的边权最小值。
此时,这条边把两个集合合并在了一起,那么一个集合到另一个集合必定要经过这条边,而这条边又是目前最小的(其它边可以不管了),所以我们只用确保路径经过了这条边即可。
按照这样构成的生成树深度最多只有log(n),因此找路径暴力遍历即可。


L - 删边
给一个图, 每次询问 k 个点, 求最小的 x 使得小于等于 x 的边删掉之后 k 个点互相不连通

建生成树, 把 k 个点按照 dfn 排序, 每次求相邻点的 lca 取 min 即可

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-8-30 12:31:49 | 显示全部楼层

回帖奖励 +3 鱼币

我去。。。只看懂了一个链式前向星。。。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2024-8-30 12:59:00 | 显示全部楼层
本帖最后由 柿子饼同学 于 2024-8-30 13:00 编辑
学习编程中的Ben 发表于 2024-8-30 12:31
我去。。。只看懂了一个链式前向星。。。


基本都是提高组的
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-30 14:13:20 | 显示全部楼层

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
老了,跟不上时代的节奏了
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-30 14:17:18 | 显示全部楼层
小小问一下,你为啥要专门来发这些帖子,真正看得人很少,编辑帖子也很麻烦
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2024-8-30 16:41:51 | 显示全部楼层
学习编程中的Ben 发表于 2024-8-30 14:17
小小问一下,你为啥要专门来发这些帖子,真正看得人很少,编辑帖子也很麻烦

相当于一个错题本的作用, 时不时回来看看复习总结
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-31 09:56:54 | 显示全部楼层
柿子饼同学 发表于 2024-8-30 16:41
相当于一个错题本的作用, 时不时回来看看复习总结

orz!!!
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-31 16:34:32 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-9-1 09:33:18 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-9-1 09:41:23 | 显示全部楼层

回帖奖励 +3 鱼币

看看
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-9-4 17:42:57 | 显示全部楼层

回帖奖励 +3 鱼币

谢谢
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-9-8 20:22:51 | 显示全部楼层

回帖奖励 +3 鱼币

没币解锁课后作业了
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-10-7 22:53:34 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-4-27 17:15

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表