设一个源点， 到所有设备连一条弧， 容量为1， 然后设一个汇点， 所有插座到汇点连弧， 容量为1， 然后
转换器也连一条弧， 容量为1。 最后最大流就是答案。其中注意节点数要开大一些。
#include#include #include #include #include #include #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 512; //注意总的节点数 struct Edge{ int from, to, cap, flow; Edge(int from, int to, int cap, int flow) : from(from), to(to), cap(cap), flow(flow) {}};vector edges;vector g[MAXN];vector name;int h[MAXN], cur[MAXN], device[MAXN], target[MAXN];int d[MAXN][MAXN], n, m, k, s, t;int from[MAXN], to[MAXN]; int ID(string x){ REP(i, 0, name.size()) if(x == name[i]) return i; name.push_back(x); return name.size() - 1;}void AddEdge(int from, int to, int cap){ edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); g[from].push_back(edges.size() - 2); g[to].push_back(edges.size() - 1);}bool bfs(){ memset(h, 0, sizeof(h)); queue q; q.push(s); h[s] = 1; //不要漏！ while(!q.empty()) { int u = q.front(); q.pop(); REP(i, 0, g[u].size()) { Edge& e = edges[g[u][i]]; if(!h[e.to] && e.cap > e.flow) { h[e.to] = h[u] + 1; q.push(e.to); } } } return h[t];}int dfs(int x, int a){ if(x == t || a == 0) return a; int flow = 0, f; for(int& i = cur[x]; i < g[x].size(); i++) { Edge& e = edges[g[x][i]]; if(h[x] + 1 == h[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) { e.flow += f; edges[g[x][i] ^ 1].flow -= f; flow += f; if((a -= f) == 0) break; } } return flow;}int solve(){ int ret = 0; while(bfs()) memset(cur, 0, sizeof(cur)), ret += dfs(s, 1e9); return ret;}int main(){ int T; scanf("%d", &T); while(T--) { memset(d, 0, sizeof(d)); name.clear(); string k1, k2; scanf("%d", &n); REP(i, 0, n) { cin >> k1; target[i] = ID(k1); } scanf("%d", &m); REP(i, 0, m) { cin >> k1 >> k2; device[i] = ID(k2); } scanf("%d", &k); REP(i, 0, k) { cin >> k1 >> k2; from[i] = ID(k1); to[i] = ID(k2); } int V = name.size(); s = V, t = V + 1; edges.clear(); REP(i, 0, V + 2) g[i].clear(); REP(i, 0, m) AddEdge(s, device[i], 1); REP(i, 0, n) AddEdge(target[i], t, 1); REP(i, 0, k) AddEdge(from[i], to[i], 1e9); printf("%d\n", m - solve()); if(T) puts(""); } return 0;}