@bzoj - 4519@ [Cqoi2016]不同的最小割

朴灿烈づ我的快乐病毒、 2023-06-01 14:56 97阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

学过图论的同学都知道最小割的概念：对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。  
对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而s,t的最小割指的是在关于s,t的割中容量最小的割。  
而对冲刺NOI竞赛的选手而言，求带权图中两点的最小割已经不是什么难事了。我们可以把视野放宽，考虑有N个点的无向连通图中所有点对的最小割的容量，共能得到 N\*(N−1)/2 个数值。  
这些数值中互不相同的有多少个呢？这似乎是个有趣的问题。

**Input**  
输入文件第一行包含两个数N，M，表示点数和边数。接下来M行，每行三个数u，v，w，表示点u和点v（从1开始标号）之间有条边权值是w。  
1<=N<=850 1<=M<=8500 1<=W<=100000

**Output**  
输出文件第一行为一个整数，表示个数。

**Sample Input**  
4 4  
1 2 3  
1 3 6  
2 4 5  
3 4 4  
**Sample Output**  
3

## @solution@ ##

wow。。。最小割树。。。什么高级玩意儿。。。  
这道题充分体现以前的CQOI考模板题的一贯作风。

每一次在点集中任取两个不同的点 s, t 跑最小割，得到最小割为 k，其中割边集 E 将原图分为两个点集 S 与 T。在树上的 s 与 t 之间连权值为 k 的边，然后分治递归 S 与 T 建树，就可以得到我们的最小割树。  
这个有什么用？可以证明两点之间的最小割等于最小割树上两点之间权值的最小值。  
同时，这也表明两两点之间的最小割最多只会有 N - 1 种不同的值。  
至于证明。。。我统统不会。。。

但是这道题只需要问有多少种不同的最小割，即树上有多少中权值不同的边。所以没有必要实际把树建出来。  
因为树上一共只有 N - 1 条边，所以只需要跑 N - 1 次最大流，时间复杂度 O(N\*最大流的玄学复杂度)。

## @accepted code@ ##

#include<cstdio> #include<queue> #include<set> #include<algorithm> using namespace std; const int MAXN = 850; const int MAXM = 8500; const int MAXV = MAXN; const int MAXE = 4*MAXM; const int INF = (1<<30); bool vis[MAXN + 5]; struct FlowGraph{ struct edge{ int to, flow, cap; edge *nxt, *rev; }edges[MAXE + 5], *adj[MAXV + 5], *cur[MAXV + 5], *ecnt; FlowGraph() {ecnt = &edges[0];} void addedge(int u, int v, int c) { edge *p = (++ecnt), *q = (++ecnt); p->to = v, p->cap = c, p->flow = 0; p->nxt = adj[u], adj[u] = p; q->to = u, q->cap = c, q->flow = 0; q->nxt = adj[v], adj[v] = q; p->rev = q, q->rev = p; } void clear() { for(int i=0;i<=ecnt-edges;i++) edges[i].flow = 0; } int d[MAXV + 5], n, s, t; bool relabel() { for(int i=0;i<=n;i++) cur[i] = adj[i], d[i] = n + 5; d[t] = 0; queue<int>que; que.push(t); while( !que.empty() ) { int f = que.front(); que.pop(); for(edge *p=adj[f];p;p=p->nxt) { if( p->rev->cap > p->rev->flow && d[f] + 1 < d[p->to] ) { d[p->to] = d[f] + 1; que.push(p->to); } } } return !(d[s] == n + 5); } int aug(int x, int tot) { if( x == t ) return tot; int sum = 0; for(edge *&p=cur[x];p;p=p->nxt) { if( d[p->to] + 1 == d[x] && p->cap > p->flow ) { int del = aug(p->to, min(tot - sum, p->cap - p->flow)); p->flow += del, p->rev->flow -= del, sum += del; if( sum == tot ) return sum; } } return sum; } void dfs(int x, bool f) { vis[x] = f; for(edge *p=adj[x];p;p=p->nxt) if( vis[p->to] != f && p->cap > p->flow ) dfs(p->to, f); } int max_flow(int _s, int _t) { int flow = 0; s = _s, t = _t; while( relabel() ) flow += aug(s, INF); return flow; } }G; int n, m, Q; int a[MAXN + 5]; set<int>st; void divide_conquer(int l, int r) { if( l >= r ) return ; int s = a[l], t = a[r]; st.insert(G.max_flow(s, t)); G.dfs(s, true); int m = r; for(int i=r;i>=l;i--) if( vis[a[i]] ) swap(a[m--], a[i]); G.dfs(s, false); G.clear(); divide_conquer(l, m), divide_conquer(m + 1, r); } void build() { for(int i=1;i<=n;i++) a[i] = i; divide_conquer(1, n); } int main() { scanf("%d%d", &n, &m), G.n = n; for(int i=1;i<=m;i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); G.addedge(u, v, w); } build(); printf("%d\n", st.size()); }

## @details@ ##

做完这道题稍微改一改你还可以继续做ZJOI2011的最小割。

求最小割时，必须要把所有边的流量归零，且要在原图上求最小割。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11416355.html