luogu2763 试题库问题

倘若某个试题已经被选到某个类型里了，那么它就不可再被选进别的类型了。

所以，对于每个类型，我们将其与汇连边，权值是它的要求的题目数量。

对于每个题目，我们将源与其连边，权值是1，代表只能用一次。然后再将其与它所对应的所有类型连边。

倘若最大流小于m，则说明不能组卷。

输出路径我觉得还是比较好做的，对于每个类型，枚举它的每一条边，倘若边的另一头是试题，并且这条边上有流，则说明那个题是要选上的。（因为反向边）

#include <iostream>#include <cstring>#include <cstdio>#include <queue>using namespace std;struct Edge{int too, nxt, val;}edge[50005];int k, n, ss, tt, uu, vv, hea[], cnt, maxFlow, tot, lev[];const int oo=0x3f3f3f3f;queue<int> d;void add_edge(int fro, int too, int val){edge[cnt].nxt = hea[fro];edge[cnt].too = too;edge[cnt].val = val;hea[fro] = cnt++;}void addEdge(int fro, int too, int val){add_edge(fro, too, val);add_edge(too, fro, 0);}bool bfs(){memset(lev, 0, sizeof(lev));d.push(ss);lev[ss] = 1;while(!d.empty()){int x=d.front();d.pop();for(int i=hea[x]; i!=-1; i=edge[i].nxt){int t=edge[i].too;if(!lev[t] && edge[i].val>0){d.push(t);lev[t] = lev[x] + 1;}}}return lev[tt]!=0;}int dfs(int x, int lim){if(x==tt) return lim;int addFlow=0;for(int i=hea[x]; i!=-1 && addFlow<lim; i=edge[i].nxt){int t=edge[i].too;if(lev[t]==lev[x]+1 && edge[i].val>0){int tmp=dfs(t, min(lim-addFlow, edge[i].val));edge[i].val -= tmp;edge[i^1].val += tmp;addFlow += tmp;}}return addFlow;}void dinic(){while(bfs()) maxFlow += dfs(ss, oo);}int main(){memset(hea, -1, sizeof(hea));cin>>k>>n;ss = 0; tt = k + n + 1;for(int i=1; i<=k; i++){scanf("%d", &uu);addEdge(i+n, tt, uu);tot += uu;}for(int i=1; i<=n; i++){scanf("%d", &uu);for(int j=1; j<=uu; j++){scanf("%d", &vv);addEdge(i, vv+n, 1);}addEdge(ss, i, 1);//每题只能用一次}dinic();if(maxFlow<tot) cout<<"No Solution!"<<endl;elsefor(int i=n+1; i<=n+k; i++){printf("%d: ", i-n);for(int j=hea[i]; j!=-1; j=edge[j].nxt){int t=edge[j].too;if(t<=n && edge[j].val)printf("%d ", t);}printf("\n");}return 0;}

如果觉得《luogu2763 试题库问题》对你有帮助，请点赞、收藏，并留下你的观点哦！