題目鏈接：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++;新聞熱點
疑難解答
