PROBLEM
https://www.luogu.org/problemnew/show/P1330
ANALYSIS
用不相邻的x 的点,切断所有的边。不存在则输出Impossible 。
有点意思的一个题。直接思考可能比较困难,转化为 用两种颜色对全图所有点染色,且相邻点颜色不同 的话,就可以轻松解决了。
以下为深搜和宽搜两种解法。
SOLUTION
// 152ms / 2.63MB #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; const int N = 11000; vector<int> a[N]; queue<int> q; int n, m, cnt; int c[N], f[2], s; void try_dfs(int x, int w) { c[x] = w; f[w]++; s++; for (auto e : a[x]) { if (!~c[e]) { try_dfs(e, c[x] ^ 1); } else if (c[e] == w) { throw 1; return; } } } int main() { scanf("%d%d", &n, &m); for (int i = 0, e, f; i < m; i++) { scanf("%d%d", &e, &f); a[e].push_back(f); a[f].push_back(e); } memset(c, -1, sizeof(c)); while (s != n) { f[0] = f[1] = 0; for (int i = 1; i <= n; i++) { if (!~c[i]) { try { try_dfs(i, 0); } catch (...) { cout << "Impossible" << endl; return 0; } cnt += min(f[1], f[0]); break; } } } cout << cnt << endl; return 0; }
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; const int N = 11000; vector<int> a[N]; queue<int> q; int n, m, cnt; int c[N], f[2], s; int main() { scanf("%d%d", &n, &m); for (int i = 0, e, f; i < m; i++) { scanf("%d%d", &e, &f); a[e].push_back(f); a[f].push_back(e); } memset(c, -1, sizeof(c)); while (s != n) { f[0] = f[1] = 0; for (int i = 1; i <= n; i++) { if (!~c[i]) { q.push(i); c[i] = 0; f[0]++; s++; break; } } int u; while (!q.empty()) { u = q.front(); for (auto e : a[u]) { if (!~c[e]) { c[e] = c[u] ^ 1; s++; f[c[e]]++; q.push(e); } else if (c[e] == c[u]) { cout << "Impossible" << endl; return 0; } } q.pop(); } cnt += min(f[1], f[0]); } cout << cnt << endl; return 0; }
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; const int N = 11000, M = 110000; queue<int> q; int n, m, cnt, ans; int c[N], f[2], s, head[N]; struct Edge { int to, pre; } e[M * 2]; void inline addedge(Edge e[], int from, int to, int & cnt, int head[]) { e[cnt].to = to; e[cnt].pre = head[from]; head[from] = cnt++; } void try_dfs(int x, int w) { c[x] = w; f[w]++; s++; for (int i = head[x], u; ~i; i = e[i].pre) { u = e[i].to; if (!~c[u]) { try_dfs(u, c[x] ^ 1); } else if (c[u] == w) { throw 1; return; } } } int main() { memset(head, -1, sizeof(head)); memset(e, 0, sizeof(e)); scanf("%d%d", &n, &m); for (int i = 0, q, r; i < m; i++) { scanf("%d%d", &q, &r); addedge(e, q, r, cnt, head); addedge(e, r, q, cnt, head); } memset(c, -1, sizeof(c)); while (s != n) { f[0] = f[1] = 0; for (int i = 1; i <= n; i++) { if (!~c[i]) { try { try_dfs(i, 0); } catch (...) { cout << "Impossible" << endl; return 0; } ans += min(f[1], f[0]); break; } } } cout << ans << endl; return 0; }
本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.