POJ 1966 Cable TV Network （最大流最小割）

$ POJ₁₉₆₆Cable_TVNetwork $

$ solution: $

第一眼可能让人很难下手，但本就是冲着网络流来的，所以我们直接一点。这道题我们要让这个联通图断开，那么势必会有两个点变得不连通，这道题的数据范围很小，所以我们试着暴力枚举两个点。这样就变成了最小割。不过，嗯？割的东西怎么是点？

为了靠近我们已经学得知识，我们想办法看，能不能割点变成割边。反正网络流最喜欢千变万化、左右建模了。。。于是我们引进书上的一个东西：

一个节点可以拆成两个节点，将原节点用中间那条边表示
一条边可以拆成两条边，将原边用中间那个点表示
中间的边权为1代表这个点是否被割，旁边的边权为inf是为了排除其影响（因为它不可能被割掉）

我们用第一条和第三条性质可以解决这个问题。首先对于每个节点建立两个 $ i $ 和 $ i+n $ 节点。然后这两个节点之间用一条权值为1的有向边（从 $ i $ 到 $ i+n $ ），如果这条边在最小割中被割掉（等价于原本的点被割掉）。然后 $ i $ 节点连入边（权值正无穷）， $ i+n $ 节点连出边（权值正无穷），连正无穷是为了让割掉的边只能是中间的边。然后我们跑一遍最大流，它对应的最小割里每条代表原来一个点，因为权值为1，所以流量就是答案。

注意：我们的源汇点也要被分为两个点，而网络流中的实际源点是 $ S+n $ ，它连出边。因为源汇点的性质，这两个点不可能被割掉，所以它们中间不连边。

$ code: $

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

#define ll long long
#define db double
#define rg register int

using namespace std;

int n,m,S,T;
int ans,top=1;
int dep[505];
int tou[505];
int qi[505];
int f[55][55];

struct su{
	int to,v,next;
}b[5005];

inline int qr(){
	register char ch; register bool sign=0; rg res=0;
	while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
	while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
	if(sign)return -res; else return res;
}

inline void add(int x,int y,int v){ //注意博主加边自带反向
	b[++top]=su{y,v,tou[x]}; tou[x]=top;
	b[++top]=su{x,0,tou[y]}; tou[y]=top;
}

inline bool bfs(int x){
	for(rg i=1;i<=x;++i)
		qi[i]=tou[i],dep[i]=0;
	queue<int> q; q.push(S); dep[S]=1;
	while(!q.empty()){
		rg i=q.front(); q.pop();
		for(rg j=tou[i];j;j=b[j].next)
			if(b[j].v&&!dep[b[j].to]){
 				dep[b[j].to]=dep[i]+1;
				if(b[j].to==T)return 1;
				q.push(b[j].to);
			}
	} return 0;
}

inline int dfs(int i,int w){
	if(i==T||!w)return w;
	rg rest=w,f;
	for(rg &j=qi[i];j;j=b[j].next){
		if(b[j].v&&dep[b[j].to]==dep[i]+1){
			f=dfs(b[j].to,min(w,b[j].v));
			if(!f){dep[b[j].to]=-2; continue;}
			b[j].v-=f; b[j^1].v+=f; w-=f;
		} if(!w)break;
	}return rest-w;
}

inline void solve(){
	rg res=0; top=1;
	for(rg i=1;i<=n*2+2;++i) tou[i]=0; //初始化
	for(rg i=1;i<=n;++i){
		if(i!=S&&i!=T)add(i,i+n,1); //一点拆成两点，中间连边
		for(rg j=1;j<=n;++j)
			if(f[i][j])add(i+n,j,1e9); //连边注意是否有加n操作
	} S=S+n;
	while(bfs(n*2+2)) res+=dfs(S,1e9); //DInic
	ans=min(res,ans);
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	rg t=qr();
	while(t--){
		n=qr();m=qr();
		for(rg i=1;i<=n;++i){
			for(rg j=i;j<=n;++j){
				f[i][j]=f[j][i]=0; //初始化
			}
		}
		for(rg i=1;i<=m;++i){
			rg x=qr()+1,y=qr()+1;
			f[x][y]=f[y][x]=1; //邻接矩阵读边
		}
		if(n==0||n==2){puts("0");continue;}
		if(m==0&&n&&n!=2){puts("1");continue;}//特判，这题有点卡细节
		ans=1e9;
		for(rg i=1;i<=n;++i){
			for(rg j=1;j<=n;++j){
				if(f[i][j]||i==j)continue; //注意两个相邻的点不可能通过割点不联通
				S=i;T=j; solve(); //枚举源汇点
			}
		} if(ans==1e9)ans=n; //无论怎么割点图都联通，就输出n
		printf("%d\n",ans);
	}
	return 0;
}

POJ 1966 Cable TV Network （最大流最小割）

$ POJ1966CableTVNetwork $

$ solution: $

$ code: $

推荐阅读

$ POJ₁₉₆₆Cable_TVNetwork $