首先学习一下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; }
2015年6月29日 12:30
神神神!!!
2019年2月19日 13:37
The lists of the programmers are prepared for the goodwill of the computer specialists. The role of the program and top rated professional resume writers is advanced in the midst of the skills. The abilities are met for the occupational challenges for the citizens in the whole of the scheme of the program.