水题
注意建图,转换器是无限的。另外不能建设备。会t
##代码如下
#include<iostream> #include<algorithm> #include<queue> #include<cstdio> #include<set> #include<map> using namespace std; const int max_n = 500; const int max_m = 1000; const int inf = 2e9; struct edge { int to, cap, rev, next; }E[max_m * 2]; int head[max_n]; int cnt = 1; void add(int from, int to, int cap) { E[cnt].to = to; E[cnt].cap = cap; E[cnt].rev = cnt + 1; E[cnt].next = head[from]; head[from] = cnt++; E[cnt].to = from; E[cnt].cap = 0; E[cnt].rev = cnt - 1; E[cnt].next = head[to]; head[to] = cnt++; } int iter[max_n]; int dist[max_n]; bool searchpath(int s, int t) { fill(dist, dist + max_n, -1); queue<int> que;dist[s] = 0; que.push(s); while (!que.empty()) { int u = que.front();que.pop(); for (int i = head[u];i;i = E[i].next) { edge& e = E[i]; if (dist[e.to] != -1 || e.cap == 0)continue; dist[e.to] = dist[u] + 1; que.push(e.to); } }return dist[t] != -1; } int matchpath(int u, int t, int f) { if (u == t)return f; for (int& i = iter[u];i;i = E[i].next) { edge& e = E[i]; if (dist[e.to] <= dist[u] || e.cap <= 0)continue; int d = matchpath(e.to, t, min(e.cap, f)); if (d > 0) { e.cap -= d; E[e.rev].cap += d; return d; } }return false; } int dinic(int s, int t) { int flow = 0;int f; while (searchpath(s, t)) { for (int i = 1;i < max_n;i++)iter[i] = head[i]; while (f = matchpath(s, t, inf)) flow += f; }return flow; } int n, m, k; string a[max_n], b[max_n], c[max_n][2]; string d[max_n]; int main() { ios::sync_with_stdio(0); cin >> n; map<string, int> mp;int tot = 0; for (int i = 1;i <= n;++i) { cin >> a[i]; if (mp.find(a[i]) == mp.end())mp[a[i]] = ++tot; }cin >> m; for (int i = 1;i <= m;++i) { cin >> d[i] >> b[i]; if (mp.find(b[i]) == mp.end())mp[b[i]] = ++tot; }cin >> k; for (int i = 1;i <= k;++i) { cin >> c[i][0] >> c[i][1]; if (mp.find(c[i][0]) == mp.end())mp[c[i][0]] = ++tot; if (mp.find(c[i][1]) == mp.end())mp[c[i][1]] = ++tot; }int start = tot + 1;int ed = start + 1; for (int i = 1;i <= n;++i)add(start, mp[a[i]], 1); for (int i = 1;i <= m;++i) { add(mp[b[i]], ed, 1); }for (int i = 1;i <= k;++i) add(mp[c[i][1]], mp[c[i][0]], inf); cout << m - dinic(start, ed) << endl; }