二分图匹配/网络流
把每个学校拆成两个点中间连一条容量下界为2的边，然后求可行流就行了。由于问题特殊，可以用二分图匹配来解决：把每个学校拆成两个点，如果一个学生愿意去一个学校，将这个学生和这个学校拆成的两个点各连一条边。利用匈牙利算法求二分图最大匹配，如果最大匹配数恰好为2k则有解，按照匹配方案输出即可，否则无解。
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 | #include <iostream> using namespace std; struct edge { int v; edge *next; edge(int v,edge *next):v(v),next(next) {} } *e[222]; int match[222]; bool u[222]; bool findAugmentPath(int v) { for(edge *t=e[v];t;t=t->next) if(!u[t->v]) { u[t->v]=true; if(!match[t->v]||findAugmentPath(match[t->v])) { match[t->v]=v; return true; } } return false; } int main() { int n,k,t,p; scanf("%d%d",&n,&k); if(k*2>n) { puts("NO"); return 0; } for(int i=1;i<=n;++i) for(scanf("%d",&t);t;--t) { scanf("%d",&p); e[i]=new edge(p,e[i]); e[i]=new edge(k+p,e[i]); } int total=0; for(int i=1;i<=n;++i) { memset(u,false,sizeof(u)); if(findAugmentPath(i)) ++total; } if(total==(k<<1)) { puts("YES"); for(int i=1;i<=k;++i) printf("2 %d %d\n",match[i],match[k+i]); } else puts("NO"); return 0; } |