题意：
有编号为1~n的女生和1~n的男生配对
首先输入m组，a,b表示编号为a的女生没有和编号为b的男生吵过架
然后输入f组，c,d表示编号为c的女生和编号为d的女生是朋友
进行配对的要求满足其一即可。
1.a女生没有和b男生吵过架
2.a女生的朋友和b男生没有吵过架
每进行一轮之后重新配对，配过得一对不可再配，问最多能进行几轮。
解析：
一看就是先用并查集或者Floyd 都行
然后这类题目都是二分那个要求的值 然后源点s向X集建立权值为mid的边 X集向Y集建立权值 为1的边 Y集向汇点t建立权值为mid的边 跑最大流然后不断更改mid 使之最大或最小即可
二分游戏的轮数 设为mid
s 到每个女孩 建边 权值为mid 女孩到每个可以配对的男孩建边 权值为 1 男孩到t建边权值为mid
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <cctype> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <bitset> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define pd(a) printf("%d ", a); #define plld(a) printf("%lld ", a); #define pc(a) printf("%c ", a); #define ps(a) printf("%s ", a); #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 100100, INF = 0x7fffffff, LL_INF = 0x7fffffffffffffff; int n, m, z, s, t, cnt; int f[maxn], re[110][110]; int d[maxn], cur[maxn], head[maxn]; struct node { int u, v, c, next; }Node[maxn << 1]; void add_(int u, int v, int c) { Node[cnt].u = u; Node[cnt].v = v; Node[cnt].c = c; Node[cnt].next = head[u]; head[u] = cnt++; } void add(int u, int v, int c) { add_(u, v, c); add_(v, u, 0); } bool bfs() { queue<int> Q; mem(d, 0); Q.push(s); d[s] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i = head[u]; i != -1; i = Node[i].next) { node e = Node[i]; if(!d[e.v] && e.c > 0) { d[e.v] = d[u] + 1; Q.push(e.v); if(e.v == t) return 1; } } } return d[t] != 0; } int dfs(int u, int cap) { int ret = 0; if(u == t || cap == 0) return cap; for(int &i = cur[u]; i != -1; i = Node[i].next) { node e = Node[i]; if(d[e.v] == d[u] + 1 && e.c > 0) { int V = dfs(e.v, min(cap, e.c)); Node[i].c -= V; Node[i ^ 1].c += V; ret += V; cap -= V; if(cap == 0) break; } } if(cap > 0) d[u] = -1; return ret; } int Dinic() { int ans = 0; while(bfs()) { memcpy(cur, head, sizeof(head)); ans += dfs(s, INF); } return ans; } int find(int x) { return f[x] == x ? x : (f[x] = find(f[x])); } void build(int mid) { for(int i = 1; i <= n; i++) { add(s, i, mid); add(n + i, t, mid); } for(int i = 1; i <= n; i++) for(int k = n + 1; k <= n * 2; k++) if(re[i][k]) add(i, k, 1); } void init() { for(int i = 1; i < maxn; i++) f[i] = i; mem(re, 0); mem(head, -1); cnt = 0; } int main() { int T; rd(T); while(T--) { init(); int a, b; rd(n), rd(m), rd(z); s = 0, t = n * 2 + 1; for(int i = 0; i < m; i++) { rd(a), rd(b); b += n; re[a][b] = re[b][a] = 1; } for(int i = 0; i < z; i++) { rd(a), rd(b); int r = find(a); int l = find(b); if(r != l) f[l] = r; } for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { if(find(i) == find(j)) for(int k = n + 1; k <= n * 2; k++) re[i][k] = re[j][k] = (re[i][k] || re[j][k]); } } int x = 0, y = 100; while(x <= y) { mem(head, -1); cnt = 0; int mid = x + (y - x) / 2; build(mid); if(Dinic() == mid * n) x = mid + 1; else y = mid - 1; } pd(y); } return 0; }