POJ--1966--Cable TV Network【无向图顶点连通度】

链接：http://poj.org/problem?id=1966

题意：一个无向图，n个点，m条边，求此图的顶点连通度。

思路：顶点连通度，即最小割点集里的割点数目。一般求无向图顶点连通度的方法是转化为网络流的最小割。

建图：

（1）原图每一个点i拆点，拆为i‘和i’‘，i’到i‘’连一条弧容量为1。

（2）对于原图中存在的边(u, v)，连两条弧(u‘, v')和(v'', u')，容量INF。

（3）找一个源点i。这个点不能和其它全部点都相邻否则无法找到最小割，以这个点i''为源点，枚举汇点j'。

图建好了之后求n-1遍最大流。答案最小的那个就是此图的顶点连通度，i'到i''满流的i点组成了最小割点集。

#include<cstring>

#include<string>

#include<fstream>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<queue>

#include<map>

#include<set>

#include<vector>

#include<stack>

#include<ctime>

#include<cstdlib>

#include<functional>

#include<cmath>

using namespace std;

#define PI acos(-1.0)

#define MAXN 1010

#define eps 1e-7

#define INF 0x3F3F3F3F      //0x7FFFFFFF

#define LLINF 0x7FFFFFFFFFFFFFFF

#define seed 1313131

#define MOD 1000000007

#define ll long long

#define ull unsigned ll

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

struct node{

    int u,v,w,next;

}edge[500000],edge2[500000];

int head[120],dist[120],cur[120],fa[120],num[120],vis[120];

int n,m,k,cnt,nn,src,sink;

void add_edge(int a,int b,int c){

    edge2[cnt].u = a;

    edge2[cnt].v = b;

    edge2[cnt].w = c;

    edge2[cnt].next = head[a];

    head[a] = cnt++;

}

void bfs()

{

    int x,i,j;

    queue<int> q;

    memset(dist,-1,sizeof(dist));

    memset(num,0,sizeof(num));

    q.push(sink);

    dist[sink] = 0;

    num[0] = 1;

    while(!q.empty()){

        x = q.front();

        q.pop();

        for(i=head[x];i!=-1;i=edge[i].next){

            if(dist[edge[i].v]<0){

                dist[edge[i].v] = dist[x] + 1;

                num[dist[edge[i].v]]++;

                q.push(edge[i].v);

            }

        }

    }

}

int augment()

{

    int x=sink,a=INF;

    while(x!=src){

        a = min(a,edge[fa[x]].w);

        x = edge[fa[x]].u;

    }

    x=sink;

    while(x!=src){

        edge[fa[x]].w -= a;

        edge[fa[x]^1].w += a;

        x = edge[fa[x]].u;

    }

    return a;

}

int isap()

{

    int i,x,ok,minm,flow=0;

    bfs();

    for(i=0;i<=nn+5;i++) cur[i] = head[i];

    x=src;

    while(dist[src]<nn){

        if(x==sink){

            flow += augment();

            x = src;

        }

        ok=0;

        for(i=cur[x];i!=-1;i=edge[i].next){

            if(edge[i].w && dist[x]==dist[edge[i].v]+1){

                ok=1;

                fa[edge[i].v] = i;

                cur[x] = i;

                x = edge[i].v;

                break;

            }

        }

        if(!ok){

            minm = nn;

            for(i=head[x];i!=-1;i=edge[i].next)

                if(edge[i].w && dist[edge[i].v]<minm)   minm=dist[edge[i].v];

            if(--num[dist[x]]==0)break;

            num[dist[x]=minm+1]++;

            cur[x]=head[x];

            if(x!=src)  x=edge[fa[x]].u;

        }

    }

    return flow;

}

int main(){

    int i,j;

    int a,b;

    while(scanf("%d%d",&n,&m)!=EOF){

        memset(head,-1,sizeof(head));

        cnt = 0;

        for(i=0;i<n;i++){

            add_edge(i,i+n,1);

            add_edge(i+n,i,0);

        }

        for(i=0;i<m;i++){

            scanf(" (%d,%d)",&a,&b);

            add_edge(a+n,b,INF);

            add_edge(b,a+n,0);

            add_edge(b+n,a,INF);

            add_edge(a,b+n,0);

        }

        int ans = INF;

        nn = n * 2;

        for(i=0;i<n;i++){

            memset(vis,0,sizeof(vis));

            for(j=head[i];j!=-1;j=edge2[j].next){

                vis[edge2[j].v] = 1;

            }

            int sum = 0;

            for(j=0;j<n;j++){

                if(vis[j])  sum++;

            }

            if(sum < n - 1){

                src = i + n;

                break;

            }

        }

        for(i=1;i<n;i++){

            sink = i;

            memcpy(edge,edge2,sizeof(node)*cnt);

            int temp = isap();

            ans = min(ans, temp);

        }

        if(ans == INF)  ans = n;

        printf("%d\n",ans);

    }

    return 0;

}