首页 > 代码库 > POJ1815_Friendship
POJ1815_Friendship
一个无向图,问你删除多少点后,可以隔断起点到终点的所有路径?输出字典序最小的删点方案。
求最小点割,先拆点,容量为1,普通边容量无穷,最大流即为应删点数。
需要求出字典序最小的方案,可以从小到大枚举所有的点,如果当前枚举的点是割点,那么进行标记,同时后面的枚举也不再经过这个点。
召唤代码君:
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <vector>#define maxn 5555#define maxm 555555using namespace std;int to[maxm],next[maxm],c[maxm],belong[maxm],first[maxm],edge;int d[maxn],tag[maxn],TAG=222;bool can[maxn],go[maxn];int Q[maxn],bot,top;int f[511][511];int s,t,n,pos[maxn];void _init(){ edge=-1; for (int i=1; i<=n+n; i++) first[i]=-1,go[i]=false;}void addedge(int U,int V){ edge++; to[edge]=V,c[edge]=1,next[edge]=first[U],first[U]=edge; edge++; to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge;}bool bfs(){ Q[bot=top=1]=t,tag[t]=++TAG,d[t]=0,can[t]=false; while (bot<=top) { int cur=Q[bot++]; for (int i=first[cur]; i!=-1; i=next[i]) if (c[i^1]>0 && tag[to[i]]!=TAG && !go[to[i]]) { tag[to[i]]=TAG,d[to[i]]=d[cur]+1; can[to[i]]=false,Q[++top]=to[i]; if (to[i]==s) return true; } } return false;}int dfs(int cur,int num){ if (cur==t) return num; int tmp=num,k; for (int i=first[cur]; i!=-1; i=next[i]) if (c[i]>0 && tag[to[i]]==TAG && d[to[i]]==d[cur]-1 && !can[to[i]]) { k=dfs(to[i],min(num,c[i])); if (k) num-=k,c[i]-=k,c[i^1]+=k; if (!num) break; } if (num) can[cur]=true; return tmp-num;}int maxflow(){ int flow=0; while (bfs()) flow+=dfs(s,~0U>>1); return flow;}int get(int x){ for (int i=first[x]; i!=-1; i=next[i]) if (c[i]==0 && !(i&1)) { int tmp=to[i]; tmp-=x; if (tmp<0) tmp=-tmp; if (tmp!=n) return get(to[i]); tmp=min(x,to[i]); return min(tmp,get(to[i])); } return ~0U>>1;}int main(){ int tmp,mf; vector<int> ans; while (scanf("%d%d%d",&n,&s,&t)!=EOF) { _init(); for (int i=1; i<=n; i++) addedge(i,i+n),pos[i]=edge; for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) { scanf("%d",&tmp); f[i][j]=f[j][i]=tmp; if (i>=j) continue; if (tmp) addedge(i+n,j),addedge(j+n,i); } if (s==t || f[s][t]) { puts("NO ANSWER!"); continue; } s+=n; ans.clear(); mf=maxflow(); printf("%d\n",mf); if (mf==0) continue; for (int i=1; i<=n && mf>0; i++) { if (i==s-n || i==t) continue; for (int j=0; j<edge; j+=2) c[j]+=c[j+1],c[j+1]=0; go[i]=true,go[i+n]=true; tmp=maxflow(); if (tmp<mf) ans.push_back(i),mf--; else go[i]=false,go[i+n]=false; } sort(ans.begin(),ans.end()); printf("%d",ans[0]); for (unsigned i=1; i<ans.size(); i++) printf(" %d",ans[i]); printf("\n"); } return 0;}
POJ1815_Friendship
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。