题意
判定给出的二分图是否存在完备匹配。
思路
按照题目要求直接建立二分路，之后运行最大匹配算法，出答案。
代码
使用了匈牙利算法。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; #pragma mark - Hungary Algorithm for BiGraph Matching DFS Version (BGM_H) const int MAXN = 305; const int INF = 0x3f3f3f3f; struct Node{ vector<int> to; } X[MAXN],Y[MAXN];//index starts from 0 int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y] bool ap_vis[MAXN];//vis marking array for augment path searching void init(){ for (int i = 0; i < MAXN; i++) { X[i].to.clear(); Y[i].to.clear(); } memset(matchX, -1, sizeof(matchX)); memset(matchY, -1, sizeof(matchY)); } int ap_dfs(int u){ for (int i = 0; i < X[u].to.size(); i++) { int v = X[u].to[i]; if (!ap_vis[v]) { ap_vis[v] = true; if (matchY[v] == -1 || ap_dfs(matchY[v])) { matchX[u] = v; matchY[v] = u; return 1; } } } return 0; } int BGM_H(){ int ret = 0; memset(matchX, -1, sizeof(matchX)); memset(matchY, -1, sizeof(matchY)); for (int i = 1; i <= nx; i++) { if (matchX[i] == -1) { memset(ap_vis, false, sizeof(ap_vis)); ret += ap_dfs(i); } } return ret; } #pragma mark - int main(){ int caseCnt; scanf(" %d",&caseCnt); for (int d = 1; d <= caseCnt; d++) { int p,n; scanf(" %d %d",&p,&n); init(); nx = p; ny = n; for (int i = 1; i <= p; i++) { int cnt; scanf(" %d",&cnt); for (int j = 1; j <= cnt; j++) { int tmp; scanf(" %d",&tmp); X[i].to.push_back(tmp); } } int res = BGM_H(); //cerr << res << endl; if (res == p) { cout << "YES" << endl; }else{ cout << "NO" << endl; } } } |
