POJ 1966 Cable TV Network (点连通度)【最小割】

题目大意：

给定一个无向图，求点连通度，即最少去掉多少个点使得图不连通。

解题分析：

解决点连通度和边连通度的一类方法总结见 >>>

本题是求点连通度，所以对每个点进行拆点，然后入点向出点连一条容量为1的边，其它边则是用一个容量为INF的边来代替。然后就是枚举一下源点和汇点，跑最大流，选最小的值即可。不过，本题需要注意一下是否为完全图，因为完全图的最大流是INF，所以特判一下，如果是完全图，就将点全部删除，输出n。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

typedef long long ll;
const int N = 500 , INF = 0x3f3f3f3f;

struct Dinic
{
    struct edge{ int from,to;ll cap,flow; };     //cap-flow才是这条边的真实流量
    vector<edge>es;
    vector<int>G[N];
    bool vis[N];
    int dist[N],iter[N];
    void init(int n){
        for(int i=0; i<=n+10; i++)G[i].clear();
        es.clear();
    }
    void addedge(int from,int to,ll cap){
        es.push_back((edge){from,to,cap,0});    //将边存储的边表
        es.push_back((edge){to,from,0,0});
        int x=es.size();     
        G[from].push_back(x-2);    //G[u][i]记录以u为顶点的第i条边的反边在es中的编号
        G[to].push_back(x-1);
    }
    bool BFS(int s,int t){      //bfs将该图划分成分层图
        memset(vis,0,sizeof(vis));
        queue <int> q;
        vis[s]=1;
        dist[s]=0;
        q.push(s);
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=0; i<G[u].size(); i++){
                edge &e=es[G[u][i]];
                if(!vis[e.to]&&e.cap>e.flow){
                    vis[e.to]=1;
                    dist[e.to]=dist[u]+1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int DFS(int u,int t,ll f){
        if(u==t||f==0)return f;
        int nowflow=0,d;
        for(int &i=iter[u]; i<G[u].size(); i++){
            edge &e=es[G[u][i]];
            if(dist[u]+1==dist[e.to]&&(d=DFS(e.to,t,min(f,e.cap-e.flow)))>0){
                e.flow+=d;     //正边真实流量-d
                es[G[u][i]^1].flow-=d;    //反边真实流量+d
                nowflow+=d;    //得到现在搜得的能够流入汇点的流量
                f-=d;      //找到一条增广路之后，减去这条路的流量，然后继续从这个顶点的其它边开始寻找增广路
                if(f==0)break;
            }
        }
        return nowflow;
    }
    int Maxflow(int s,int t){
        int flow=0;
        while(BFS(s,t)){
            memset(iter,0,sizeof(iter));
            int d=0;
            while(d=DFS(s,t,INF))flow+=d;
        }
        return flow;
    }
}dinic;


int mpa[110][110];
int n,m;

inline void getGraph(){
    dinic.init(2*n+5);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)dinic.addedge(i,i+n,1);
            else if(mpa[i][j])dinic.addedge(i+n,j,INF);
        }
    }
}

int main(){
    while(cin>>n>>m){
        memset(mpa,0,sizeof(mpa));
        for(int i=1;i<=m;i++){
            int u,v;scanf(" (%d,%d)",&u,&v);
            mpa[u][v]=mpa[v][u]=1;
        }
        int ans=INF;
        for(int st=0;st<n;st++){
            for(int ed=st+1;ed<n;ed++){
                getGraph(); 
                ans=min(ans,dinic.Maxflow(st+n,ed));       //注意这里是st+n
            }
        }
        if(ans>n)ans=n;     //如果是完全图，最大流就是INF,只能全部删除，才能使得原图不连通
        printf("%d
",ans); 
    }   
}

POJ 1966 Cable TV Network (点连通度)【最小割】

相关推荐