网友投稿 769 2022-11-28 19:20:29
UVA - 753 A Plug for UNIX——二分图最大基数匹配
用了ek最大流+flody闭包，然后瞎写一通
#include #include #include #include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 1e5;struct Data { string s; int link, id;}data1[110], data2[110];map ma;int G[1000][1000];struct Edge { int from, to, cap, flow; Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}};struct EdmondsKarp { int n, m; vector edges; vector G[maxn]; int p[maxn], a[maxn]; void init(int x) { n = x; edges.clear(); for (int i = 0; i < n; i++) G[i].clear(); } void addedge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } int maxflow(int s, int t) { int flow = 0; while (true) { memset(a, 0, sizeof(a)); queue q; p[s] = 0, a[s] = INF; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (!a[e.to] && e.cap > e.flow) { p[e.to] = G[u][i]; a[e.to] = min(a[u], e.cap - e.flow); q.push(e.to); } } if (a[t]) break; } if (!a[t]) break; for (int u = t; u != s; u = edges[p[u]].from) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; } flow += a[t]; } return flow; }}ek;int main() { int T, flag = 0; scanf("%d", &T); while (T--) { ma.clear(); memset(G, 0, sizeof(G)); int cnt = 0; int n; scanf("%d", &n); for (int i = 0; i < n; i++) { cin >> data1[i].s; if (!ma[data1[i].s]) ma[data1[i].s] = ++cnt; data1[i].id = ma[data1[i].s]; } int m; scanf("%d", &m); for (int i = 0; i < m; i++) { string s; cin >> data2[i].s >> s; if (!ma[s]) ma[s] = ++cnt; if (!ma[data2[i].s]) ma[data2[i].s] = ++cnt; int id1 = ma[s], id2 = ma[data2[i].s]; data2[i].link = id1, data2[i].id = id2; } int k; scanf("%d", &k); for (int i = 0; i < k; i++) { string s1, s2; cin >> s1 >> s2; if (!ma[s1]) ma[s1] = ++cnt; if (!ma[s2]) ma[s2] = ++cnt; int id1 = ma[s1], id2 = ma[s2]; G[id1][id2] = 1; } for (int t = 0; t <= cnt; t++) { for (int i = 0; i <= cnt; i++) { for (int j = 0; j <= cnt; j++) { G[i][j] = G[i][j] || (G[i][t] && G[t][j]); } } } int s = ++cnt; int t = ++cnt; ek.init(cnt + 10); for (int i = 0; i < n; i++) ek.addedge(s, data1[i].id, 1); for (int i = 0; i < m; i++) ek.addedge(data2[i].id, t, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int id = data1[i].id; if (data2[j].link == id || G[data2[j].link][id] || G[id][data2[j].link]) ek.addedge(id, data2[j].id, INF); } } if (flag++) printf("\n"); printf("%d\n", m - ek.maxflow(s, t)); }}
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
