题目大意不再敖述,就是赤裸裸的求最大匹配,只是顺手复习下匈牙利算法,呵呵。
代码如下:
#include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<cstdio> #include<vector> #include<queue> #define mem(a , b) memset(a , b , sizeof(a)) using namespace std ; const int MAXN = 300 ; vector<int> G[MAXN]; bool vis[MAXN] ; int linkx[MAXN] , linky[MAXN] ; int n , m ; void chu() { mem(linkx , -1) ; mem(linky , -1) ; int i ; for(i = 0 ; i <= n ; i ++) { G[i].clear() ; } } void init() { int i ; for(i = 1 ; i <= n ; i ++) { int t ; scanf("%d" , &t) ; int j ; for(j = 0 ; j < t ; j ++) { int b ; scanf("%d" , &b) ; G[i].push_back(b) ; } } } int dfs(int u) { int i ; for(i = 0 ; i < G[u].size() ; i ++) { int v ; v = G[u][i] ; if(!vis[v]) { vis[v] = true ; if(linkx[v] == -1 || dfs(linkx[v])) { linkx[v] = u ; linky[u] = v ; return 1 ; } } } return 0 ; } void solve() { int ans = 0 ; int i ; for(i = 1 ; i <= n ; i ++) { if(linky[i] == -1) { mem(vis , 0) ; ans += dfs(i) ; } } printf("%d\n" , ans) ; } int main() { while (scanf("%d%d" , &n , &m) != EOF) { chu() ; init() ; solve() ; } return 0 ; }