首页 > 代码库 > 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