网络流24题-试题库问题
Ajsoabk
2019-01-31 21:23:42
# [P2763 试题库问题](https://www.luogu.org/problemnew/show/P2763)
题意有点不清
要注意每道题虽可以有多种类型，但却只能与一种类型相匹配
即最后输出时不能在不同种类型中出现同一道题
理解了题意后显然是要我们求某种题与类型之间的的匹配
而类型可以匹配多道题，而且要求某个类型只能匹配特定数量的题
故将类型（n+i）作为右部，与汇点t连容量为题目给出的匹配数量的边
求完最大流后这些边是否满流自然就意味着是否有解
题与类型之间也根据题的类型连边，每道题最多只能有1的贡献，故容量为1
再将源点s与各道题连边，求最大流
如上所述，若最大流不等于m则无解
若相等，则从1到k遍历所有右部点（类型），对每个右部点遍历邻接点，将所有值为1（这个别忘了），且指向左部的边指向的点输出即可
（喜欢就给个赞顶顶我吧）
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=1000+5,K=20+5;
const int inf=0x7fffffff;
template<class T>inline void read(T &num){
char ch;
while(!isdigit(ch=getchar()));
num=ch-'0';
while(isdigit(ch=getchar()))num=num*10+ch-'0';
}
int hea[N<<1],to[N*N<<1],nex[N*N<<1],val[N*N<<1],tot=1,n,k,dep[N<<1],s,t,m;
inline void add_edge(const int x,const int y,const int w){
to[++tot]=y,nex[tot]=hea[x],hea[x]=tot,val[tot]=w;
}
inline void Add_edge(const int x,const int y,const int w){
//printf("%d --> %d ( %d )\n",x,y,w);
add_edge(x,y,w);
add_edge(y,x,0);
}
queue<int> que;
bool bfs(){
memset(dep,0,sizeof(dep));
dep[s]=1;
while(que.size())que.pop();
que.push(s);
int x;
while(que.size()){
x=que.front();que.pop();
for(int i=hea[x];i;i=nex[i]){
int y=to[i];
if(val[i]&&!dep[y]){
dep[y]=dep[x]+1;
if(y==t)return true;
que.push(y);
}
}
}
return false;
}
int dfs(const int x,const int flow){
//printf("dfs(%d,%d) %d\n",x,flow,x==t);
if(x==t)return flow;
int rest=flow,k;
for(int i=hea[x];i&&rest;i=nex[i]){
int y=to[i];
if(val[i]&&dep[y]==dep[x]+1){
k=dfs(y,min(rest,val[i]));
if(k){
val[i]-=k;
val[i^1]+=k;
rest-=k;
}
else dep[y]=0;
}
}
//printf("\t%d x=%d,return %d\n",x==s,x,flow-rest);
return flow-rest;
}
int dinic(){
int maxflow=0,flow;
while(bfs())while(flow=dfs(s,inf))maxflow+=flow;
//printf("return %d\n",maxflow);
return maxflow;
}
inline void print(const int x){
for(int i=hea[x];i;i=nex[i]){
int y=to[i];
//printf("\ny=%d\n",y);
if(val[i]&&y<=n){
printf(" %d",y);
}
}
}
int main(){
read(k),read(n);
s=n+k+1;
t=s+1;
for(int i=1,w;i<=k;++i){
read(w);
m+=w;
Add_edge(n+i,t,w);
}
for(int i=1,b,h;i<=n;++i){
Add_edge(s,i,1);
read(h);
for(int j=1;j<=h;++j){
read(b);
Add_edge(i,b+n,1);
}
}
if(dinic()==m){
for(int i=1;i<=k;++i){
printf("%d:",i);
print(n+i);
putchar('\n');
}
}
else{
printf("No Solution!\n");
}
return 0;
}
```