I - 1 or 2
I 一般图最大匹配
思路
一看就是个匹配问题,不过属于多重匹配。我们可以通过拆点,拆成一般匹配。留意到 很小,可以直接把点 拆成 个点,这些点记为
为了保留匹配关系,还需要拆边。对于边:
1、先建立两个中介点
2、将 所有点和 连接 (无向边)
3、将 所有点和 连接 (无向边)
4、连接中介点 (无向边)
例子:
d[ ] = [1, 1, 2]
e[ ] = [(1, 3), (2, 3)]
首先拆点:
p[1] = [1]
p[2] = [2]
p[3] = [3, 4]
然后拆边,并连边:
1、(1, 3): 中介点(5, 6), 连接(1, 5), (3, 6), (4, 6), (5, 6)
2、(2, 3): 中介点(7, 8), 连接(2, 7), (3, 8), (4, 8), (7, 8)
然后在上图跑一般图最大匹配,如果有解,一定所有的点都匹配上。(可画图证明)
代码
#include <iostream> #include <cstring> #include <vector> using namespace std; const int N = 1e3 + 5; const int M = 1e4 + 5; const int inf = 1LL << 30; struct edge { int v, nxt; }; edge e[M << 1]; int head[N], tot; int match[N], pre[N], type[N]; int que[N], qhead, qtail; int ft[N]; inline void init() { memset(match, 0, sizeof(match)); memset(head, -1, sizeof(head)); tot = 0; } inline void addEdge(int u, int v) { e[tot] = edge{v, head[u]}; head[u] = tot++; } inline int find(int x) { return ft[x] == x ? x : ft[x] = find(ft[x]); } inline int getLca(int u, int v) { static int ss[N], tim; tim++; while (ss[u] != tim) { if (u) { ss[u] = tim; u = find(pre[match[u]]); } swap(u, v); } return u; } inline void flower(int x, int y, int p) { while (find(x) != p) { pre[x] = y; y = match[x]; ft[x] = ft[y] = p; if (type[y] == 1) { que[qtail++] = y; type[y] = 2; } x = pre[y]; } } inline bool blossom(int u, int n) { qhead = qtail = 0; for (int i = 1; i <= n; i++) { type[i] = 0; ft[i] = i; } que[qtail++] = u; type[u] = 2; while (qhead != qtail) { u = que[qhead++]; for (int i = head[u]; ~i; i = e[i].nxt) { int v = e[i].v; if (type[v] == 0) { type[v] = 1; pre[v] = u; if (!match[v]) { while (u) { u = match[pre[v]]; match[v] = pre[v]; match[match[v]] = v; v = u; } return true; } else { que[qtail++] = match[v]; type[match[v]] = 2; } } else if (type[v] == 2 && find(u) != find(v)) { int p = getLca(u, v); flower(u, v, p); flower(v, u, p); } } } return false; } int d[N], id[N], od[N]; vector<int> p[N]; int main() { int n, m; while (~scanf("%d%d", &n, &m)) { init(); int tot = 0, ans = 0; memset(id, 0, sizeof(id)); memset(od, 0, sizeof(od)); for (int i = 1; i <= n; i++) { p[i].clear(); scanf("%d", &d[i]); for (int j = 0; j < d[i]; ++j) { id[++tot] = i; p[i].push_back(tot); } } while (m--) { int u, v; scanf("%d%d", &u, &v); int x = ++tot, y = ++tot; for (auto u0 : p[u]) addEdge(u0, x), addEdge(x, u0); for (auto v0 : p[v]) addEdge(v0, y), addEdge(y, v0); addEdge(x, y), addEdge(y, x); od[u]++, od[v]++; } bool err = 0; for (int i = 1; i <= n; i++) { if (od[i] < d[i]) { puts("No"); err = 1; break; } } if (err) continue; for (int i = 1; i <= tot; i++) if (!match[i] && blossom(i, tot)) ans++; int count = 0; for (int i = 1; i <= tot; i++) count += !!(match[i]); if (count == tot) puts("Yes"); else puts("No"); } return 0; }