首先学习一下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; }