POJ 1815 Friendship 求最小点割集

Description

Input

Output

Sample Input

3 1 3
1 1 0
1 1 1
0 1 1

Sample Output

1
2

Source

//1408K	704MS
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 0x3f3f3f3f
#define M 1007
#define MIN(a,b) a>b?b:a;
using namespace std;
struct E
{
    int v,w,next;
} edg[500000];
int dis[M],gap[M],head[M],nodes;
int sourse,sink,nn;
int g[M][M],cut[M],p[M];
int n;
void addedge(int u,int v,int w)
{
    edg[nodes].v=v;
    edg[nodes].w=w;
    edg[nodes].next=head[u];
    head[u]=nodes++;
    edg[nodes].v=u;
    edg[nodes].w=0;
    edg[nodes].next=head[v];
    head[v]=nodes++;
}
int dfs(int src,int aug)
{
    if(src==sink)return aug;
    int left=aug,mindis=nn;
    for(int j=head[src]; j!=-1; j=edg[j].next)
    {
        int v=edg[j].v;
        if(edg[j].w)
        {
            if(dis[v]+1==dis[src])
            {
                int minn=MIN(left,edg[j].w);
                minn=dfs(v,minn);
                edg[j].w-=minn;
                edg[j^1].w+=minn;
                left-=minn;
                if(dis[sourse]>=nn)return aug-left;
                if(left==0)break;
            }
            if(dis[v]<mindis)
                mindis=dis[v];
        }
    }

    if(left==aug)
    {
        if(!(--gap[dis[src]]))dis[sourse]=nn;
        dis[src]=mindis+1;
        gap[dis[src]]++;
    }
    return aug-left;
}
int sap(int s,int e)
{
    int ans=0;
    nn=n*2;
    memset(dis,0,sizeof(dis));
    memset(gap,0,sizeof(gap));
    gap[0]=nn;
    sourse=s;
    sink=e;
    while(dis[sourse]<nn)
        ans+=dfs(sourse,inf);
    return ans;
}
void build()
{
    memset(head,-1,sizeof(head));
    nodes=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
         if(g[i][j]){addedge(i+n,j,inf);addedge(j+n,i,inf);}
    for(int i=1; i<=n; i++)
        if(!cut[i])addedge(i,i+n,1);
        else addedge(i,i+n,0);
}
int main()
{
    int start,end;
    scanf("%d%d%d",&n,&start,&end);
    memset(head,-1,sizeof(head));
    memset(cut,0,sizeof(cut));
    nodes=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            scanf("%d",&g[i][j]);
    if(g[start][end])
    {
        printf("NO ANSWER!\n");
        return 0;
    }
    build();//建图
    int anss=sap(start+n,end);
    printf("%d\n",anss);
    int cnt=0;
    for(int i=1; i<=n&&anss; i++)
    {
        if(i==start||i==end)continue;
        cut[i]=1;
        build();
        if(sap(start+n,end)==anss-1)
        {
            anss--;
            p[cnt++]=i;
        }
        else  cut[i]=0;
    }
    for(int i=0; i<cnt; i++)
        printf("%d ",p[i]);
    printf("\n");
    return 0;
}