题面

洛谷 P2763 & LOJ #6006

题目描述

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

输入格式

第 $ 1 $ 行有 $ 2 $ 个正整数 $ k $ 和 $ n $。$ k $ 表示题库中试题类型总数，$ n $ 表示题库中试题总数。第 $ 2 $ 行有 $ k $ 个正整数，第 $ i $ 个正整数表示要选出的类型 $ i $ 的题数。这 $ k $ 个数相加就是要选出的总题数 $ m $。

接下来的 $ n $ 行给出了题库中每个试题的类型信息。每行的第 $ 1 $ 个正整数 $ p $ 表明该题可以属于 $ p $ 类，接着的 $ p $ 个数是该题所属的类型号。

输出格式

第 $ i $ 行输出 `i:` 后接类型 $ i $ 的题号。如果有多个满足要求的方案，只要输出一个方案。如果问题无解，则输出 `No Solution!`。

思路

将每道题目看做一个点，每种分类看做一个点、

由源点向每道题目连权值为 $1$ 的边（每道题目只能选一次），每道题目向其所属的分类连权值为 $1$ 的边（选其中的一种分类），每个分类向汇点连边，权值为该分类要选出的题数。

然后跑一遍最大流，统计被使用的边输出。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,k,last[200005],from[200005],to[200005],nextt[200005],s[200005],top=1;
long long v[200005],d[200005];
void add(int a,int b,int c){
    nextt[++top]=last[a];
    from[top]=a;
    to[top]=b;
    s[top]=c;
    last[a]=top;
}
bool bfs(long long S,long long T){
    memset(v,0,sizeof(v));
    memset(d,63,sizeof(d));
    queue<long long> q;
    q.push(S);
    v[S]=1;
    d[S]=0;
    while (!q.empty()){
        long long now=q.front();
        q.pop();
        v[now]=0;
        for (int i=last[now];i;i=nextt[i]){
            int j=to[i];
            if (d[j]>d[now]&&s[i]){
            	d[j]=d[now]+1;
            	if (!v[j]){
	            	q.push(j);
	            	v[j]=1;
				}
			}
        }
    }
    if (d[T]<1000000000){
    	return 1;
	}
    return 0;
}
int dfs(long long x,long long minn,long long T){
	if (x==T){
		return minn;
	}
	int tmp=0;
	for (int i=last[x];i;i=nextt[i]){
        int j=to[i];
        if (d[j]==d[x]+1&&s[i]){
			tmp=dfs(j,min(minn,s[i]),T);
			if (tmp){
	            s[i]-=tmp;
	            s[i^1]+=tmp;
	            return tmp;
			}
		}
    }
    return 0;
}
long long dinic(long long S,long long T){
	long long ans=0,tmp=0;
	while (bfs(S,T)){
		while (1){
			tmp=dfs(S,2147483647,T);
			if (!tmp){
				break;
			}
			ans+=tmp;
		}
	}
    return ans;
}
int a[10000];
int main(){
    long long S=3005,T=3006;
    cin>>k>>n;
    int sum=0;
    for (int i=1;i<=n;i++){
    	add(S,i,1);
    	add(i,S,0);
	}
    for (int i=1;i<=k;i++){
    	cin>>a[i];
    	sum+=a[i];
    	add(n+i,T,a[i]);
    	add(T,n+i,0);
	}
    for (int i=1;i<=n;i++){
    	int x,y;
    	cin>>x;
    	while (x--){
    		cin>>y;
    		add(i,n+y,1);
    		add(n+y,i,0);
		}
	}
    bfs(S,T);
    int cnt=dinic(S,T);
    if (cnt<sum){
    	cout<<"No Solution!\n";
    	return 0;
	} 
    vector<int> res[1005];
    for (int i=1;i<=top;i++){
    	if (from[i]<=n&&to[i]<=n+k&&from[i]<to[i]&&s[i]==0){
    		res[to[i]-n].push_back(from[i]);
		}
	}
	for (int i=1;i<=k;i++){
		cout<<i<<":";
		for(int j=0;j<res[i].size();j++){
			cout<<" "<<res[i][j];
		}
		cout<<endl;
	}
}