题目描述看：这里
这是我们遇到的第一个要求输出方案的问题
考虑建图然后用最大流思想：
首先由源点向每一道试题连边，容量为1
然后由每一种试题类型向汇点连边，容量为需求量
最后由每一道试题向可能属于的试题类型连边，容量为1
然后跑最大流，如果流量等于总需求量的话即证明合法（每一条到汇点的边流量都跑满才能使流量等于总需求量，这时一定是合法的）
接下来考虑在合法时如何输出方案
根据网络流的特征，我们可以发现如果某一道试题被归入了某一个类型，那么这道试题到这个类型的边就会跑上1的流量
而如果正向边跑上了1的流量，正向边的容量即变为0，而反向边的容量即成为1
所以我们仅需检验正向边容量为0/反向边容量为1任意一个条件，即可说明这道试题归属到了这个试题类型中
考虑到是按试题类型输出选择的试题编号，所以我们检验反向边更加简单一些
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
const int inf=0x3f3f3f3f;
struct Edge
{
int next;
int to;
int val;
}edge[40005];
int head[1505];
int dis[1505];
int cur[1505];
int k,n;
int cnt=1;
int st,ed;
void init()
{
memset(head,-1,sizeof(head));
cnt=1;
}
void add(int l,int r,int w)
{
edge[cnt].next=head[l];
edge[cnt].to=r;
edge[cnt].val=w;
head[l]=cnt++;
}
bool bfs()
{
memcpy(cur,head,sizeof(head));
memset(dis,0,sizeof(dis));
dis[st]=1;
queue <int> M;
M.push(st);
while(!M.empty())
{
int u=M.front();
M.pop();
for(int i=head[u];i!=-1;i=edge[i].next)
{
int to=edge[i].to;
if(!dis[to]&&edge[i].val)dis[to]=dis[u]+1,M.push(to);
}
}
return dis[ed];
}
int ide(int x)
{
return (x&1)?x+1:x-1;
}
int dfs(int x,int lim)
{
if(x==ed)return lim;
int ret=0;
for(int i=head[x];i!=-1;i=edge[i].next)
{
int to=edge[i].to;
if(edge[i].val&&dis[to]==dis[x]+1)
{
int temp=dfs(to,min(lim,edge[i].val));
if(temp)
{
edge[i].val-=temp;
edge[ide(i)].val+=temp;
lim-=temp;
ret+=temp;
if(!lim)break;
}
}
cur[x]=i;
}
return ret;
}
int dinic()
{
int ret=0;
while(bfs())ret+=dfs(st,inf);
return ret;
}
int main()
{
scanf("%d%d",&k,&n);
init();
st=k+n+1,ed=k+n+2;
int s=0;
for(int i=1;i<=k;i++)
{
int x;
scanf("%d",&x);
s+=x;
add(i+n,ed,x);
add(ed,i+n,0);
}
for(int i=1;i<=n;i++)
{
int num;
scanf("%d",&num);
for(int j=1;j<=num;j++)
{
int x;
scanf("%d",&x);
add(i,x+n,1);
add(x+n,i,0);
}
add(st,i,1);
add(i,st,0);
}
int t=dinic();
if(t!=s)printf("No Solution!\n");
else
{
for(int i=1;i<=k;i++)
{
printf("%d: ",i);
for(int j=head[i+n];j!=-1;j=edge[j].next)
{
if(edge[j].to!=ed&&edge[j].val==1)printf("%d ",edge[j].to);
}
printf("\n");
}
}
return 0;
}