[洛谷 2763]试题库问题

题目链接

https://www.luogu.org/problem/P2763

题解

我们这样建立一个网络流模型：

1. 从源点向每道题目之间连一条容量为 \(1\) 的边，代表每道题目只能被选一次。
2. 每道题目向它匹配的类型连一条容量为 \(1\) 的边。
3. 每个类型向汇点连接一条容量为该类型所需题目数的边，代表该类型需要选出这么多的题目。

跑一遍最大流，如果最大流量小于总题数 \(m\) ，则无解。否则方案为题目与类型边中满流的那些边。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
 int v,w,next;
}e[2000005];
int head[2005],vis[2005],cur[2005],dep[2005],s,t,cnt=1,k,n;
queue<int> res[25];
void addedge(int u,int v,int w)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].next=head[u];
 head[u]=cnt;
}
bool bfs()
{
 queue<int> q;
 memcpy(cur,head,sizeof(cur));
 memset(dep,INF,sizeof(dep));
 dep[s]=0,vis[s]=1;
 q.push(s);
 while(!q.empty())
 {
  int u=q.front();
  q.pop();
  vis[u]=0;
  for(int i=head[u];i;i=e[i].next)
   if(e[i].w&&dep[e[i].v]>dep[u]+1)
   {
    dep[e[i].v]=dep[u]+1;
    if(!vis[e[i].v])
    {
     q.push(e[i].v);
     vis[e[i].v]=1;
    }
   }
 }
 return dep[t]!=INF;
}
int dfs(int u,int w)
{
 if(u==t)return w;
 int used=0;
 for(int i=cur[u];i;i=e[i].next)
 {
  cur[u]=i;
  if(dep[e[i].v]==dep[u]+1&&e[i].w)
  {
   int flow=dfs(e[i].v,min(w-used,e[i].w));
   if(flow)
   {
    used+=flow;
    e[i].w-=flow;
    e[i^1].w+=flow;
    if(used==w)break;
   }
  }
 }
 return used;
}
int main()
{
 scanf("%d%d",&k,&n);
 int ans=0;
 s=n+k+1,t=n+k+2;
 for(int i=1;i<=k;i++)
 {
  int x;
  scanf("%d",&x);
  addedge(n+i,t,x);
  addedge(t,n+i,0);
  ans+=x;
 }
 for(int i=1;i<=n;i++)
 {
  int p;
  scanf("%d",&p);
  addedge(s,i,1);
  addedge(i,s,0);
  while(p--)
  {
   int x;
   scanf("%d",&x);
   addedge(i,n+x,1);
   addedge(n+x,i,0);
  }
 }
 while(bfs())
  ans-=dfs(s,INF);
 if(ans)
 {
  puts("No Solution!");
  return 0;
 }
 for(int i=1;i<=n;i++)
  for(int j=head[i];j;j=e[j].next)
   if(!e[j].w)res[e[j].v-n].push(i);
 for(int i=1;i<=k;i++)
 {
  printf("%d: ",i);
  while(!res[i].empty())
  {
   printf("%d ",res[i].front());
   res[i].pop();
  }
  puts("");
 }
 return 0;
}