线性规划与网络流之7 试题库问题 网络流

题目：

假设一个试题库中有n道试题。 每道试题都标明了所属类别。同一道题可能有多个类别
属性。现要从题库中抽取 m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个
满足要求的组卷算法。

由文件input.txt提供输入数据。 文件第1行有2个正整数n和k (2 <=k<= 20, k<=n<= 1000)
k 表示题库中试题类型总数，n 表示题库中试题总数。第 2 行有 k 个正整数，第 i 个正整数
表示要选出的类型i的题数。这k个数相加就是要选出的总题数m。接下来的n行给出了题
库中每个试题的类型信息。每行的第1 个正整数 p表明该题可以属于 p类，接着的 p个数是
该题所属的类型号。

分析：

明显的网络流模型，对于每个试题，连一条边(S,i,1)

对于每个试题类型，连一条边(i,T,tmp)。其中tmp表示这个类型需要多少题。

然后最大流。

如果流量等于SUM(tmp)，有解，按要求输出，否则，输出No Solution！

HINT
我写的check程序(No Solution 请手测)：

#include using namespace std;

int n,m,a[2000][2000],num[2000],v[2000];

void init(){
     cin >> m >> n;
     for (int i=1;i<=m;i++) scanf("%d",&num[i]);
     for (int i=1;i<=n;i++){
         int num,tmp;
         scanf("%d",&num);
         for (int j=1;j<=num;j++){
           scanf("%d",&tmp);
           a[i][tmp]=1;
         }
     }
}

bool work(){
     for (int i=1;i<=m;i++){
         int tmp;
         scanf("%d:",&tmp);
         if (tmp!=i) return false;
         for (int j=1;j<=num[i];j++){
           scanf("%d",&tmp);
           if (v[tmp]==1) return false;
           if (a[tmp][i]==0) return false;
           v[tmp]=1;
         }
     }
     return true;
}

int main(){
    freopen("input.txt","r",stdin);
    init();
    freopen("output.txt","r",stdin);
    freopen("result.txt","w",stdout);
    if (work()) cout << "AC" << endl;
          else cout << "WA" << endl;
}

code：

#include using namespace std;
const int P=10000;
const int E=2000000;
const int INF=0x7FFFFFFF;
struct gtp{int x,y,next,c,op;}g[E];
int n,m,e=0,ls[P],fa[P],cur[P],d[P],num[P],total=0;
int link[1000][1000];

inline void addedge(int x,int y,int c){
       e++;
       g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].c=c; g[e].op=e+1;
       e++;
       g[e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].c=0; g[e].op=e-1;
}

void init(){
     scanf("%d%d",&m,&n);
     for (int i=1;i<=n;i++) addedge(0,i,1);
     for (int i=1;i<=m;i++){
         int tmp;
         scanf("%d",&tmp);
         addedge(n+i,m+n+1,tmp);
         total+=tmp;
     }
     for (int i=1;i<=n;i++){
         int num,tmp;
         scanf("%d",&num);
         for (int j=1;j<=num;j++){
             scanf("%d",&tmp);
             addedge(i,tmp+n,1);
         }
     }
}

void relabel(int k){
     int min=m+n+1;
     cur[k]=ls[k];
     for (int i=ls[k];i!=0;i=g[i].next)
       if (g[i].c>0 && d[g[i].y]         min=d[g[i].y];
     d[k]=min+1;
}

void change(int &flow){
     int nf=INF;
     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;
     }
}

int sap(){
    int flow=0;
    for (int i=0;i<=n+m+1;i++){
        d[i]=0;
        cur[i]=ls[i];
        num[i]=0;
    }
    num[0]=n+m+2;
    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(flow);
              i=0;
            }
          }
    }
    return flow;
}

void work(){
     int flow=sap();
     if (flow     else{
          for (int i=1;i<=e;i++)
            if (i%2==1 && g[i].c==0 && 1<=g[i].x && g[i].x<=n && n+1<=g[i].y && g[i].y<=n+m){
              link[g[i].y-n][0]++;
              link[g[i].y-n][link[g[i].y-n][0]]=g[i].x;
            }
          for (int i=1;i<=m;i++){
            cout << i << ":";
            for (int j=1;j<=link[i][0];j++)
              cout << link[i][j] << " ";
            cout << endl;
          }
     }
}

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    init();
    work();
}