题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=3081
题意
有n对男女 女生去选男朋友
如果女生从来没和那个男生吵架 那么那个男生就可以当她男朋友 女生也可以选择从来没和自己闺蜜吵过架的男生当男朋友
如果 女生A和女生B是闺蜜 女生A和男生C吵过架 但是女生B和男生C从来没吵过架
那么女生A是可以选择男生C当男朋友的。
看来 讨好闺蜜是一件多么重要的事情。。
T T组数据
给出 n, m, f
有N对男女， m对从未吵架关系 f 对闺蜜关系
思路
先将m对关系 用二分图存下来
然后f对闺蜜关系 先用并查集并起来 并完后，跑一下Flyod
然后去二分匹配 匹配完一次 将匹配过的边删去 再去匹配，如果还能匹配成功 继续删边 继续匹配 匹配的次数 就是答案
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); #define fi first #define se second //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double EI = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 7e3 + 5e2 + 10; const int MOD = 6; const int MAXN = 110; int uN, vN;//u,v的数目，使用前面必须赋值 int g[MAXN][MAXN];//邻接矩阵 int linker[MAXN]; bool used[MAXN]; bool dfs(int u) { for (int v = 0; v < vN; v++) if (g[u][v] && !used[v]) { used[v] = true; if (linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } return false; } int hungary() { int res = 0; memset(linker, -1, sizeof(linker)); for (int u = 0; u < uN; u++) { memset(used, false, sizeof(used)); if (dfs(u))res++; } return res; } int pre[MAXN]; int n, m, f; int find(int x) { while (x != pre[x]) x = pre[x]; return x; } void join(int x, int y) { int fx = find(x), fy = find(y); if (fx != fy) pre[fx] = fy; } void Flyod() { for (int i = 0; i < n; i++) { for (int k = 0; k < n; k++) { if (find(i) == find(k)) { for (int j = 0; j < n; j++) g[i][j] = g[k][j] = (g[i][j] || g[k][j]); } } } } void clear() { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) g[i][j] = 0; for (int i = 0; i < n; i++) pre[i] = i; } int main() { int t; cin >> t; while (t--) { scanf("%d%d%d", &n, &m, &f); clear(); int x, y; for (int i = 0; i < m; i++) { scanf("%d%d", &x, &y); x--, y--; g[x][y] = 1; } for (int i = 0; i < f; i++) { scanf("%d%d", &x, &y); x--, y--; join(x, y); } Flyod(); int tot = 0; uN = vN = n; int vis; while (true) { vis = hungary(); if (vis != n) break; tot++; for (int i = 0; i < n; i++) g[linker[i]][i] = 0; } cout << tot << endl; } }转载于:https://www.cnblogs.com/Dup4/p/9433079.html
