Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5153 Accepted Submission(s): 2477
/* ID: LinKArftc PROG: 1083.cpp LANG: C++ */ #include <map> #include <set> #include <cmath> #include <stack> #include <queue> #include <vector> #include <cstdio> #include <string> #include <utility> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define eps 1e-8 #define randin srand((unsigned int)time(NULL)) #define input freopen("input.txt","r",stdin) #define debug(s) cout << "s = " << s << endl; #define outstars cout << "*************" << endl; const double PI = acos(-1.0); const double e = exp(1.0); const int inf = 0x3f3f3f3f; const int INF = 0x7fffffff; typedef long long ll; const int maxn = 310; int uN, vN; vector <int> vec[maxn]; int linker[maxn]; bool vis[maxn]; bool dfs(int u) { int cnt = vec[u].size(); for (int i = 0; i < cnt; i ++) { int v = vec[u][i]; if (!vis[v]) { vis[v] = true; if (linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } } return false; } int hungry() { memset(linker, -1, sizeof(linker)); int ret = 0; for (int i = 1; i <= uN; i ++) { memset(vis, 0, sizeof(vis)); if (dfs(i)) ret ++; } return ret; } int main() { int T, cnt, u, v; scanf("%d", &T); while (T -- ) { scanf("%d %d", &uN, &vN); for (int i = 1; i <= uN; i ++) vec[i].clear(); for (int i = 1; i <= uN; i ++) { scanf("%d", &cnt); for (int j = 1; j <= cnt; j ++) { scanf("%d", &v); vec[i].push_back(v); } } if (uN == hungry()) printf("YES\n"); else printf("NO\n"); } return 0; }
原文:http://www.cnblogs.com/LinKArftc/p/4908333.html