POJ - 1087
题意：写这种题目，（有翻译情况下）我的看题时间 = 想 + 敲代码，生无可恋.jpg
一个房间里有很多插座，一种类型的插座只能容纳一种类型的插头，还有一些适配器，使不同类型的插头可以插到某个插座上，适配器还可以嵌套使用，虽然适配器种类不多，但是可以无限提供，使尽可能多的用电器插上插座，那么最后会有几个用电器无法接上插头
思路：明显的，插座和插头一一对应，连边，cap = 1， 适配器可以使a - > b，连边inf，然后加个源点，加个汇点。
但是这题是真的坑，插头种类100，用电器对应的插头100，适配器可能有200个不同型号的玩意出现，还得加上用电器100，所以这个题起码得开到502个点： ）,当然不知为什么我开到300多的时候交g++过了，最后折腾半天才发现这个问题。
而且我开始时有意识到用电器那里可能会有没出现的插头出现（样例嘛），但是根本没意识到适配器也有可能有没出现的插头.....
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <queue> #include <map> using namespace std; const int maxn = 550, maxe = maxn * maxn; const int inf = 0x3f3f3f3f; struct node { int to,next,cap,rev; node(){} node(int a,int b,int c,int d) {to = a; next = b; cap = c; rev = d;} }edge[maxe << 1]; int n , m , k , cnum , edgenum , s, t; int h[maxn] , deg[maxn] , cur[maxn]; char did[maxn][30]; int dy[maxn]; string s1, s2; map<string,int> id; void init() { id.clear(); for(int i = 0; i < maxn; i++) h[i] = -1; cnum = 0; edgenum = 0; } void add(int u,int v,int cap) { edge[edgenum] = node(v,h[u],cap,edgenum+1); h[u] = edgenum++; edge[edgenum] = node(u,h[v],0,edgenum-1); h[v] = edgenum++; } void build() { cin >> k; for(int i = 0; i < k; i++) { cin >> s1 >> s2; if(id.count(s1) == 0) id[s1] = ++cnum; if(id.count(s2) == 0) id[s2] = ++cnum; add(id[s2] , id[s1] , inf); } s = 0, t = cnum + m + 1; for(int i = 1; i <= m; i++) add(i + cnum , t , 1); for(int i = 1; i <= m; i++) add(dy[i] , i + cnum , 1 ); // cout << "cnum " << cnum << endl; } int bfs() { for(int i = s; i <= t; i++) deg[i] = -1; queue<int> q; q.push(s); deg[s] = 0; while(!q.empty()) { int u = q.front(); q.pop(); for(int i = h[u]; ~i ; i = edge[i].next) { int v = edge[i].to,cap = edge[i].cap; if(cap && deg[v] == -1) { deg[v] = deg[u] + 1; q.push(v); } } } return deg[t] != -1; } int dfs(int u,int f) { if(u == t) return f; for(int i = cur[u]; ~i; i = edge[i].next) { cur[u] = i; int v = edge[i].to, cap = edge[i].cap, rev = edge[i].rev; if(cap && deg[v] == deg[u] + 1) { int k = dfs(v,min(f,cap)); if(!k)continue; edge[i].cap -= k; edge[rev].cap += k; return k; } } return 0; } void solve() { int flow = 0; while(bfs()) { for(int i = s; i <= t; i++) cur[i] = h[i]; while(int k = dfs(s,inf)) flow += k; } cout << m-flow << endl; } int main() { std::ios::sync_with_stdio(false); cin >> n; init(); for(int i = 1; i <= n; i++) { cin >> s1; id[s1] = ++cnum; add(0,i,1); } cin >> m; for(int i = 1; i <= m; i++) { cin >> did[i] >> s2; if(id.count(s2) == 0) id[s2] = ++cnum; dy[i] = id[s2]; } build(); solve(); return 0; }
