日度归档：2 8 月, 2017

洛谷 封锁阳光大学

发表评论

题号：1330
这个属于搜索中的染色问题，之前不会，以后要多多学习。

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
#include<iostream>
#include<algorithm>
#include<list>
#include<queue>
using namespace std;
list<int> edge[100005];
int n, m;
int point[100005];
inline int color(int x){
    if (x == 1)return 2;
    else return 1;
}
int BFS(int i){
    int cnter1 = 0, cnter2 = 0;
    queue<pair<int, int>> q;
    q.push(pair<int, int>(i, 1));
    while (!q.empty()){
        pair<int, int> cur = q.front(); q.pop();
        if (point[cur.first] != 0){
            if (point[cur.first] != cur.second)return -1;
            continue;
        }
        point[cur.first] = cur.second;
        if (cur.second == 1)cnter1++;
        if (cur.second == 2)cnter2++;
        for (auto iter = edge[cur.first].begin(); iter != edge[cur.first].end(); iter++){
            q.push(pair<int, int>((*iter), color(cur.second)));
        }
    }
    return cnter1 < cnter2 ? cnter1 : cnter2;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    int sum = 0;
    for (int i = 1; i <= n; i++){
        if (point[i] == 0){
            int t=BFS(i);
            if (t == -1){
                cout << "Impossible";
                return 0;
            }
            else
                sum += t;
        }
    }
    cout << sum;
}

20180806：基本上自己做出来了！！哈哈！有个小细节忽略了：是每个互不联通子图分别找出最小值加起来，不是整图统计。

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n, m;
vector<int> edges[10005];
int color[10005];
inline int getOppoColor(int x) {
    if (x == 1)return 2;
    else return 1;
}
int BFS(int s) {
    int color1 = 0, color2 = 0;
    queue<int> q;
    color[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int node = q.front();
        if (color[node] == 1)color1++;
        else color2++;
        q.pop();
        for (int i = 0; i < edges[node].size(); i++) {
            if (color[edges[node][i]] == 0) {
                color[edges[node][i]] = getOppoColor(color[node]);
                q.push(edges[node][i]);
            }
            else if (color[edges[node][i]] == color[node]) {
                return 0;
            }
        }
    }
    return min(color1, color2);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    int cnter = 0;
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0 && edges[i].size() != 0) {
            int cur = BFS(i);
            if (cur == 0) {
                cout << "Impossible";
                return 0;
            }
            cnter += cur;
        }
    }

    cout << cnter;
}