POJ 1469 ZOJ1140 二分匹配裸题
很裸，左点阵n，右点阵m 问最大匹配是否为n
#include <cstdio>#include <cstring>#include <vector>using namespace std;vector <int> edge[103];int pre[303];bool vis[303];int n, m;bool dfs(int u) {for(int i = 0; i < (int)edge[u].size(); i++) {int v = edge[u][i];if(vis[v]) continue;vis[v] = 1;if(pre[v] == -1 || dfs(pre[v])) {pre[v] = u;return 1;}}return 0;}int main() {int i, cas;scanf("%d", &cas);while(cas--) {scanf("%d%d", &n, &m);int x, tp;for(i = 0; i < n; i++)edge[i].clear();for(i = 0; i < n; i++) {scanf("%d", &tp);while(tp--) {scanf("%d", &x);edge[i].push_back(--x);}}memset(pre, -1, sizeof(int)*m);int cnt = 0;for(i = 0; i < n; i++) {memset(vis, 0, sizeof(bool)*m);if(dfs(i)) cnt++;if(cnt == n) break;}printf("%s\n", cnt==n ? "YES" : "NO");}return 0;}