这题先用邻接矩阵打了试，TLE，改成邻接表，就过了。。
/* * hdu1054/win.cpp * Created on: 2012-8-14 * Author : ben */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <queue> #include <set> #include <map> #include <stack> #include <string> #include <vector> #include <deque> #include <list> #include <functional> #include <numeric> #include <cctype> using namespace std; const int MAXN = 1600; int N, mymatch[MAXN], temp[MAXN]; vector<int> mymap[MAXN]; bool visited[MAXN]; void init() { for(int i = 0; i < N; i++) { mymap[i].clear(); } } bool dfs(int k) { int t, I; for(int i = 0; i < (int)mymap[k].size(); i++) { I = mymap[k][i]; if(!visited[I]) { visited[I] = true; t = mymatch[I]; mymatch[I] = k; if(t == -1 || dfs(t)) { return true; } mymatch[I] = t; } } return false; } int hungary () { memset(mymatch, -1, sizeof(mymatch)); int ans = 0; for (int i = 0; i < N; i++) { memset(visited, false, sizeof(visited)); if (dfs(i)) { ans++; } } return ans; } bool buildgraph() { int t, k, a; if(scanf("%d", &N) == EOF) { return false; } init(); memset(temp, -1, sizeof(temp)); bool flag = false; for(int i = 0; i < N; i++) { scanf("%d:(%d)", &a, &k); if(!flag) { if(k > 0) { temp[a] = 0; flag = true; } } for(int j = 0; j < k; j++) { scanf("%d", &t); if(temp[a] == 0) { temp[t] = 1; mymap[a].push_back(t); }else{ temp[t] = 0; mymap[t].push_back(a); } } } return true; } int main() { #ifndef ONLINE_JUDGE freopen("data.in", "r", stdin); #endif while(buildgraph()) { printf("%d\n", hungary()); } return 0; }