题意，给你一个基环树，每个边都可以用一个集合中材料之一修建，有m个工人，每一个工人擅长一种材料（可以用这个材料修建边），每个工人只能修一条路。问，可不可以修建出一颗树。
网络流板子，不在环上的边必须修建，在环上的k条边只要修建k-1条即可。为了优先选择非环边，我们将环上的边加以限制，连接到一个虚节点，再从这个虚节点往T一个容量为k-1的边连接。非环边直接往T连接一个容量为1的边。剩下按照模板建图。
这里我采用了暴力找环的方式找到环上的点，然后对于每个边，用两个端点pair<x， y>向一个编号建立双射。记录每个种材料的边的编号。工人直接向这个材料集合中的边（基环树边）建边（网络流边）。
#include<cstdio> #include<iostream> #include<cstring> #include <map> #include <queue> #include <set> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <list> #include <bitset> #include <array> #include <cctype> #include <time.h> #pragma GCC optimize(2) void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); } void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); } void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; } template <typename T> bool bacmp(const T & a, const T & b) { return a > b; } template <typename T> bool pecmp(const T & a, const T & b) { return a < b; } #define ll long long #define ull unsigned ll #define _min(x, y) ((x)>(y)?(y):(x)) #define _max(x, y) ((x)>(y)?(x):(y)) #define max3(x, y, z) ( max( (x), max( (y), (z) ) ) ) #define min3(x, y, z) ( min( (x), min( (y), (z) ) ) ) #define pr(x, y) (make_pair((x), (y))) #define pb(x) push_back(x); using namespace std; const int N = 1e4 + 5; const int M = 1e7+5; const int inf = 0x3f3f3f3f; int he[N], ne[M], ver[M], e[M]; int l[N]; int tot = 1; void add(int x, int y, int w) { ver[++tot] = y; ne[tot] = he[x]; e[tot] = w; he[x] = tot; ver[++tot] = x; ne[tot] = he[y]; e[tot] = 0; he[y] = tot; } bool bfs(int s, int en) { memset(l, 0, sizeof(l)); queue<int> q; q.push(s); l[s] = 1; while(q.size()) { int u = q.front(); q.pop(); if (u == en) return 1; for (int i = he[u]; i; i = ne[i]) { int y = ver[i]; if (!l[y] && e[i]) { l[y] = l[u] + 1; q.push(y); } } } return 0; } int dfs(int u, int MaxFlow, int en) { if (u == en) return MaxFlow; int uflow = 0; for (int i = he[u]; i; i = ne[i]) { int y = ver[i]; if (l[y] == l[u]+1 && e[i]) { int flow = min(e[i], MaxFlow - uflow); flow = dfs(y, flow, en); e[i] -= flow; e[i^1] += flow; uflow += flow; if (uflow == MaxFlow) break; } } if (uflow == 0) l[u] = 0; return uflow; } int Dinic(int s, int t) { int MaxF = 0; while(bfs(s, t)) MaxF += dfs(s, inf, t); return MaxF; } int cntp, ans[N], st[N], top; bool vis[N]; int the[N], tver[N], tne[N], ttot; void tadd(int x, int y) { tver[++ttot] = y; tne[ttot] = the[x]; the[x] = ttot; } bool dfs_w(int cur, int fa) { st[++top] = cur; vis[cur] = 1; for (int i = the[cur]; i; i = tne[i]) { int y = tver[i]; if (y == fa) continue; if (vis[y]) { while(st[top] != y) ans[++cntp] = st[top--]; ans[++cntp] = y; return 1; } else if (dfs_w(y, cur)) return 1; } top--; return 0; } map<pair<int, int>, int> mp; map<int, vector<int> > col; pair<int, int> cc[N]; int main() { int n, m; scanf("%d%d", &n, &m); int cnt = 0; for (int i = 1; i <= n; i++) { int a; scanf("%d", &a); tadd(i, a); tadd(a, i); mp[pr(min(i, a), max(a, i))] = ++cnt; cc[cnt] = pr(i, a); int k = 0; scanf("%d", &k); while(k--) { int te; scanf("%d", &te); col[te].pb(cnt); } } dfs_w(1, 0); for (int i = 1; i <= cntp; i++) { int l = ans[i], r = ans[(i) % cntp + 1]; if (l > r) swap(l, r); mp[pr(l, r)] = -mp[pr(l, r)]; } int vur = ++cnt; int s = 0, t = cnt + m + 1; add(vur, t, cntp - 1); for (auto x : mp) { if (x.second < 0) add(-x.second, vur, 1); else add(x.second, t, 1); } for (int i = 1; i <= m; i++) { int cl; scanf("%d", &cl); for (int x : col[cl]) add(i+cnt, x, 1); add(s, i+cnt, 1); } int ans = Dinic(s, t); if (ans == n - 1) { //cout << ans << endl; for (int i = cnt + 1; i <= cnt + m; i++) { bool flag = 0; for (int j = he[i]; j; j = ne[j]) { if (!e[j] && ver[j] != s) { flag = 1; printf("%d %d\n", cc[ver[j]].first, cc[ver[j]].second); break; } } if (!flag) puts("0 0"); } } else puts("-1"); return 0; }