洛谷P1330《封锁阳光大学》

一月 23, 2019 4567

对子连通图的染色

题目描述

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

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

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

输入输出格式

输入格式

第一行：两个整数N，M

接下来M行：每行两个整数A，B，表示点A到点B之间有道路相连。

输出格式

仅一行：如果河蟹无法封锁所有道路，则输出“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

说明

【数据规模】

1<=N<=10000，1<=M<=100000，任意两点之间最多有一条道路。

解题思路

本题的图可能不为连通图（注意这个坑）

阅读题目，我们得到了这样几条信息：
「当某个点被封锁后，与这个点相连的道路就被封锁了」
「当两只河蟹封锁了相邻的两个点时，他们会发生冲突」
「封锁所有道路并且不发生冲突」

总结一下就是：
「要求每一条边有且仅有一个点被选择，求最少能选择多少点」

然后我们就可以考虑用染色的方法做这一题

我们枚举每一个点，以当前枚举到的起点为根对这个子连通图进行 DFS 染色（因为图可能不联通），答案累加每次染色的最小数量（黑色点数量和白色点数量中最小的）

代码实现

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */
#include <map>
#include <cmath>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)
#define head(a) Head[a].id
#define nowcolor(a) Head[a].color
#define visited(a) Head[a].used
// 这样 define 有助于简化代码

namespace FastIO {
    
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    int n, m, ans;
    int sum0, sum1;
    
    struct Graph {
        static const int MAXN = 10000 + 10;
        static const int MAXM = 100000 + 10;
        
        struct Node {
            int color, used, id;
            // 在一个数组中存储三个数量
            
            Node() { color = used = id = 0; }
        } Head[MAXN];
        
        struct Edge {
            int now, next;
        } edge[MAXM * 2];
        
        int cnt;
        
        inline void addEdge(int prev, int next, bool isR = true) {
            if (isR) { addEdge(next, prev, false); }
            edge[++cnt].now = next;
            edge[cnt].next = head(prev);
            head(prev) = cnt;
        }
        
        inline bool Color(int __id, int nowColor) {
            // 返回 true 为成功染色， false 反之
            if (visited(__id)) {
                return nowcolor(__id) == nowColor;
                // 如果当前被染过不同的颜色，就失败
            }
            visited(__id) = true;
            nowcolor(__id) = nowColor;
            if (nowColor) ++sum1;
            else ++sum0;
            bool __ans = true; 
            for (int e = head(__id); e && __ans; e = edge[e].next) {
                int now = edge[e].now;
                __ans = __ans & Color(now, nowColor ^ 1);
                // 遍历与当前点相连的每一条边并 DFS
            }
            return __ans;
        }
    } g1;
    
    void __EXIT() {
        puts("Impossible");
        exit(0);
    }
}

signed main() {
#define HANDWER_FILE
#ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    using namespace Solution;
    using FastIO::getint;
    n = getint();
    m = getint();
    For (i, 1, m) {
        int prev = getint();
        int next = getint();
        g1.addEdge(prev, next);
    }
    for (int i = 1; i <= n; ++i) {
        if (g1.visited(i)) continue;
        sum0 = sum1 = 0;
        if (!g1.Color(i, 0)) __EXIT();
        ans += std::min(sum0, sum1);
    }
    FastIO::putint(ans, '\n');
    return 0;
}