题目链接：
题意：
给定n个人，m个终点
以下n行表示每一个人能够去m个点。
每一个人仅仅能去一个点。
输出随意一个方案使得每一个点至少有2个人到达。
若存在输出m行，第一个数字表示i这个点来了几个人，后面是人的点标。
思路：
建一个二部图n-m，然后m到汇点限流2。推断是否满流，若不满流就无解。
若满流则其它的人随便走。
#include#include #include #include #include #include #include using namespace std;typedef int ll;#define N 420#define M 100000#define inf 107374182struct Edge{ ll from, to, cap, nex;}edge[M*2];ll head[N], edgenum;void add(ll u, ll v, ll cap, ll rw = 0){ Edge E = {u, v, cap, head[u]}; edge[edgenum] = E; head[u] = edgenum ++; Edge E2 = {v, u, rw, head[v]}; edge[edgenum] = E2; head[v] = edgenum ++;}ll sign[N];bool BFS(ll from, ll to){ memset(sign, -1, sizeof sign); sign[from] = 0; queue q; q.push(from); while( !q.empty() ) { ll u = q.front(); q.pop(); for(ll i = head[u]; ~i; i = edge[i].nex) { ll v = edge[i].to; if(sign[v] == -1 && edge[i].cap){ sign[v] = sign[u] +1, q.push(v); if(sign[to] != -1) return true; } } } return false;}ll Stack[N], top, cur[N];ll Dinic(ll from, ll to){ ll ans = 0; while( BFS(from, to) ) { memcpy(cur, head, sizeof head); ll u = from; top = 0; while(1) { if(u==to) { ll flow = inf, loc; for(ll i = 0; i < top; i++) if(flow > edge[Stack[i]].cap) { flow = edge[Stack[i]].cap; loc = i; } for(ll i = 0; i < top; i++) { edge[ Stack[i] ].cap -= flow; edge[Stack[i]^1].cap += flow; } ans += flow; top = loc; u = edge[Stack[top]].from; } for(ll i = cur[u]; ~i; cur[u] = i = edge[i].nex) if(edge[i].cap && (sign[u]+1 == sign[edge[i].to]))break; if(cur[u] != -1){ Stack[top++] = cur[u]; u = edge[cur[u]].to; } else { if(top==0)break; sign[u] = -1; u = edge[Stack[--top]].from; } } } return ans;}void init(){memset(head, -1, sizeof head); edgenum = 0;}int n, m, from, to, to2, ans[N], G[N];vector D[N];bool solve(){ from = 0; to = n+m+1; to2 = to+1; init(); for(int i = 1; i <= n; i++) { G[i] = -1; add(from, i, 1); int x, y; scanf("%d",&x); while(x--){ scanf("%d",&y); G[i] = y; add(i, n+y, 1); } } for(int i = 1; i <= m; i++) add(n+i, to, 2); add(to, to2, inf); if(m*2 > n || Dinic(from, to2) < m*2)return false; puts("YES"); for(int i = 1; i <= n; i++) { ans[i] = -1; for(int j = head[i]; ~j; j = edge[j].nex) { if(edge[j].cap==0 && edge[j].to != from) { ans[i] = edge[j].to-n; D[edge[j].to-n].push_back(i); break; } } if(ans[i]==-1 && G[i]!=-1) D[G[i]].push_back(i); } for(int i = 1; i <= m; i++) { printf("%d", D[i].size()); for(int j = 0; j < D[i].size(); j++) printf(" %d", D[i][j]); puts(""); } return true;}int main(){ while(~scanf("%d %d",&n,&m)){ if(solve()==false)puts("NO"); for(int i = 1; i <= m; i++)D[i].clear(); } return 0;}/*5 21 11 21 11 11 15 21 11 21 11 12 1 2*/