【线性规划与网络流24题 7】试题库问题

Description

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

Input

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

Output

/*
程序运行结束时，将组卷方案输出。
第i 行输出 “i：”后接类型i的题号。如果有多个满足要求的方案，只要输出1 个字典序最小的方案。如果问题无解，则输出“No
Solution!”。
*/
一行，包含一个字符串如果存在，输出"YES"(不包含引号)，如果不存在,输出"No Solution!"(不包含引号)

Sample Input

Sample Output

/*
1: 1 6 8
2: 7 9 10
3: 2 3 4 5
*/
YES

思路和第五题差不多的

二分图多重匹配问题。X，Y集合之间的边容量全部是1，保证两个点只能匹配一次，源汇的连边限制了每个点匹配的个数。
求出网络最大流，如果流量等于X集合所有点与S边容量之和，那么则说明X集合每个点都有完备的多重匹配。

建模方案就不贴了，直接上代码

#include<bits/stdc++.h>
using namespace std;

bool issqr(int x){
	int y=int(sqrt(x*1.0));
	if (x==y*y) return true;
	return false;
}

const int maxn=11000;
const int maxm=1200010;
const int INF=999999;

int n,m,k;
struct Edge{
	int to,nxt,cap,flow;
}edge[maxm];
int tol,Head[maxn];
bool flag[maxn];
int path[maxn],num;

void init(){
	memset(Head,-1,sizeof(Head));
	tol=2;
}

void addedge(int u,int v,int w,int rw=0){
	edge[tol].to=v;
	edge[tol].cap=w;
	edge[tol].flow=0;
	edge[tol].nxt=Head[u];
	Head[u]=tol++;
	
	edge[tol].to=u;
	edge[tol].cap=rw;
	edge[tol].flow=0;
	edge[tol].nxt=Head[v];
	Head[v]=tol++;
}

int Q[maxn],dep[maxn],cur[maxn],sta[maxn];

bool bfs(int s,int t,int n){
	int front=0,tail=0;
	memset(dep,-1,sizeof(dep[0])*(n+1));
	dep[s]=0;
	Q[tail++]=s;
	while(front<tail){
		int u=Q[front++];
		for(int i=Head[u];i!=-1;i=edge[i].nxt){
			int v=edge[i].to;
			if (edge[i].cap>edge[i].flow&&dep[v]==-1){
				dep[v]=dep[u]+1;
				if (v==t) return true;
				Q[tail++]=v;
			}
		}
	}
	return false;
}

int dinic(int s,int t,int n){
	int maxflow=0;
	while(bfs(s,t,n)){
		for(int i=0;i<n;i++) cur[i]=Head[i];
		int u=s,tail=0;
		while(cur[s]!=-1){
			if (u==t){
				int tp=INF;
				for(int i=tail-1;i>=0;i--) 
					tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
				maxflow+=tp;
				for(int i=tail-1;i>=0;i--){
					edge[sta[i]].flow+=tp;
					edge[sta[i]^1].flow-=tp;
					if (edge[sta[i]].cap-edge[sta[i]].flow==0) tail=i;
				}
				u=edge[sta[tail]^1].to;
			}
			else if (cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to]){
				sta[tail++]=cur[u];
				u=edge[cur[u]].to;
			}
			else{
				while(u!=s&&cur[u]==-1) u=edge[sta[--tail]^1].to;
				cur[u]=edge[cur[u]].nxt;
			}
		}
	}
	return maxflow;
}

void getpath(int u){
	u+=n;
    for(int i=Head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        if (!flag[v]&&v<=n&&edge[i].flow)
        	path[++num]=v;
    }
}

int main(){
	//freopen("testlib.in","r",stdin);
	//freopen("testlib.out","w",stdout);
	int s,t,tot,x,y;
	init();
	scanf("%d%d",&m,&n);
	s=0,t=n+m+1,tot=n+m+2,k=0;
	for(int i=1;i<=m;i++){
		scanf("%d",&x);
		k+=x;
		addedge(i+n,t,x);
	}
	for(int i=1;i<=n;i++){
		addedge(s,i,1);
		scanf("%d",&x);
		while(x--){
			scanf("%d",&y);
			addedge(i,y+n,1);
		}
	}
	int maxflow=dinic(s,t,tot);
	if (maxflow>=k){
		/*
		for(int i=1;i<=m;i++){
			printf("%d: ",i);
			num=0;
			getpath(i);
			for(int j=num;j>=1;j--)
				printf("%d ",path[j],j==1?'\n':' ');
			printf("\n");
		}*/
		puts("YES");
	}
	else{
		puts("No Solution!");
	}
	return 0;
}