洛谷 P2763 试题库问题 网络流 最大流 Dinic 输出路径

题目链接：

​​https://www.luogu.com.cn/problem/P2763​​

参考博客：

​​https://www.luogu.com.cn/blog/ajsoabk/p2763-shi-ti-ku-wen-ti​​

算法：1：网络流 最大流 Dinic

图解：

思路：

1：建立超源点和超汇点，源点与试题相连，汇点与类型相连，对应试题与对应类型相连

2：一道题只可以有一个，所以源点和试题的边的容量为1，一道题只能满足一种类型，所以试题和类型的边的容量也为1

3：需要满足的每种类型是有多个的，所以类型与汇点的边的容量为所需类型的数量

注意：

如何输出每种类型包含的试卷：

for(int i=1;i<=k;i++) { printf("%d: ",i); for(int j=head[n+i];j;j=e[j].next) { if(e[j].w==1)printf("%d ",e[j].to); } printf("\n"); }if(e[j].w==1)printf("%d ",e[j].to);

 的意思是，如果j的反向边，即你画的示意图的正向边被流过，那么其流量变为0，而其反向边，即j的w值加1，变为1，与t相连的那条边本身在原图中就是正向边，此时w值已经变为0

代码：

#include <bits/stdc++.h>using namespace std;const int maxn=1e3+2e1+2,maxm=4e4+2e3+4e1+1;int k,n,a,s,t,tot=1,head[maxn],dep[maxn],ans,sum,num;//用上了分层图，可以用dep判重了struct edge{ int to,next,w;}e[maxm];void addedge(int x,int y,int w){ e[++tot].to=y;e[tot].w=w;e[tot].next=head[x];head[x]=tot; e[++tot].to=x;e[tot].w=0;e[tot].next=head[y];head[y]=tot;}bool bfs()//bool 函数是一个小优化，判断是否能搜到汇点，如果连汇点都搜不到还dfs干什么？{ memset(dep,0,sizeof dep);//一定要初始化 queue<int>q; q.push(s);dep[s]=1; while(!q.empty()) { int x=q.front();q.pop(); for(int i=head[x];i;i=e[i].next) { int y=e[i].to,w=e[i].w; if(w&&!dep[y])//如果有残余流量（没有的话谁也过不去）并且这个点是第一次到达 { dep[y]=dep[x]+1; q.push(y); } } } return dep[t];//t 的深度不为0，就是搜到了汇点}int dfs(int x,int flow){ if(x==t)return flow; int sum=0; for(int i=head[x];i;i=e[i].next) { int y=e[i].to,w=e[i].w; if(w&&dep[y]==dep[x]+1)//仅允许流向下一层 { int t=dfs(y,min(w,flow)); e[i].w-=t;e[i^1].w+=t; flow-=t;sum+=t; } } if(!sum)dep[x]=0;//我与终点（顺着残余网络）不连通的话，那么上一层的点请别给我流量 return sum;}int main(){ ios::sync_with_stdio(0); scanf("%d %d",&k,&n); s=0,t=k+n+1; for(int i=1;i<=k;i++) { scanf("%d",&a);sum+=a; addedge(n+i,t,a); } for(int i=1;i<=n;i++) { addedge(s,i,1); scanf("%d",&num); for(int j=1;j<=num;j++) scanf("%d",&a),addedge(i,n+a,1); } while(bfs())ans+=dfs(s,2e9); if(ans==sum) { for(int i=1;i<=k;i++) { printf("%d: ",i); for(int j=head[n+i];j;j=e[j].next) { if(e[j].w==1)printf("%d ",e[j].to); } printf("\n"); } } else printf("No Solution!\n"); return 0;}