Tang-Dreamoon's Blog

poj 1966 点连通度

发表于 | 分类于 ， ，

特此嘲讽网上诸多垃圾题解，你们许多都是错的

　　题目链接：poj 1966

　　题意：求最少删去几个点使得一个无向图不连通。

　　题解：首先让我们先来学习一下边连通度好了。虽然题目并不会给我们一个源点或者汇点，但是显然图中的任何一个点，在图被断开后不是在 S 集合中就是在 T 集合中；而对于每一对点，显然不是在同一集合就是在两个集合当中。所以我们可以随便确定一个点作为源点，然后枚举汇点，把所有的最小割取一个 m i n 就好了。

　　　　　那么，点连通度又该如何求呢？在这里我们可以利用一个很重要的思想就是点边转化的思想，在网络流中我们常常把点的一些信息通过拆点反应在边上，同样可以把边的信息转化到点上。进而通过求一个特殊的边连通度，来表示点连通度。所以在这里我们对于每一个点进行拆点操作：入点向出点连一条容量为一的边，表示如果要割掉这个点就有一的代价。而把原图中所有的边( U , V )我们从 U 的出点向 V 的入点连一条容量为﹢ ∞ 的边目的是防割（显然不能割掉“边”）。然后枚举源点和汇点开始跑最小割就好了。在此我们把“源点”的出点当做源点，“汇点”的入点当做汇点。

　　我思故我在：在这里我一定要强烈指责网上许多错误的题解，自以为少了一重枚举，其实是错误的做法。那就是许多人像求边连通度一样随意固定一个源点然后枚举汇点，这是十分错误的做法！！！因为当我们枚举了两个点的时候就意味着我们要在这一次求最小割的时候保留下来这两个点，而且显然我们并不知道哪个点会在最后的割集中，如果你不小心将源点设成了一个在最终割集中的点，那么一定是错的喽。至于网上的众多题解，不过是 p o j 数据水罢了，大家千万不要无脑模仿啊！~~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n,m;
int tot=0;
struct table{
	int to,id;
};
vector<table> ve[5000];
int deep[5000];
int f[500000];
inline int min(int a,int b)
{
	return a < b ? a : b ;
}
bool bfs(int a,int b)
{
	memset(deep,-1,sizeof(deep));
	queue<int> q;
	deep[a]=0;
	q.push(a);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=0;i<ve[x].size();i++)
		{
			table y=ve[x][i];
			if(deep[y.to]==-1&&f[y.id]>0)
			{
				deep[y.to]=deep[x]+1;
				q.push(y.to);
			}
		}
	}
	return deep[b]!=-1;
}
int zeng(int a,int b,int c)
{
	if(a==c) return b;
	int r=0,t;
	for(int i=0;i<ve[a].size()&&b>r;i++)
	{
		table y=ve[a][i];
		if(deep[y.to]==deep[a]+1&&f[y.id]>0)
		{
			t=zeng(y.to,min(b-r,f[y.id]),c);
			r+=t,f[y.id]-=t,f[y.id^1]+=t;
		}
	}
	if(!r) deep[a]=-1;
	return r;
}
int dinic(int st,int ed)
{
	int ans=0,now;
	while(bfs(st,ed))
	{
		while(now=zeng(st,247483647,ed)) ans+=now;
	}
	return ans;
}
int main()
{
//	cout<<(sizeof(deep)+sizeof(f)+sizeof(love))<<endl;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=0;i<n;i++)
		{
			ve[i].push_back((table){i+n,tot}),f[tot++]=1;
			ve[i+n].push_back((table){i,tot}),f[tot++]=0;
		}
		for(int i=1;i<=m;i++)
		{
			int x=0,y=0;
			char c=getchar();
			while(c<'0'||c>'9') c=getchar();
			while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
			while(c<'0'||c>'9') c=getchar();
			while(c>='0'&&c<='9') y=y*10+c-'0',c=getchar();
			ve[x+n].push_back((table){y,tot}),f[tot++]=247483647;
			ve[y].push_back((table){x+n,tot}),f[tot++]=0;
			ve[y+n].push_back((table){x,tot}),f[tot++]=247483647;
			ve[x].push_back((table){y+n,tot}),f[tot++]=0;
		}
		int ans=247483647;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(i==j) continue;
				ans=min(ans,dinic(i+n,j));
				for(int i=0;i<tot;i+=2)  
	            {  
	                f[i]+=f[i^1];  
	                f[i^1]=0;  
	            }
			}
		}
		if(ans==247483647) ans=n;
		printf("%d\n",ans);
		tot=0;
		for(int i=0;i<=2*n;i++)
			ve[i].clear();
	}
	return 0;
}