题意：
有N个学生，可以被分配去M个学校，给出哪些学生能去哪些学校，
求一个解：每间学校都分到>=2个学生的方案。
分析：
cai0715用上下界做。。。其实不用这么麻烦= =
连边(s,i,1) i为学生
连边(i,j,1) j为学校
连边(j,T,2)
然后最大流即可。
插曲：
PE到2B，原来SGU的PE有可能是Runtime ERROR。原来我数组没开够
code：
#include
struct gtp{int x,y,c,next,op;}g[N];
int e,n,m,ls[N],flow,cur[N],fa[N],d[N],num[N],list[N][3];
void add(int x,int y,int c){
e++;
g[e].x=x;
g[e].y=y;
g[e].c=c;
g[e].next=ls[x];
ls[x]=e;
g[e].op=e+1;
e++;
g[e].x=y;
g[e].y=x;
g[e].c=0;
g[e].next=ls[y];
ls[y]=e;
g[e].op=e-1;
}
void init(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
add(0,i,1);
int num,x;
scanf("%d",&num);
for (int j=1;j<=num;j++){
scanf("%d",&x);
add(i,n+x,1);
}
}
for (int i=1;i<=m;i++) add(i+n,n+m+1,2);
}
void relabel(int k){
int min=n+m+1;
cur[k]=ls[k];
for (int t=ls[k];t!=0;t=g[t].next)
if (g[t].c>0 && d[g[t].y]
}
void change(){
int nf=2;
for (int i=n+m+1;i!=0;i=g[fa[i]].x)
if (g[fa[i]].c
for (int i=n+m+1;i!=0;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
}
void sap(){
num[0]=n+m+2;
for (int i=0;i<=n+m+1;i++) cur[i]=ls[i];
int i=0;
while (d[0]
if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
cur[i]=g[cur[i]].next;
}
if (cur[i]==0){
num[d[i]]–;
if (num[d[i]]==0) break;
relabel(i);
num[d[i]]++;
if (i!=0) i=g[fa[i]].x;
}
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==n+m+1){
change();
i=0;
}
}
}
}
void addlist(int key,int pos){
list[pos][++list[pos][0]]=key;
}
void print(){
if (flow
return;
}
printf("YESn");
for (int i=1;i
int t=ls[g[i].y];
while (t!=0){
if (g[t].y>=n+1 && g[t].y<=n+m && g[t].c==0){
addlist(g[i].y,g[t].y-n);
break;
}
t=g[t].next;
}
}
for (int i=1;i<=m;i++)
printf("2 %d %dn",list[i][1],list[i][2]);
}
int main(){
init();
sap();
print();
return 0;
}
