0、题目大意:求两点之间的最小割,然后找出其中小于x的数量
1、分析:最小割树水题,上个板子就好
#include <queue> #include <ctime> #include <cstdio> #include <cstring> #include <cstring> #include <algorithm> using namespace std; #define LL long long #define inf 214748364 inline int read(){ char ch = getchar(); int x = 0, f = 1; while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while('0' <= ch && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } struct Edge{ int from, to, cap, flow, next; }; int head[310], cur[310]; Edge G[20010]; int tot; int d[310]; bool vis[310]; int s, t, n, m; int a[310]; int ans[310][310]; int b[310]; inline void init(){ memset(head, -1, sizeof(head)); tot = -1; return; } inline void insert(int from, int to, int cap){ G[++ tot] = (Edge){from, to, cap, 0, head[from]}; head[from] = tot; G[++ tot] = (Edge){to, from, 0, 0, head[to]}; head[to] = tot; return; } inline bool BFS(){ memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); vis[s]=1; d[s]=0; while(!Q.empty()){ int x = Q.front(); Q.pop(); for(int i = head[x]; i != -1; i = G[i].next){ Edge& e = G[i]; if(e.cap - e.flow > 0 && !vis[e.to]){ vis[e.to] = 1; d[e.to]=d[x]+1; Q.push(e.to); } } } return vis[t]; } inline int dfs(int x, int a){ if(x == t || a == 0) return a; int flow = 0, f; for(int& i = cur[x]; i != -1; i = G[i].next){ Edge& e = G[i]; if(d[x]+1 == d[e.to] && (f = dfs(e.to, min(e.cap - e.flow, a))) > 0){ e.flow += f; G[i ^ 1].flow -= f; flow += f; a -= f; if(a == 0) break; } } return flow; } inline int maxflow(){ int res = 0; while(BFS()){ for(int i = 1; i <= n; i ++) cur[i] = head[i]; res += dfs(s, inf); } return res; } inline void Clear(){ for(int i = 0; i <= tot; i += 2){ G[i].flow = G[i ^ 1].flow = (G[i].flow + G[i ^ 1].flow) / 2; } } inline void DFS(int x){ vis[x] = 1; for(int i = head[x]; i != -1; i = G[i].next) if(!vis[G[i].to] && G[i].cap > G[i].flow){ DFS(G[i].to); } } inline void solve(int l, int r){ if(l == r) return; s = a[l], t = a[r]; Clear(); int tw = maxflow(); memset(vis, 0, sizeof(vis)); DFS(s); for(int i = 1; i <= n; i ++) if(vis[i]){ for(int j = 1; j <= n; j ++) if(!vis[j]){ ans[i][j] = ans[j][i] = min(ans[i][j], tw); } } int L = l, R = r; for(int i = l; i <= r; i ++){ if(vis[a[i]]) b[L ++] = a[i]; else b[R --] = a[i]; } for(int i = l; i <= r; i ++) a[i] = b[i]; solve(l, L - 1); solve(L, r); } int main(){ int T = read(); while(T --){ n = read(); m = read(); init(); for(int i = 1; i <= m; i ++){ int u = read(), v = read(), w = read(); insert(u, v, w); insert(v, u, w); } for(int i = 1; i <= n; i ++){ for(int j = 1; j <= n; j ++){ ans[i][j] = 214748364; } } for(int i = 1; i <= n; i ++) a[i] = i; solve(1, n); int q = read(); while(q --){ LL ret = 0; int x = read(); for(int i = 1; i <= n; i ++){ for(int j = i + 1; j <= n; j ++){ ret += (ans[i][j] <= x ? 1 : 0); } } printf("%lld\n", ret); } puts(""); } return 0; }