davidwang's Blog

首先学习一下fhq的最小割树理论

应该是比较好理解的，然后只需要求n此最小割就可以得到任意两点之间的最小割了，因为大错一个字母然后拜样例所赐一直在疯狂的wa然后……然后&然后就没有了

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <climits>
#include <queue>
#include <deque>
#include <iostream>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
#define PII pair<int,int>
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 155,M=3010;
struct edge{
	int to,flow;
	edge(int to=0,int flow=0):to(to),flow(flow){}
}e[M*2];
vector<int>g[N];
int vis[N],q[N],d[N],cnt;
inline void connect(int x,int y,int f){
	e[cnt]=edge(y,f); g[x].push_back(cnt++);
	e[cnt]=edge(x,f); g[y].push_back(cnt++);
}
int s,t,n,m;
int bfs(){
	int head=0,tail=1,u,v;
	memset(d,0,sizeof(d));
	q[1]=s; d[s]=1;
	while (head<tail){
		u=q[++head];
		for (vector<int>::iterator it=g[u].begin();it!=g[u].end();it++){
			if (e[*it].flow && d[e[*it].to]==0){
				d[e[*it].to]=d[u]+1;
				q[++tail]=e[*it].to;
			}
		}
	}
	return d[t];
}
int dfs(int x,int flow){
	if (x==t || flow==0) return flow;
	int f,totflow=0;
	for (vector<int>::iterator it=g[x].begin();it!=g[x].end();it++){
		if (e[*it].flow && d[e[*it].to]==d[x]+1){
			f=dfs(e[*it].to,min(flow,e[*it].flow));
			totflow+=f; flow-=f;
			e[*it].flow-=f; e[(*it)^1].flow+=f;
			if (flow==0) return totflow;
		}
	}
	if (flow)d[x]=0;
	return totflow;
}
inline int dinic()
{
	int ret=0;
	while (bfs()) ret+=dfs(s,INT_MAX);
	return ret;
}
			
int ans[N][N];
inline void rebuild(){
	for (int i=0;i<cnt;i+=2)
		e[i].flow=e[i+1].flow=(e[i].flow+e[i+1].flow)/2;	
}
int a[N],list[N];
void solve(int l,int r){
	if (l==r) return;
	rebuild();
	s=a[l],t=a[r];
	int Flow=dinic();
	for (int i=1;i<=n;i++)
		if (d[i])
			for (int j=1;j<=n;j++)
				if (d[j]==0)
					ans[i][j]=ans[j][i]=min(ans[i][j],Flow);
	int L=l,R=r;
	for (int i=l;i<=r;i++){
		if (d[a[i]])
			list[L++]=a[i];
		else list[R--]=a[i];
	}
	for (int i=l;i<=r;i++) a[i]=list[i];
	solve(l,L-1); solve(R+1,r);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	int T=read();
	while (T--){
		cnt=0; for (int i=1;i<=n;i++) g[i].clear();
		memset(ans,127,sizeof(ans));
		n=read(); m=read();
		for (int i=1;i<=m;i++){
			int x=read(),y=read(),z=read();
			connect(x,y,z);
		}
		for (int i=1;i<=n;i++) a[i]=i;
		solve(1,n);
		int Q=read();
		while (Q--){
			int now=read(),ret=0;
			for (int i=1;i<=n;i++)
				for (int j=i+1;j<=n;j++)
					if (ans[i][j]<=now) ret++;
			printf("%d\n",ret);
		}
		puts("");
	}
	return 0;
}