洛谷P2763 试题库问题

题目描述

问题描述：

假设一个试题库中有 nn 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 mm 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。

编程任务：

对于给定的组卷要求，计算满足要求的组卷方案。

输入格式

第一行有两个正整数 kk 和 nn。kk 表示题库中试题类型总数，nn 表示题库中试题总数。

第二行有 kk 个正整数，第 ii 个正整数表示要选出的类型 ii 的题数。这 kk 个数相加就是要选出的总题数 mm。

接下来的 nn 行给出了题库中每个试题的类型信息。每行的第一个正整数 pp 表明该题可以属于 pp 类，接着的 pp 个数是该题所属的类型号。

输出格式

输出共 kk 行，第 ii 行输出 i: 后接类型 ii 的题号。
如果有多个满足要求的方案，只要输出一个方案。
如果问题无解，则输出No Solution!。

输入输出样例

输入 #1复制

3 15
3 3 4
2 1 2
1 3
1 3
1 3
1 3
3 1 2 3
2 2 3
2 1 3
1 2
1 2
2 1 2
2 1 3
2 1 2
1 1
3 1 2 3

输出 #1复制

1: 1 6 8
2: 7 9 10
3: 2 3 4 5

说明/提示

2\leq k \leq 202≤k≤20，k \leq n \leq 10^3k≤n≤103。

---

感谢 @PhoenixEclipse 提供 spj

只是记录，不多说

#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<numeric>
#include<stack>
#include<queue>
#include<set>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f,int_max=0x7fffffff;
//这道题还是最大流，但是就是每个类型的结点的流量是有一个上限的，并且要标记说被选中的是归属于哪一类的
//这个其实也不用标记，就是最后跑一遍深搜看哪些边是 cap==flow 的，是的话就是选中到这一类中了
const int maxn=1100,maxm=maxn*21;
struct edge{
    int v,nxt,cap,flow;
    edge():flow(0){}
}edg[maxm*2];
int ecnt=0,head[maxn],d[maxn],cur[maxn],n,m,k,s,t;
set<int> ans[25];
bool vis[maxn];
void addedge(int u,int v,int cap)//cap 正边是cap，反边是0
{
    edg[ecnt].v=v;
    edg[ecnt].nxt=head[u];
    edg[ecnt].cap=cap;
    head[u]=ecnt++;
}
bool bfs()
{
    memset(d,63,sizeof d);
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(s);
    d[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];~i;i=edg[i].nxt)
        {
            edge &e=edg[i];
            if(!vis[e.v]&&e.cap>e.flow)
            {
                vis[e.v]=1;
                d[e.v]=d[u]+1;
                q.push(e.v);
            }
        }
    }
    return vis[t];
}
ll dfs(int u,ll fi)
{
    if(u==t||!fi)return fi;
    ll flow=0,fo;
    for(int &i=cur[u];~i;i=edg[i].nxt)
    {
        edge &e=edg[i];
        if(d[u]+1==d[e.v]&&(fo=dfs(e.v,min(fi,(ll)e.cap-e.flow)))>0)
        {
            e.flow+=fo;
            edg[i^1].flow-=fo;
            flow+=fo;
            fi-=fo;
            if(!fi)break;
        }
    }
    return flow;
}
ll maxFlow()
{
    ll flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof cur);
        flow+=dfs(s,(ll)inf*inf);
    }
    return flow;
}
int main()
{
	ios_base::sync_with_stdio(0),cin.tie(0);
	s=1098,t=1097;//随便给个可以的就行
    memset(head,-1,sizeof head);
	cin>>k>>n;
    for(int i=1;i<=k;i++)
    {
        int nd;
        cin>>nd;
        addedge(s,i+1005,nd);
        addedge(i+1005,s,0);
    }
    for(int i=1;i<=n;i++)
    {
        int num;
        cin>>num;
        addedge(i,t,1);
        addedge(t,i,0);
        while(num--)
        {
            int tp;
            cin>>tp;
            tp+=1005;
            addedge(tp,i,1);
            addedge(i,tp,0);
        }
    }
    maxFlow();//md一开始忘记调用这个了，检查了好久
    bool flag=1;
    for(int i=head[s];~i;i=edg[i].nxt)
    {
        if(edg[i].cap-edg[i].flow)
        {
            flag=0;
            break;
        }
        if(!edg[i].cap)continue;
        //注意如果没有上面这一步，那么后面在遍历边的时候就会遍历到那个类型到s的一条反向边
        //（而正常情况下是不会这样的，这是由于反向边是最先加入的，所以最晚被遍历到，因此不是0的时候就是不会出错的）
        //最合理的解决方法应该就是判断要是终点是s的话就去掉
        int tp=edg[i].v;
        for(int j=head[tp];~j;j=edg[j].nxt)
        {
            if(edg[j].cap==edg[j].flow)ans[tp-1005].insert(edg[j].v);
        }
    }
    if(!flag)cout<<"No Solution!";
    else
    {
        for(int i=1;i<=k;i++)
        {
            cout<<i<<": ";
            for(auto a:ans[i])cout<<a<<" ";
            cout<<"\n";
        }
    }
	return 0;
}