[SGU 242] 网络流

题意：

有N个学生，可以被分配去M个学校，给出哪些学生能去哪些学校，

求一个解：每间学校都分到>=2个学生的方案。

分析：

cai0715用上下界做。。。其实不用这么麻烦= =

连边(s,i,1) i为学生

连边(i,j,1) j为学校

连边(j,T,2)

然后最大流即可。

插曲：

PE到2B，原来SGU的PE有可能是Runtime ERROR。原来我数组没开够

code：

#include #include #define N 100000
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]    d[k]=min+1;
}   

void change(){
    int nf=2;
    for (int i=n+m+1;i!=0;i=g[fa[i]].x)
      if (g[fa[i]].c    flow+=nf;
    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]        while (cur[i]!=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        printf("NOn");
        return;
    }   
    printf("YESn");
    for (int i=1;i      if (g[i].x==0 && g[i].c==0){
          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;
}