gym-101667E How Many to Be Happy
2022/8/30 23:24:15
本文主要是介绍gym-101667E How Many to Be Happy,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
How Many to Be Happy?
最小割
因为是最小生成树,因此可以考虑对于一条边来说,他的左右两端的点视为处于两个不同的集合,然后只通过该边进行连接,这样最小生成树就必然会利用这条边
比该边大的边显然不用考虑,就考虑比该边边权小的边,然后进行最小割,边流量为 \(1\)(分割成两个集合,且割的边数最少)
#include <iostream> #include <cstdio> #include <vector> #include <array> #include <algorithm> #include <queue> using namespace std; typedef long long ll; const int maxn = 2e4 + 10; const int inf = 1e8; int head[maxn], nexx[maxn], to[maxn], vol[maxn], vp = 1; int dep[maxn], cur[maxn], n, m, s, t; inline void add(int u, int v, int t) { vp++; nexx[vp] = head[u]; to[vp] = v; vol[vp] = t; head[u] = vp; } bool bfs() { queue<int>q; q.push(s); for(int i=0; i<=n; i++) cur[i] = head[i]; for(int i=0; i<=n; i++) dep[i] = 0; dep[s] = 1; while(q.size()) { int now = q.front(); q.pop(); for(int i=head[now]; i; i=nexx[i]) { int nex = to[i]; if(dep[nex] == 0 && vol[i] > 0) { dep[nex] = dep[now] + 1; q.push(nex); } } } return dep[t]; } int dfs(int now, int flow = inf) { if(now == t) return flow; int ans = 0; for(int i=head[now]; i && flow; i=nexx[i]) { int nex = to[i]; if(dep[nex] == dep[now] + 1 && vol[i]) { int f = dfs(nex, min(flow, vol[i])); vol[i] -= f; vol[i ^ 1] += f; ans += f; flow -= f; } } return ans; } int dinic() { int ans = 0; while(bfs()) ans += dfs(s); return ans; } int main() { cin >> n >> m; vector<array<int, 3> >num(m); for(int i=0; i<m; i++) { int a, b, c; cin >> a >> b >> c; num[i] = {c, a, b}; } sort(num.begin(), num.end()); ll ans = 0; for(auto [c, a, b] : num) { for(int i=0; i<=n; i++) head[i] = 0; vp = 1; for(auto [cc, aa, bb] : num) { if(cc >= c) break; add(aa, bb, 1); add(bb, aa, 0); add(bb, aa, 1); add(aa, bb, 0); } s = a; t = b; ans += dinic(); } cout << ans << endl; return 0; }
这篇关于gym-101667E How Many to Be Happy的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行
- 2024-05-08阿里云域名注册流程,分享给第一次购买域名的新手站长!
- 2024-05-082024年,行业变动下的程序员应该首先学习哪种编程语言?