题解 UVA1660 【电视网络 Cable TV Network】

· · 题解

题目链接

更好的阅读体验

不得不说，网络流的题目其实实现起来都是套模板，但是要想到就很困难。

很多人学了最小割之后就来切这道“裸题”，数据范围小，还没要求输出具体方案，太简单了！

但是最小割是适用于有向图，而且是边集，但是这道题是要我们找出点的个数，而且是无向图。

在看这篇题解的时候默认你知道“最大流最小割定理”

我们先来着手解决第一个问题：无向图转化成有向图。

由于这道题是关于图的连通性的问题，因此转化出来的有向图和原图连通性不变

如上图，我们可以将原来的图的每个点，拆成两个点x,x‘（图中的点不包括源点和汇点），在它们之间连容量为1的有向边。对于原来的边(x,y)，我们可以转化成(x',y)和(y',x)这两条有向边，容量为\infty

这样做显然连通性不变。

而且，我们发现，在原图中，如果删去y点，x与z就不连通了；

在转换图中，如果删去(y,y')那么x与z也是不连通的；

于是我们可以将问题转化为：在转化后图中，至少删掉多少条权值为1的边才能使图不连通；

这就是一个典型的最小割问题，由于其他边权值都是 \infty ,而图中最大流量为N-2，因此求最小割的时候贡献答案的一定是权值为1的边。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN =500;
const int inf=1<<30;
int Head[MAXN*10],Nt[MAXN*10],val[MAXN*10],to[MAXN*10],pre[MAXN],incf[MAXN],v[MAXN];
int s,t,n,m,tot=1,maxflow;
int a[MAXN],b[MAXN];


void add(int x,int y,int z){
    Nt[++tot]=Head[x];
    to[tot]=y;
    val[tot]=z;
    Head[x]=tot;
    Nt[++tot]=Head[y];
    to[tot]=x;
    val[tot]=0;
    Head[y]=tot;
}

int read(){
    int x=0,f=1;char ch='[';
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f=-1;}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

bool bfs(){
    memset(v,0,sizeof(v));
    queue<int>q;
    q.push(s);incf[s]=inf;v[s]=1;
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=Head[x];i;i=Nt[i]){
            if(val[i]){
                int y=to[i];
                if(v[y])continue;
                incf[y]=min(incf[x],val[i]);
                pre[y]=i;
                if(y==t)return 1;
                q.push(y);v[y]=1;
            }
        }
    }
    return 0;
}

void update(){
    int x=t;
    while(x!=s){
        int i=pre[x];
        val[i]-=incf[t];
        val[i^1]+=incf[t];
        x=to[i^1];
    }
    maxflow+=incf[t];
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=1;i<=m;i++){
            a[i]=read()+1;
            b[i]=read()+1;
        }
        int ans=inf;
        for(s=1;s<=2;s++)
            for(t=1;t<=n;t++){
                if(s!=t){
                    memset(Head,0,sizeof(Head));
                    tot=1;maxflow=0;
                    for(int i=1;i<=n;i++){
                        if(i==s||i==t)add(i,i+n,inf);
                        else add(i,i+n,1);
                    }
                    for(int i=1;i<=m;i++){
                        add(a[i]+n,b[i],inf);
                        add(b[i]+n,a[i],inf);
                    }
                    while(bfs())update();
                    ans=min(ans,maxflow);
                }
            }
        if(n<=1||ans==inf)ans=n;
        cout<<ans<<endl;
    }
    return 0;
}

Q&A

对于上面有些问题没弄懂的可以看这里

Q1：为什么最大流量是N-2？

A：你可以想一下最大流量的情况，就是整个图分3层，第一层为源点，第三层为汇点，第二层有N-2个点，每个点流量都是1；

欢迎提问~