首页 > 代码库 > 【BZOJ2229】【ZJOI2011】最小割 {没有错,这道题的算法跟题帽是一样的!!!}
【BZOJ2229】【ZJOI2011】最小割 {没有错,这道题的算法跟题帽是一样的!!!}
题解:分治求最小割。
【l……r】里任意找两个作为s、t(不妨把s设为l位置上的点,t设为r位置上的点)求最小割,两层for循环枚举修改map[i][j]即两点间最小割值。
然后一部分属于S集,一部分属于T集,分治【l,L】,【R,r】,每次求完最小割值都全局进行修改。
最后每次询问暴力做就好了,无需任何优化即可AC。
代码:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 200 #define M 7000 #define inf 0x3f3f3f3f #define ci crs[i] #define cj crs[j] using namespace std; struct KSD { int v,len,next,flow; }e[M]; int head[N],cnt; inline void add(int u,int v,int len) { cnt++; e[cnt].v=v; e[cnt].flow=e[cnt].len=len; e[cnt].next=head[u]; head[u]=cnt; } inline void resume(){for(int i=2;i<=cnt;i++)e[i].len=e[i].flow;} int crs[N],tcrs[N]; bool flag[N]; int map[N][N]; int d[N],s,t; int n,m; queue<int>q; bool bfs() { int i,u,v; memset(d,0,sizeof(d)); while(!q.empty())q.pop(); q.push(s),d[s]=1; while(!q.empty()) { u=q.front(),q.pop(); for(i=head[u];i;i=e[i].next) { v=e[i].v; if(e[i].len&&!d[v]) { d[v]=d[u]+1; if(v==t)return 1; q.push(v); } } } return 0; } int dinic(int x,int flow) { if(x==t)return flow; int remain=flow,i,v,k; for(i=head[x];i&&remain;i=e[i].next) { if(d[v=e[i].v]==d[x]+1&&e[i].len) { k=dinic(v,min(remain,e[i].len)); if(!k)d[v]=0; e[i].len-=k,e[i^1].len+=k; remain-=k; } } return flow-remain; } void dfs(int x) { int i,v; flag[x]=1; for(i=head[x];i;i=e[i].next)if(!flag[v=e[i].v]&&e[i].len)dfs(v); } void dar(int l,int r) // divide and rule 分治 { int i,j,maxflow=0; s=crs[l],t=crs[r]; resume(); while(bfs())maxflow+=dinic(s,inf); memset(flag,0,sizeof(flag)),dfs(s); for(i=1;i<=n;i++)for(j=1;j<=n;j++) if(flag[ci]^flag[cj]) map[ci][cj]=min(map[ci][cj],maxflow); int L=l-1,R=r+1; for(i=l;i<=r;i++)(flag[ci]?tcrs[++L]:tcrs[--R])=ci; for(i=l;i<=r;i++)crs[i]=tcrs[i]; if(l<L)dar(l,L); if(R<r)dar(R,r); } int main() { int i,j,k,g; int a,b,c; for(scanf("%d",&g);g--;) { cnt=1; memset(head,0,sizeof(head)); memset(map,0x3f,sizeof(map)); for(scanf("%d%d",&n,&m),cnt=1;m--;) { scanf("%d%d%d",&a,&b,&c); add(a,b,c),add(b,a,c); } for(i=1;i<=n;i++)crs[i]=i; dar(1,n); for(scanf("%d",&m);m--;) { scanf("%d",&k); int ans=0; for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(map[i][j]<=k)ans++; printf("%d\n",ans>>1); } puts(""); } return 0; }
:SW算法求全局最小割,然后两边任意点对间的最小割值肯定都是这个值,然后两边分治。
SW算法相关博客(点此即链接):话说我学SW就是想用来解决这个的233……
这个很有正确性的样子嘛,为什么会挂呢?
就姑且留给读者思考吧,这个是确实有问(fan)题(li)的(跟SW算法实现过程以及分治后的一些值有关系)
代码(WA):
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 160 #define inf 0x3f3f3f3f using namespace std; int n,m,q,crs[N],tcrs[N],cnt; struct ANS { int x,sum; ANS(int _x=0,int _sum=0):x(_x),sum(_sum){} bool operator < (const ANS &a)const{return x<a.x;} }ans[N]; int map[N][N]; int dis[N],f[N]; bool vis[N],flag[N]; int next[N],final[N]; int find(int x){return f[x]==x?x:f[x]=find(f[x]);} void Stoer_Wagner(int l,int r) { int ret=inf; int i,j,_n,rnd; int u,v,temp,lastu=0; for(i=l;i<=r;i++)f[i]=next[i]=final[i]=i,flag[i]=0; for(_n=r-l+1;_n>1;_n--) { for(i=l;i<=r;i++)dis[i]=vis[i]=0; for(rnd=1;rnd<=_n;rnd++) { lastu=u; temp=-1; for(i=l;i<=r;i++)if(f[i]==i&&!vis[i]) { if(temp<dis[i])temp=dis[i],u=i; } vis[u]=1; bool flag=0; for(j=u;;j=next[j]) { if(j==final[u])flag=1; for(i=l;i<=r;i++)if(map[crs[u]][crs[i]]) { v=find(i); if(v!=u)dis[v]+=map[crs[u]][crs[i]]; } if(flag)break; } } if(ret>=dis[u]) { for(i=l;i<=r;i++)flag[i]=(f[i]!=i||i==u); ret=dis[u]; } f[u]=lastu; next[final[lastu]]=u; final[lastu]=final[u]; } int L=l-1,R=r+1; for(i=l;i<=r;i++) { if(flag[i])tcrs[++L]=crs[i]; else tcrs[--R]=crs[i]; } for(i=l;i<=r;i++)crs[i]=tcrs[i]; ans[++cnt]=ANS(ret,(R-l)*(r-L)); if(R-l>1)Stoer_Wagner(l,L); if(r-L>1)Stoer_Wagner(R,r); return ; } int sum[N]; int main() { // freopen("test.in","r",stdin); int i,k,g; int a,b,c; for(scanf("%d",&g);g--;) { memset(map,0,sizeof(map)); scanf("%d%d",&n,&m); for(i=1;i<=n;i++)crs[i]=i; for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); if(a!=b)map[a][b]+=c,map[b][a]+=c; } Stoer_Wagner(1,n); sort(ans+1,ans+cnt+1); for(i=1;i<=cnt;i++)sum[i]=sum[i-1]+ans[i].sum; scanf("%d",&q); while(q--) { scanf("%d",&k); int l=1,r=cnt,mid,ret; while(l<r) { if(r-l<=3) { ret=0; for(i=l;i<=r;i++)if(ans[i].x<=k)ret=i; break; } mid=l+r>>1; if(ans[i].x<=k)l=mid; else r=mid-1; } printf("%d\n",sum[ret]); } } return 0; }
【BZOJ2229】【ZJOI2011】最小割 {没有错,这道题的算法跟题帽是一样的!!!}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。