题号：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; } |