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

题目大意： 给出 $m$ 道题，每道题拥有一些类型，一共有 $n$ 种类型，现在需要第 $i$ 种类型的题 $a_i$ 道，要求选出的 $\sum a_i$ 道题互不相同，请找出一种方案。

题解

每道题向对应的类型连边，流量为 $1$，源点向题连流量为 $1$ 的边，类型向汇点连流量为 $a_i$ 的边，跑一发最大流，然后看看二分图中间的那些边有哪些被走了就好。

代码如下：

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define maxn 100010int n,m,a[maxn],S,T,sum=0;struct edge{
   int x,y,z,next;};edge e[maxn<<1];int first[maxn],len=1,now;void buildroad(int x,int y,int z){
   	e[++len]=(edge){
   x,y,z,first[x]};	first[x]=len;}int h[maxn],q[maxn],st,ed;bool bfs(){
   	memset(h,0,sizeof(h));	st=ed=1;q[st]=S;h[S]=1;	while(st<=ed)	{
   		int x=q[st++];		for(int i=first[x];i;i=e[i].next)		if(!h[e[i].y]&&e[i].z)h[q[++ed]=e[i].y]=h[x]+1;	}	return h[T];}int dfs(int x,int flow){
   	if(x==T)return flow;	int tt=0,p;	for(int i=first[x];i;i=e[i].next)	{
   		int y=e[i].y;		if(h[y]==h[x]+1&&e[i].z)		{
   			p=dfs(y,min(e[i].z,flow-tt));tt+=p;			e[i].z-=p;e[i^1].z+=p;			if(tt==flow)break;		}	}	if(!tt)h[x]=0;	return tt;}int ans[maxn][30],t[maxn];int main(){
   	scanf("%d %d",&n,&m);S=n+m+1,T=S+1;	for(int i=1;i<=n;i++)	scanf("%d",&a[i]),sum+=a[i],	buildroad(i+m,T,a[i]),buildroad(T,i+m,0);	for(int i=1;i<=m;i++)buildroad(S,i,1),buildroad(i,S,0);	now=len+1;	for(int i=1,x,y;i<=m;i++)	{
   		scanf("%d",&x);		while(x--)scanf("%d",&y),		buildroad(i,y+m,1),buildroad(y+m,i,0);	}	while(bfs())sum-=dfs(S,999999999);	if(sum)return printf("No Solution!"),0;	for(int i=now;i<=len;i+=2)	if(!e[i].z)ans[e[i].y-m][++t[e[i].y-m]]=e[i].x;	for(int i=1;i<=n;i++)	{
   		printf("%d: ",i);		for(int j=1;j<=a[i];j++)		printf("%d ",ans[i][j]);		printf("\n");	}}
     
    
   

转载地址：http://wjnib.baihongyu.com/