【网络流24题】No.7 试题库问题（最大流，二分图多重匹配）

【题意】

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

输入文件示例
input.txt
3 15
3 3 4
2 1 2
1 3
1 3
1 3
1 3
3 1 2 3
2 2 3
2 1 3
1 2
1 2
2 1 2
2 1 3
2 1 2
1 1
3 1 2 3

输出文件示例
output.txt
1: 1 6 8
2: 7 9 10
3: 2 3 4 5

【分析】

　　二分图多重匹配，应该是指点可以选w[i]次，边只能选一次吧。

　　这样就不能用匈牙利了吧。。[咦~~好像也可以，就是要记录所有w次匹配的是谁然后枚举

　　也可以把点拆开，然后做匈牙利，（有空再试试）

　　嗯，最大流建边就很简单啦，那就不说了。。

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<cmath>
  8 using namespace std;
  9 #define Maxn 1010
 10 #define INF 0xfffffff
 11 
 12 struct node
 13 {
 14     int x,y,f,o,next;
 15 }t[Maxn*1010];int len;
 16 int first[Maxn];
 17 
 18 int mymin(int x,int y) {return x<y?x:y;}
 19 int mymax(int x,int y) {return x>y?x:y;}
 20 
 21 void ins(int x,int y,int f)
 22 {
 23     t[++len].x=x;t[len].y=y;t[len].f=f;
 24     t[len].next=first[x];first[x]=len;t[len].o=len+1;
 25     t[++len].x=y;t[len].y=x;t[len].f=0;
 26     t[len].next=first[y];first[y]=len;t[len].o=len-1;
 27 }
 28 
 29 int st,ed;
 30 queue<int > q;
 31 int dis[Maxn];
 32 bool bfs()
 33 {
 34     while(!q.empty()) q.pop();
 35     memset(dis,-1,sizeof(dis));
 36     q.push(st);dis[st]=0;
 37     while(!q.empty())
 38     {
 39         int x=q.front();
 40         for(int i=first[x];i;i=t[i].next) if(t[i].f>0)
 41         {
 42             int y=t[i].y;
 43             if(dis[y]==-1)
 44             {
 45                 dis[y]=dis[x]+1;
 46                 q.push(y);
 47             }
 48         }
 49         q.pop();
 50     }
 51     if(dis[ed]==-1) return 0;
 52     return 1;
 53 }
 54 
 55 int ffind(int x,int flow)
 56 {
 57     if(x==ed) return flow;
 58     int now=0;
 59     for(int i=first[x];i;i=t[i].next) if(t[i].f>0)
 60     {
 61         int y=t[i].y;
 62         if(dis[y]==dis[x]+1)
 63         {
 64             int a=ffind(y,mymin(flow-now,t[i].f));
 65             t[i].f-=a;
 66             t[t[i].o].f+=a;
 67             now+=a;
 68         }
 69         if(now==flow) break;
 70     }
 71     if(now==0) dis[x]=-1;
 72     return now;
 73 }
 74 
 75 void output()
 76 {
 77     for(int i=1;i<=len;i+=2)
 78      printf("%d->%d %d
",t[i].x,t[i].y,t[i].f);
 79 }
 80 
 81 int max_flow()
 82 {
 83     int ans=0;
 84     while(bfs())
 85     {
 86         ans+=ffind(st,INF);
 87     }
 88     return ans;
 89 }
 90 
 91 int op[Maxn][Maxn];
 92 
 93 int main()
 94 {
 95     int k,n,m=0;
 96     scanf("%d%d",&k,&n);
 97     st=n+k+1;ed=st+1;
 98     len=0;
 99     memset(first,0,sizeof(first));
100     for(int i=1;i<=k;i++)
101     {
102         int x;
103         scanf("%d",&x);
104         m+=x;
105         ins(n+i,ed,x);
106     }
107     for(int i=1;i<=n;i++)
108     {
109         int x;
110         scanf("%d",&x);
111         ins(st,i,1);
112         while(x--)
113         {
114             int y;
115             scanf("%d",&y);
116             ins(i,y+n,1);
117         }
118     }
119     int now=max_flow();
120     if(now<m) printf("No Solution!
");
121     else
122     {
123         for(int i=1;i<=k;i++) op[i][0]=0;
124         for(int i=1;i<=len;i+=2) if(t[i].x!=st&&t[i].y!=ed&&t[i].f==0)
125         {
126             op[t[i].y-n][++op[t[i].y-n][0]]=t[i].x;
127         }
128         for(int i=1;i<=k;i++)
129         {
130             printf("%d: ",i);
131          for(int j=1;j<=op[i][0];j++)
132             printf("%d ",op[i][j]);printf("
");
133         }
134     }
135     return 0;
136 }

View Code

没special judge 测不了哭泣。。

2016-11-04 14:53:36

【网络流24题】No.7 试题库问题 （最大流，二分图多重匹配）

【网络流24题】No.7 试题库问题（最大流，二分图多重匹配）