[POJ 1274] The Perfect Stall【二分图最大匹配】
Problem:
Time Limit: 1000MS | Memory Limit: 10000K |
Description
Given the preferences of the cows, compute the maximum number of milk-producing assignments of cows to stalls that is possible.
Input
Output
Sample Input
5 5 2 2 5 3 2 3 4 2 1 5 3 1 2 5 1 2
Sample Output
4
Source
Solution:
二分图最大匹配的模板题。从每只奶牛到它愿意待的牛棚连边,求最大匹配即可。
这里我用了代码较简单的匈牙利算法 (Hungarian Algorithm) 来进行最大匹配的求解,时间复杂度为 O(NM)。
Code: O(TNM) [676K, 0MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int N, M; int match[205]; bool vis[205]; struct Edge{ int np; Edge *nxt; }; struct Graph{ Edge *V[205], E[40005]; int tope; inline void clear() {tope = 0, memset(V, 0, sizeof(V));} inline void addedge(int u, int v) {E[++tope].np = v, E[tope].nxt = V[u], V[u] = &E[tope];} } G; inline bool Augmentable(int u){ for(register Edge *ne = G.V[u]; ne; ne = ne->nxt){ if(vis[ne->np]) continue; vis[ne->np] = 1; if(!match[ne->np] || Augmentable(match[ne->np])){ match[ne->np] = u; return 1; } } return 0; } inline int Hungarian(){ int maxmatch = 0; memset(match, 0, sizeof(match)); for(register int i = 1; i <= N; i++){ memset(vis, 0, sizeof(vis)); if(Augmentable(i)) maxmatch++; } return maxmatch; } int main(){ while(scanf("%d%d", &N, &M) != EOF){ G.clear(); for(register int i = 1; i <= N; i++){ int S, K; scanf("%d", &S); while(S--) scanf("%d", &K), G.addedge(i, K); } int maxmatch = Hungarian(); printf("%d\n", maxmatch); } return 0; }
发表评论