POJ1815

Problem : Friendship
Description : 一些人之间可以相互联系，但是当一个人出事后，那么与他有联系的人都会和他失去联系，同样，人与人之间的联系具有传递性，那么现在给你两个人，问你最少多少个人出事才能使得这两个人失去联系，注意，这两个人不可能出事。
Solution : 这是一个典型的求割点数目的问题，然而割点又可以通过拆点转化成割边来做，那么这个题就成了求最小割的问题了，我们的做法就是，枚举割点，如果这个点是割点那么在图中删掉这个点后跑一遍最大流后，最小割会变小，那么记录下这个点，如果最小割不变，那么这个点就不是必须的，把这个点又在图中恢复，这样下来就可以把所有的割点都找到了。拆点然后在这两个点之间连一条权值为1的边是为了每个人只会删除一次，相当于删掉这个点了，而且，这条边的在S，T之间的权值要设成INF，这是为了给出的两个人总不会出事。这条边的方向要和其他边的方向相反，这也是为了满足传递性。这题我开始用的邻接矩阵TLE，非得逼我用邻接表才AC。
Code(C++) :

#include <stdio.h>
#include <string.h>

#include <iostream>
#include <string>
#include <queue>

#define MIN(a,b) ((a)>(b)? (b):(a))

using namespace std;

const int SIZE=400+50;
const int INF=0x3f3f3f3f;

struct Node{
    int u,v;
    int cap;
    Node(){}
    Node(int U,int V,int Cap):
    u(U),v(V),cap(Cap){}
};

int src,des;
vector<int> G[SIZE];
Node e[SIZE*SIZE/2];
int d[SIZE];
int cur[SIZE];
int n;
int top;

int N,S,T;
bool had_erase[SIZE/2];
int MAP[SIZE/2][SIZE/2];
int t_M[SIZE/2][SIZE/2];

void addedge(int u,int v,int cap)
{
    G[u].push_back(top);
    e[top++]=Node(u,v,cap);
    G[v].push_back(top);
    e[top++]=Node(v,u,0);
}

void build()
{   
    int i,j;
    for(i=0;i<SIZE;i++)
        G[i].clear();
    top=0;
    n=2*N;
    src=0;
    des=n+1;
    addedge(src,S,INF);
    addedge(T+N,des,INF);
    for(i=1;i<=N;i++)
        addedge(i+N,i,1);
    addedge(S+N,S,INF);
    addedge(T+N,T,INF);
    for(i=1;i<=N;i++)
        for(j=1;j<=N;j++)
            if(MAP[i][j]&&i!=j)
                addedge(i,j+N,INF);
}

bool bfs(int src,int des)
{
    memset(d,-1,sizeof(d));
    queue<int> que;
    que.push(src);
    d[src]=0;
    while(!que.empty()){
        int now=que.front();
        que.pop();
        for(int i=0;i<G[now].size();i++){
            Node &tmp=e[G[now].at(i)];
            if(tmp.cap>0&&d[tmp.v]==-1)
                d[tmp.v]=d[now]+1,
                que.push(tmp.v);
        }
    }
    return d[des]>=0;
}

int dfs(int t,int sum,int des)
{
    if(t==des||!sum)
        return sum;
    int flow=0,f;
    for(int &i=cur[t];i<G[t].size();i++){
        Node &tmp=e[G[t].at(i)];
        if(d[tmp.v]==d[t]+1&&(f=dfs(tmp.v,MIN(sum,tmp.cap),des))>0){
            tmp.cap-=f;
            e[G[t].at(i)^1].cap+=f;
            sum-=f;
            flow+=f;
            if(!sum)
                break;
        }
    }
    return flow;
}

int DINIC(int src,int des)
{
    int sum=0;
    while(bfs(src,des)){
        memset(cur,0,sizeof(cur));
        sum+=dfs(src,INF,des);
    }
    return sum;
}

void work()
{
    int i,j;
    for(i=1;i<=N;i++)
        for(j=1;j<=N;j++)
            scanf("%d",&MAP[i][j]);
    if(MAP[S][T]){
        puts("NO ANSWER!");
        return ;
    }
    build();
    int tmp=DINIC(src,des);
    printf("%d\n",tmp);
    if(!tmp)
        return ;
    memset(had_erase,false,sizeof(had_erase));
    for(int L=1;L<=N;L++){
        if(L==S||L==T)
            continue;

        int i,j;
        for(i=1;i<=N;i++)
            for(j=1;j<=N;j++){
                t_M[i][j]=MAP[i][j];
                if(i==L||j==L)
                    MAP[i][j]=0;
            }
        build();
        int t=DINIC(src,des);
        if(t>=tmp){
            for(i=1;i<=N;i++)
                for(j=1;j<=N;j++)
                    MAP[i][j]=t_M[i][j];
        }
        else{
            --tmp;
            had_erase[L]=true;
        }
        if(!tmp)
            break;
    }
    int h[SIZE]={0};
    int top=0;
    for(i=1;i<=N;i++)
        if(had_erase[i])
            h[top++]=i;
    printf("%d",h[0]);
    for(i=1;i<top;i++)
        printf(" %d",h[i]);
    puts("");
}

int main()
{
    //freopen("in.data","r",stdin);
    while(~scanf("%d%d%d",&N,&S,&T))
        work();
    return 0;
}