POJ 1850 通常指「Code」或「Password」類問題，實為經典二分圖最大匹配或最小點覆蓋模型。典型場景：N 個鎖、M 把鑰匙，每把鑰匙能開部分鎖，求最多能開多少鎖（每鎖一鑰、每鑰一鎖）。
u-v 表示可匹配S 向左部連容量 1 邊，右部向匯點 T 連容量 1 邊，中間邊容量 1（或 INF）。| 演算法 | 時間複雜度 | 適用規模 |
|---|---|---|
| 匈牙利算法 (DFS) | O(VE) | V≤500, E≤5000 |
| Hopcroft-Karp (BFS+DFS) | O(√V E) | V≤10^4, E≤10^5 |
| Dinic (網絡流通用) | O(E√V) 二分圖 | 同 HK，代碼復用性強 |
vector> adj; // adj[u] = {v...}
vector matchR; // 右部匹配的左部節點
vector vis;
bool dfs(int u) {
for (int v : adj[u]) if (!vis[v]) {
vis[v] = true;
if (matchR[v] == -1 || dfs(matchR[v])) {
matchR[v] = u;
return true;
}
}
return false;
}
int maxMatching(int nLeft) {
matchR.assign(nRight, -1);
int ans = 0;
for (int u=0; u
struct Dinic {
struct Edge { int to, rev, cap; };
vector> g;
vector level, it;
Dinic(int n): g(n), level(n), it(n) {}
void addEdge(int u, int v, int cap) {
g[u].push_back({v, (int)g[v].size(), cap});
g[v].push_back({u, (int)g[u].size()-1, 0});
}
bool bfs(int s, int t) {
fill(level.begin(), level.end(), -1);
queue q; q.push(s); level[s]=0;
while(!q.empty()) {
int u=q.front(); q.pop();
for(auto &e:g[u]) if(e.cap>0 && level[e.to]==-1)
level[e.to]=level[u]+1, q.push(e.to);
}
return level[t]!=-1;
}
int dfs(int u, int t, int f) {
if(u==t) return f;
for(int &i=it[u]; i0 && level[e.to]==level[u]+1) {
int ret=dfs(e.to,t,min(f,e.cap));
if(ret) { e.cap-=ret; g[e.to][e.rev].cap+=ret; return ret; }
}
}
return 0;
}
int maxFlow(int s, int t) {
int flow=0, inf=1e9;
while(bfs(s,t)) {
fill(it.begin(), it.end(), 0);
while(int f=dfs(s,t,inf)) flow+=f;
}
return flow;
}
};
// 使用：
// Dinic dinic(N+M+2);
// S=0, T=N+M+1;
// for(u) dinic.addEdge(S, u, 1);
// for(v) dinic.addEdge(N+v, T, 1);
// for(u,v) dinic.addEdge(u, N+v, 1);
// ans = dinic.maxFlow(S,T);
求最小頂點集合覆蓋所有邊：
1. 求最大匹配
2. 從未匹配左部節點出發，沿非匹配邊→匹配邊交替 DFS/BFS 標記可達節點
3. 最小點覆蓋 = (左部未標記) ∪ (右部標記)
POJ 1850 核心考察二分圖建模與最大流/匹配演算法。掌握匈牙利、HK、Dinic 三種寫法，並理解最小點覆蓋、最大獨立集、最小路徑覆蓋等等價轉化，是演算法競賽圖論必修課。
