线性规划与网络流之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();
}

线性规划与网络流之6 构图、网络流

题目参见:http://www.byvoid.com/blog/lpf24-solution/

题意:给定A[1],A[2]…A[N]

Question1:最长上升子序列的长度是多少?

Question2:从这个序列中,最多能取出多少个没有重复使用的元素的上升子序列。其长度=Question1

Question3:同2,但A[1]和A[N]能使用无限次。

分析:

第一问:DP

第二问:

对于f[i]=1的点加一条边(S,i,1)

对于f[i]=len的点加一条边(i,T,1)

对于a[j]

求最大流

第三问:

在第二问的图的基础上加入以下两条边

(S,1,INF)

如果f[n]=len,加这条边(n,T,INF)

求最大流

HINT:

1、len表示第一问的答案。

2、我的程序是从0开始的。。。和分析有点出入

code:

#include #define E 4000000
#define N 1000000
using namespace std;
const int INF=0x7FFFFFFF/2;
struct gtp{int x,y,next,c,op;} g[E];
int n,a[500],f[500],e,ls[N],d[N],num[N],cur[N],fa[N],S,T,Flow;

int problem1(){
     for (int i=0;i     int ans=1;
     for (int i=1;i       for (int j=0;j         if (a[j]           f[i]=f[j]+1;
           ans=max(f[i],ans);
         }
     return ans;
}

void add(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 relabel(int k){
     int min=T,i=ls[k];
     cur[k]=ls[k];
     while (i!=0){
       if (g[i].c>0 && d[g[i].y]       i=g[i].next;
     }
     d[k]=min+1;
}

void change(){
     int nf=INF;
     for (int i=T;i!=S;i=g[fa[i]].x)
       if (g[fa[i]].c     Flow+=nf;
     for (int i=T;i!=S;i=g[fa[i]].x){
         g[fa[i]].c-=nf;
         g[g[fa[i]].op].c+=nf;
     }
}

void sap(){
     Flow=0;
     for (int i=0;i<=T;i++){
         d[i]=0;
         num[i]=0;
         cur[i]=ls[i];
     }
     num[0]=T+1;
     int i=S;
     while (d[S]<=T){
           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!=S) i=g[fa[i]].x;
           }
           else{
             fa[g[cur[i]].y]=cur[i];
             i=g[cur[i]].y;
             if (i==T){
               change();
               i=S;
             }
           }
     }
}

void problem2(int len){
     memset(ls,0,sizeof(ls));
     S=n;
     T=n+1;
     e=0;
     for (int i=0;i       if (f[i]==1) add(S,i,1);
       if (f[i]==len) add(i,T,1);
     }
     for (int i=0;i       for (int j=i+1;j         if (a[i]     sap();
     cout << Flow << endl;
}

void problem3(int len){
     memset(ls,0,sizeof(ls));
     S=n;
     T=n+1;
     e=0;
     add(S,0,INF);
     if (f[n-1]==len) add(n-1,T,INF);
     for (int i=0;i       if (f[i]==1) add(S,i,1);
       if (f[i]==len) add(i,T,1);
     }
     for (int i=0;i       for (int j=i+1;j         if (a[i]     sap();
     cout << Flow << endl;
}

int main(){
    freopen("alis.in","r",stdin);
    freopen("alis.ans","w",stdout);
    scanf("%d",&n);
    for (int i=0;i    int len=problem1();
    cout << len << endl;
    problem2(len);
    problem3(len);
    return 0;
}

线性规划与网络流之4 抽象模型、网络流

题目:http://www.byvoid.com/blog/lpf24-solution/

分析:

把每根柱子上按顺序插的球当做是一条路径。然后这题变成了N个不相交路径最多可以覆盖多少连续的球。我们可以枚举答案。然后每次加入一个点。然后sap。直到不能覆盖。因为每次最多增加1的流量,所以sap会非常快。平均起来也就几乎O(N)每一次

code:

#include #include #define E 2222222
#define N 111111
#define sqr(x) (x)*(x)
using namespace std;

struct gtp{int x,y,next,c,op;} g[E];
int n,e=0,ls[N],S=0,T=1,p=1,Flow=0,cur[N],fa[N],d[N],num[N];

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

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

void change(){
     int i;
     i=T;
     while (i!=S){
           g[fa[i]].c–;
           g[g[fa[i]].op].c++;
           i=g[fa[i]].x;
     }
     Flow++;
}

void sap(){
     for (int i=0;i<=p;i++){
         cur[i]=ls[i];
         d[i]=0;
         num[i]=0;
     }
     num[0]=p+1;
     int i=S;
     while (d[S]           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!=S) i=g[fa[i]].x;
           }
           else{
             fa[g[cur[i]].y]=cur[i];
             i=g[cur[i]].y;
             if (i==T){
               change();
               i=S;
             }
           }
     }
}

bool Try(int k){
     p++;
     add(S,p,1);
     p++;
     add(p,T,1);
     for (int i=1;i       if (sqr((int)(sqrt(i+k)+0.5))==i+k)
         add(i<<1,p,1);
     sap();
     if (k-Flow<=n) return true;
     return false;
}

int main(){
    freopen("ball10.in","r",stdin);
    freopen("ball10.ans","w",stdout);
    cin >> n;
    for (int i=1;i<=99999;i++)
        if (!Try(i)){
          cout << i-1 << endl;
          return 0;
        }
}

线性规划与网络流之3 最小路径覆盖

题目:http://www.byvoid.com/blog/lpf24-solution/

分析:

求一个有向无环图的最小路径覆盖。

构造二分图,每个点拆成两个。然后按边的关系从左边向右边连边即可。

然后求最大匹配。最后输出N-最大匹配数即可。

HINT

另外也可以求无向图的最小路径覆盖。

最后答案就是N-最大匹配数/2

code:

#include #include #define E 100000
#define N 10000
int n,e,x[E],y[E],next[E],ls[N],link[N],v[N];

void add(int X,int Y,int i){
     x[i]=X; y[i]=Y; next[i]=ls[X]; ls[X]=i;
}

void init(){
     scanf("%d%d",&n,&e);
     int X,Y;
     for (int i=1;i<=e;i++){
         scanf("%d%d",&X,&Y);
         add(X,Y,i);
     }
}

bool find(int k,int mark){
     for (int t=ls[k];t!=0;t=next[t])
       if (v[y[t]]!=mark){
         int q=link[y[t]];
         link[y[t]]=k;
         v[y[t]]=mark;
         if (q==0 || find(q,mark)) return true;
         link[y[t]]=q;
     }
     return false;
}

void match(){
     memset(link,0,sizeof(link));
     memset(v,0,sizeof(v));
     int MatchNum=0;
     for (int i=1;i<=n;i++)
       if (find(i,i)) MatchNum++;
     printf("%dn",n-MatchNum);
}

int main(){
    freopen("path.in","r",stdin);
    freopen("path.ans","w",stdout);
    init();
    match();
    return 0;
}

线性规划与网络流之2 最大权闭合图

题目:http://www.byvoid.com/blog/lpf24-solution/

分析

按照题意,可以构建一个二分图,然后我们可以发现这是一个依赖关系的最大权取值问题。所以直接套用《最小割模型在信息学竞赛中的应用》里的最大权闭合图模型解决。

code:

#include #define E 1000001
#define N 1001
#define Maxnum 1000000000
int m,n,x[E],y[E],next[E],c[E],op[E],ls[N],d[N],fa[N],num[N],cur[N],vs,vt,e=0,s=0,flow=0;

void add(int X,int Y,int C){
     e++;
     x[e]=X; y[e]=Y; c[e]=C; next[e]=ls[X]; ls[X]=e; op[e]=e+1;
     e++;
     x[e]=Y; y[e]=X; c[e]=0; next[e]=ls[Y]; ls[Y]=e; op[e]=e-1;
}

void init(){
     scanf("%d%d",&m,&n);
     vs=0; vt=m+n+1;
     char ch;
     for (int i=1;i<=m;i++){
         int t;
         scanf("%d",&t);
         s+=t;
         add(vs,i,t);
         while (scanf("%c",&ch)!=EOF && ch!=’n’){
               scanf("%d",&t);
               add(i,m+t,Maxnum);
         }
     }
     for (int i=1;i<=n;i++){
         int t;
         scanf("%d",&t);
         add(m+i,vt,t);
     }
}

void relabel(int k){
     int min=vt,i=ls[k];
     cur[k]=ls[k];
     while (i>0){
       if (c[i]>0 && d[y[i]]       i=next[i];
     }
     d[k]=min+1;
}

void change(){
     int i=vt,nf=Maxnum;
     while (i!=vs){
           if (c[fa[i]]           i=x[fa[i]];
     }
     flow+=nf;
     i=vt;
     while (i!=vs){
           c[fa[i]]-=nf;
           c[op[fa[i]]]+=nf;
           i=x[fa[i]];
     }
}

void sap(){
     for (int i=vs;i<=vt;i++){
         num[i]=0;
         d[i]=0;
         cur[i]=ls[i];
     }
     num[0]=vt+1;
     int i=vs;
     while (d[vs]           while (cur[i]>0)
             if (d[x[cur[i]]]==d[y[cur[i]]]+1 && c[cur[i]]>0)
               break;
             else
               cur[i]=next[cur[i]];
           if (cur[i]==0){
              num[d[i]]–;
              if (num[d[i]]==0) break;
              relabel(i);
              num[d[i]]++;
              if (i!=vs) i=x[fa[i]];
           }
           else{
              fa[y[cur[i]]]=cur[i];
              i=y[cur[i]];
              if (i==vt){
                 change();
                 i=vs;
              }
           }
     }
}

int main(){
    freopen("shut10.in","r",stdin);
    freopen("shut10.ans","w",stdout);
    init();
    sap();
    printf("%dn",s-flow);
}