Algorithm - Problem - 封锁阳光大学

封锁阳光大学 洛谷 P1330

问题描述

曹是一只爱刷街的老曹,暑假期间,他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹,感到不爽。河蟹决定封锁阳光大学,不让曹刷街。

阳光大学的校园是一张由 NN 个点构成的无向图,NN 个点之间由 MM 条道路连接。每只河蟹可以对一个点进行封锁,当某个点被封锁后,与这个点相连的道路就被封锁了,曹就无法在与这些道路上刷街了。非常悲剧的一点是,河蟹是一种不和谐的生物,当两只河蟹封锁了相邻的两个点时,他们会发生冲突。

询问:最少需要多少只河蟹,可以封锁所有道路并且不发生冲突。

输入

第一行:两个整数NN, MM

接下来 MM 行:每行两个整数AA,BB,表示点 AA 到点 BB 之间有道路相连。

输出

仅一行:如果河蟹无法封锁所有道路,则输出“Impossible”,否则输出一个整数,表示最少需要多少只河蟹。

样例输入1
1
2
3
4
3 3
1 2
1 3
2 3
样例输出1
1
Impossible
样例输入2
1
2
3
3 2
1 2
2 3
样例输出2
1
1

染色

分析

由题意分析可知,图上的每条边只能被占领一次,而边的占领都源于点的占领,因此一条边所连接的两个点中,只有一个能被占领.
基于这样的一个事实,我们可以先标记某个点为可行,然后将其相邻的点标记为不可行,再将后面那些点的相邻的点标记为可行.
统计所有可行点的个数,即可求解.
根据对称性,将可行不可行交换,也是所要的解.
因为要求最少的占领数量,最终答案就是可行点和不可行点数目的较小者.
可行不可行看成染色过程的两种颜色.
染色
考虑到本题有可能出现非连通图情形,因此采用 DFS 算法来染色,并使用 vis 数组确保唯一访问,将每个连通分量的答案加起来即可.
如果输入数据无解,那么会出现已经访问过的点的颜色和现在要染的颜色不一致的情况.

代码
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
#include <iostream>
#define MAXM (100000+5)
#define MAXN (10000+5)
#define MIN(a,b) (((a)<(b))?(a):(b))
bool mat[MAXN][MAXN];
bool vis[MAXM];
bool c[MAXM];
int n, m, u, v;
int t = 0;
int t1 = 0, t2 = 0;
bool dfs(int x, bool s)
{
if(vis[x] && c[x] != s) return false;
if(vis[x] && c[x] == s) return true;
c[x] = s;
if(s) t1++;
else t2++;
vis[x] = true;
for(int i = 1; i <= n; i++)
{
if(mat[x][i])
{
if(!dfs(i, !s))
{
return false;
}
}
}
return true;
}
int main()
{
bool flag = true;
std::cin >> n >> m;
for(int i = 1; i <= m; i++)
{
std::cin >> u >> v;
mat[u][v] = true;
mat[v][u] = true;
}
for(int i = 1; i <= n; i++)
{
t1 = 0;
t2 = 0;
if(!vis[i])
{
if(dfs(i, 1))
{
t += MIN(t1, t2);
}
else
{
flag = false;
break;
}
}
}
if(flag) std::cout << t;
else std::cout << "Impossible";
}