网络流,关键在建图
建图思路在代码里
/* 最大流SAP 邻接表 思路:基本源于FF方法,给每个顶点设定层次标号,和允许弧。 优化: 1、当前弧优化(重要)。 1、每找到以条增广路回退到断点(常数优化)。 2、层次出现断层,无法得到新流(重要)。 时间复杂度(m*n^2) */ #include <iostream> #include <cstdio> #include <cstring> #include <map> #define ms(a,b) memset(a,b,sizeof a) using namespace std; const int INF = 500; struct node { int v, c, next; } edge[INF*INF * 4]; int pHead[INF*INF], SS, ST, nCnt; void addEdge (int u, int v, int c) { edge[++nCnt].v = v; edge[nCnt].c = c, edge[nCnt].next = pHead[u]; pHead[u] = nCnt; edge[++nCnt].v = u; edge[nCnt].c = 0, edge[nCnt].next = pHead[v]; pHead[v] = nCnt; } int SAP (int pStart, int pEnd, int N) { int numh[INF], h[INF], curEdge[INF], pre[INF]; int cur_flow, flow_ans = 0, u, neck, i, tmp; ms (h, 0); ms (numh, 0); ms (pre, -1); for (i = 0; i <= N; i++) curEdge[i] = pHead[i]; numh[0] = N; u = pStart; while (h[pStart] <= N) { if (u == pEnd) { cur_flow = 1e9; for (i = pStart; i != pEnd; i = edge[curEdge[i]].v) if (cur_flow > edge[curEdge[i]].c) neck = i, cur_flow = edge[curEdge[i]].c; for (i = pStart; i != pEnd; i = edge[curEdge[i]].v) { tmp = curEdge[i]; edge[tmp].c -= cur_flow, edge[tmp ^ 1].c += cur_flow; } flow_ans += cur_flow; u = neck; } for ( i = curEdge[u]; i != 0; i = edge[i].next) if (edge[i].c && h[u] == h[edge[i].v] + 1) break; if (i != 0) { curEdge[u] = i, pre[edge[i].v] = u; u = edge[i].v; } else { if (0 == --numh[h[u]]) continue; curEdge[u] = pHead[u]; for (tmp = N, i = pHead[u]; i != 0; i = edge[i].next) if (edge[i].c) tmp = min (tmp, h[edge[i].v]); h[u] = tmp + 1; ++numh[h[u]]; if (u != pStart) u = pre[u]; } } return flow_ans; } /* poj1087 最大流 建图: 每个种插座和为一个节点,添加源点和汇点 源点到每个存在的插座连一条容量为插座数量的边 统计需要每种插座的数量,作为插座到汇点边的容量 如果有转换器A->B,AB连接一条容量无限的边 */ int k, m, n, tol; int sum[INF], need[INF]; map<string, int> mat; string s,ss; int main() { /* 前向星存边,表头在pHead[],初始化nCnt=1 SS,ST分别为源点和汇点 */ nCnt = 1; cin >> n; for (int i = 1; i <= n; i++) { cin >> s; if (mat.find (s) == mat.end() ) mat[s] = ++tol; sum[tol]++; } cin >> m; for (int i = 1; i <= m; i++) { cin >> ss >> s; if (mat.find (s) == mat.end() ) mat[s] = ++tol; need[mat[s]]++; } cin>>k; for (int i=1;i<=k;i++){ cin>>ss>>s; if (mat.find (s) == mat.end() ) mat[s] = ++tol; if (mat.find (ss) == mat.end() ) mat[ss] = ++tol; int u=mat[s],v=mat[ss]; addEdge(u,v,100); } SS=tol+1,ST=tol+2; for(int i=1;i<=tol;i++){ addEdge(SS,i,sum[i]); addEdge(i,ST,need[i]); } int ans=SAP(SS,ST,ST); cout<<m-ans<<endl; return 0; }