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

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

阅读量：5127 次

发布时间：2019-06-13

本文共 2541 字，大约阅读时间需要 8 分钟。

【题意】

　　假设一个试题库中有 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
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              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;} 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
              
                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\n",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