网站建设 东方网景,wordpress仿美拍,赣州人才市场最新招聘信息,推广软文平台正题
题目大意:https://www.luogu.com.cn/problem/P4123 题目大意
一张无向图#xff0c;求所有点对之间有多少不同的最小割。 解题思路
考虑分治的做法#xff0c;如果我们得知了(s,t)(s,t)(s,t)的最小割www#xff0c;并且剩下的残量网络中连通点集SSS与sss连通#x…正题
题目大意:https://www.luogu.com.cn/problem/P4123 题目大意
一张无向图求所有点对之间有多少不同的最小割。 解题思路
考虑分治的做法如果我们得知了(s,t)(s,t)(s,t)的最小割www并且剩下的残量网络中连通点集SSS与sss连通点集TTT与ttt连通。那么点集SSS到TTT的每个点对之间的最小割都是www。然后分治到两个点集去做即可。
这样下来最小割的期望次数是O(n)O(n)O(n)级别的可以通过本题。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#includemap
using namespace std;
const int N900,inf2147483647/3;
struct node{int to,next,w,ret;
}a[N*20];
int n,m,ls[N],tot1;
int dep[N],p[N],ans;
mapint,int mp;
queueint q;
void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].retw;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].ww;a[tot].retw;return;
}
bool bfs(int s,int t){memset(dep,0,sizeof(dep));dep[s]1;while(!q.empty())q.pop();q.push(s);while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[y]||!a[i].w)continue;dep[y]dep[x]1;if(yt)return 1;q.push(y);}}return 0;
}
int dinic(int x,int flow,int t){int rest0,k;if(xt)return flow;for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[x]1!dep[y]||!a[i].w)continue;rest(kdinic(y,min(flow-rest,a[i].w),t));a[i].w-k;a[i^1].wk;if(flowrest)return flow;}if(!rest)dep[x]0;return rest;
}
bool cmp(int x,int y)
{return dep[x]dep[y];}
void solve(int l,int r){if(lr)return;int w0; while(bfs(p[l],p[r]))wdinic(p[l],inf,p[r]);if(!mp.count(w))mp[w]1,ans;sort(pl,p1r,cmp);int midl;for(int il;ir;i)if(dep[p[i]]){midi;break;}for(int i1;itot;i)a[i].wa[i].ret;solve(l,mid-1);solve(mid,r);return;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)p[i]i;for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);addl(x,y,w);}solve(1,n);printf(%d\n,ans);
}
