Mincut 最小割 (BZOJ1797+最小割+tarjan)

阳光穿透心脏的1/2处 2021-11-01 03:32 345阅读 0赞

# 题目链接 #

[传送门][Link 1]

# 思路 #

根据题目给定的边跑一边最大流，然后再在残留网络上跑\\(tarjan\\)。

对于每一条边有：

*  如果它是非满边，那么它一定不是最小割集里面的边；
 *  如果\\(c\[u\[i\]\] \\not= c\[v\[i\]\]\\)，那么它可以是最小割集里面的边；
 *  如果\\(c\[u\[i\]\] \\not= c\[v\[i\]\]\\)且\\(c\[u\[i\]\]=c\[s\],c\[v\[i\]=c\[t\]\]\\)，那么它一定是最小割集里面的边。

详情可以看[\\(hzwer\\)][hzwer]大佬的解释。

# 代码实现如下 #

#include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; typedef pair<LL, LL> pLL; typedef pair<LL, int> pLi; typedef pair<int, LL> pil;; typedef pair<int, int> pii; typedef unsigned long long uLL; #define lson rt<<1 #define rson rt<<1|1 #define lowbit(x) x&(-x) #define name2str(name) (#name) #define bug printf("*********\n") #define debug(x) cout<<#x"=["<<x<<"]" <<endl #define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin) #define IO ios::sync_with_stdio(false),cin.tie(0) const double eps = 1e-8; const int mod = 1000000007; const int maxn = 4000 + 7; const double pi = acos(-1); const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3fLL; int n, m, top, num, cnt, u, v, w; int dfn[maxn], low[maxn], stc[maxn], vis[maxn], c[maxn]; struct Dinic { queue<int> q; int maxflow, tot, s, t; int head[maxn], d[maxn]; void init() { tot = maxflow = 0; memset(head, -1, sizeof(head)); } struct edge { int u, v, w, next; }ed[220007]; void add(int u, int v, int w) { ed[tot].u = u; ed[tot].v = v; ed[tot].w = w; ed[tot].next = head[u]; head[u] = tot++; ed[tot].u = v; ed[tot].v = u; ed[tot].w = 0; ed[tot].next = head[v]; head[v] = tot++; } bool bfs() { memset(d, 0, sizeof(d)); d[s] = 1; while(!q.empty()) q.pop(); q.push(s); int x; while(!q.empty()) { x = q.front(); q.pop(); for(int i = head[x]; ~i; i = ed[i].next) { if(ed[i].w && !d[ed[i].v]) { d[ed[i].v] = d[x] + 1; q.push(ed[i].v); if(ed[i].v == t) return 1; } } } return 0; } int dinic(int x, int flow) { if(x == t) return flow; int res = flow, k, v; for(int i = head[x]; ~i && res; i = ed[i].next) { v = ed[i].v; if(ed[i].w && d[v] == d[x] + 1) { k = dinic(v, min(res, ed[i].w)); if(!k) d[v] = 0; ed[i].w -= k; ed[i^1].w += k; res -= k; } } return flow - res; } int work() { int flow = 0; while(bfs()) { while(flow = dinic(s, inf)) maxflow += flow; } return maxflow; } }f; void tarjan(int u) { dfn[u] = low[u] = ++num; vis[u] = 1, stc[++top] = u; int v; for(int i = f.head[u]; ~i; i = f.ed[i].next) { if(f.ed[i].w == 0) continue; v = f.ed[i].v; if(!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if(vis[v]) { low[u] = min(low[u], low[v]); } } if(dfn[u] == low[u]) { cnt++; do { v = stc[top--]; vis[v] = 0; c[v] = cnt; }while(u != v); } } int main() { #ifndef ONLINE_JUDGE FIN; #endif scanf("%d%d%d%d", &n, &m, &f.s, &f.t); f.init(); for(int i = 1; i <= m; ++i) { scanf("%d%d%d", &u, &v, &w); f.add(u, v, w); } f.work(); for(int i = 1; i <= n; ++i) { if(!dfn[i]) tarjan(i); } for(int i = 0; i < f.tot; i += 2) { if(f.ed[i].w) { printf("0 0\n"); continue; } int u = f.ed[i].u, v = f.ed[i].v; if(c[u] != c[v]) printf("1 "); else printf("0 "); if(c[u] == c[f.s] && c[v] == c[f.t]) printf("1\n"); else printf("0\n"); } return 0; }

转载于:https://www.cnblogs.com/Dillonh/p/11236173.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=1797
[hzwer]: http://hzwer.com/3217.html