s(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 = EG[G[x][i]]; if(d[x]+1 == d[e.to] && (f = dfs(e.to, min(a, e.cap))) > 0) { e.cap -= f; EG[G[x][i]^1].cap += f; flow += f; a -= f; if(a == 0) break; } } return flow; } int Dinic() { int ans = 0; while(bfs()) { memset(cur, 0, sizeof(cur)); ans += dfs(s, INF); } EG.clear(); for(int i = 0; i < n; ++i) G[i].clear(); return ans; } int Find(char* str) { int i; for(i = 2; i < cnt; ++i) if(strcmp(name[i], str) == 0) return i; strcpy(name[i], str); cnt++; return i; } int main() { //freopen("poj_1087.txt", "r", stdin); int m, k; char str1[30], str2[30]; while(~scanf("%d", &n)) { s = 0, t = 1; cnt = 2; //源点和汇点占两个 for(int i = 0; i < n; i++) { scanf("%s", str1); strcpy(name[cnt], str1); //插座不会从父，直接插入 cnt++; addEdge(0, i+2, 1); //建边，源点向每个插座连一条1的边 } scanf("%d", &m); for(int i = 0; i < m; i++) { scanf("%s%s", str1, str2); strcpy(name[cnt], str1); //设备也不会重复。直接插入 cnt++; int u = Find(str2); //扎里插座可能重复，要查找 addEdge(u, cnt-1, 1); //建边，插座向设备连一条容量为1的边 addEdge(cnt-1, 1, 1); //建边，设备到汇点连一条边，容量为1 } scanf("%d", &k); for(int i = 0; i < k; i++) { scanf("%s%s", str1, str2); int u = Find(str1); int v = Find(str2); addEdge(v, u, INF); //建边，后者到前者容量为无穷 } n = cnt; int ans = Dinic(); printf("%d\n", m-ans); } return 0; }
ISAP：
#include
#include
#include
#include
#include
#include
using namespace std; #define maxn 1010 #define INF 0x3f3f3f3f struct Edge { int from, to, cap, flow; }; char name[maxn][30]; vector
EG; vector
G[maxn]; int n, s, t, d[maxn], cur[maxn], p[maxn], num[maxn], mp[maxn][maxn]; bool vis[maxn]; int cnt; void addEdge(int from, int to, int cap) { EG.push_back((Edge){from, to, cap, 0}); EG.push_back((Edge){to, from, 0, 0}); int x = EG.size(); G[from].push_back(x-2); G[to].push_back(x-1); } void bfs() { memset(vis, false, sizeof(vis)); queue
q; vis[t] = true; d[t] = 0; q.push(t); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = 0; i < G[x].size(); i++) { Edge& e = EG[G[x][i]^1]; if(!vis[e.from] && e.cap > e.flow) { vis[e.from] = true; d[e.from] = d[x]+1; q.push(e.from); } } } } int augment() { int x = t, a = INF; while(x != s) { Edge& e = EG[p[x]]; a = min(a, e.cap-e.flow); x = EG[p[x]].from; } x = t; while(x != s) { EG[p[x]].flow += a; EG[p[x]^1].flow -= a; x = EG[p[x]].from; } return a; } int ISAP() { int ans =0; bfs(); memset(num, 0, sizeof(num)); for(int i = 0; i < n; i++) num[d[i]]++; int x = s; memset(cur, 0, sizeof(cur)); while(d[s] < n) { if(x == t) { ans += augment(); x = s; } bool flag = false; for(int i = cur[x]; i < G[x].size(); i++) { Edge& e = EG[G[x][i]]; if(e.cap > e.flow && d[x] == d[e.to]+1) { flag = true; p[e.to] = G[x][i]; cur[x] = i; x = e.to; break; } } if(!flag) { int m = n-1; for(int i = 0; i < G[x].size(); i++) { Edge& e = EG[G[x][i]]; if(e.cap > e.flow) m = min(m, d[e.to]); } if(--num[d[x]] == 0) break; num[d[x] = m+1]++; cur[x] = 0; if(x != s) x = EG[p[x]].from; } } EG.clear(); for(int i = 0; i < n; ++i) G[i].clear(); return ans; } int Find(char* str) { int i; for(i = 2; i < cnt; ++i) if(strcmp(name[i], str) == 0) return i; strcpy(name[i], str); cnt++; return i; } int main() { //freopen("poj_1087.txt", "r", stdin); int m, k; char str1[30], str2[30]; while(~scanf("%d", &n)) { s = 0, t = 1; cnt = 2; for(int i = 0; i < n; i++) { scanf("%s", str1); strcpy(name[cnt], str1); cnt++; addEdge(0, i+2, 1); } scanf("%d", &m); for(int i = 0; i < m; i++) { scanf("%s%s", str1, str2); strcpy(name[cnt], str1); cnt++; int u = Find(str2); addEdge(u, cnt-1, 1); addEdge(cnt-1, 1, 1); } scanf("%d", &k); for(int i = 0; i < k; i++) { scanf("%s%s", str1, str2); int u = Find(str1); int v = Find(str2); addEdge(v, u, INF); } n = cnt; int ans = ISAP(); printf("%d\n", m-ans); } return 0; }
不知为何，总感觉我的Dinic比ISAP要快，基本每次都是，不应该啊。
|