题目链接：bzoj点我:-) 洛谷点我:-) 题目描述： 小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话： ”对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。 对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而s,t的最小割指的是在关于s,t的割中容量最小的割“ 现给定一张无向图，小白有若干个形如”图中有多少对点它们的最小割的容量不超过x呢“的疑问，小蓝虽然很想回答这些问题，但小蓝最近忙着挖木块，于是作为仍然是小蓝的好友，你又有任务了。
输入格式： 输入文件第一行有且只有一个正整数T，表示测试数据的组数。 对于每组测试数据， 第一行包含两个整数n,m，表示图的点数和边数。 下面m行，每行3个正整数u,v,c(1<=u,v<=n,0<=c<=
输出格式： 对于每组测试数据，输出应包括q行，第i行表示第i个问题的答案。对于点对(p,q)和(q,p)，只统计一次（见样例）。两组测试数据之间用空行隔开。
思路： 最小割树的裸题。（入门的讲解） 最小割树性质：若不考虑多个最小割的情况，设S1-T1的最小割割集为C1，S2-T2的最小割割集为C2，则C1，C2必然不会相互跨立，这个结论可通过反证法得到（是可以感性证明一下的）。 它们构成了一棵最小割树，每次挑两个点算MInCut分成两个集合分治算即可，最小割数目不超过
所以Dinic+分治，但是isap不知道为什么RE了（爆栈？）。。
感想： 又一次深夜刷的题。。昨天1点多钟还在WA，整个人都不好了，早上发现。。居然忘了在跟新答案时赋成双向。（论刚开始连题目都没看懂并且不知道割是什么的我。。好吧割集是删掉这个集合中的任意一条边，会使那两个点不联通） 终于又有动力做题了，终于知道看到别人刷题记录时的强大动力了>-<
代码：
//miaomiao 2017.2.8#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<queue>using namespace std;#define Set(a, v) memset(a, v, sizeof(a))#define For(i, a, b) for(int i = (a); i <= (int)(b); i++)#define N (150+5)#define M (6000+5)#define INF 0x3f3f3f3fstruct Dinic{ int Begin[N], Next[M], to[M], cap[M], flow[M]; int cur[N], d[N], n, e, s, t; void init(){e = 1; Set(Begin, 0);} void clearflow(){Set(flow, 0);} void AddEdge(int u, int v, int w){ cap[++e] = w; to[e] = v; Next[e] = Begin[u]; Begin[u] = e; } bool Bfs(){ Set(d, 0); queue<int> q; q.push(s); int now; d[s] = 1; while(!q.empty()){ now = q.front(); q.pop(); for(int i = Begin[now]; i; i = Next[i]) if(cap[i] > flow[i] && !d[to[i]]){d[to[i]] = d[now]+1; q.push(to[i]);} } return d[t]; } int Dfs(int now, int minf){ if(now==t || minf <= 0) return minf; int v, f, ret = 0; for(int &i = cur[now]; i; i = Next[i]){ v = to[i]; if(d[v]==d[now]+1 && (f=Dfs(v, min(minf, cap[i]-flow[i])))>0){ ret += f; minf -= f; flow[i] += f; flow[i^1] -= f; if(minf <= 0) return ret; } } return ret; } int MinCut(int ss, int tt){ s = ss; t = tt; int ret = 0; while(Bfs()){ For(i, 1, n) cur[i] = Begin[i]; ret += Dfs(s, INF); } return ret; }}Din;int n, cut[N][N], id[N], tmp[N];void solve(int L, int R){ if(L == R) return; Din.clearflow(); int flow = Din.MinCut(id[L], id[R]), l = L, r = R; For(i, 1, n) if(Din.d[i]) For(j, 1, n) if(!Din.d[j]) cut[i][j] = cut[j][i] = min(cut[i][j], flow); For(i, L, R) tmp[Din.d[id[i]]? l++: r--] = id[i]; For(i, L, R) id[i] = tmp[i]; solve(L, r); solve(l, R);}int main(){ int T, m, u, v, w, q, x, ans; scanf("%d", &T); while(T--){ Din.init(); scanf("%d%d", &n, &m); Din.n = n; For(i, 1, m){ scanf("%d%d%d", &u, &v, &w); Din.AddEdge(u, v, w); Din.AddEdge(v, u, w); } For(i, 1, n) id[i] = i; Set(cut, INF); solve(1, n); scanf("%d", &q); while(q--){ scanf("%d", &x); ans = 0; For(i, 1, n) For(j, i+1, n) if(cut[i][j] <= x) ans++; PRintf("%d/n", ans); } if(T) puts(""); } return 0;}新闻热点
疑难解答
