网络流24题之七试题库问题

内容

填坑

地址：luogu2763

题目描述

«问题描述：

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

«编程任务：

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

输入输出格式

输入格式：

第1行有2个正整数k和n (2 <=k<= 20, k<=n<= 1000)

k 表示题库中试题类型总数，n 表示题库中试题总数。第2 行有k 个正整数，第i 个正整数表示要选出的类型i的题数。这k个数相加就是要选出的总题数m。接下来的n行给出了题库中每个试题的类型信息。每行的第1 个正整数p表明该题可以属于p类，接着的p个数是该题所属的类型号。

输出格式：

第i 行输出 “i：”后接类型i的题号。如果有多个满足要求的方案，只要输出1个方案。如果问题无解，则输出“No Solution!”。

输入输出样例

输入样例#1：

输出样例#1：

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

【问题分析】

二分图多重匹配问题，用最大流解决。

【建模方法】

建立二分图，每个类别为X集合中的顶点，每个题为Y集合中的顶点，增设附加源S和汇T。

1、从S向每个Xi连接一条容量为该类别所需数量的有向边。
2、从每个Yi向T连接一条容量为1的有向边。
3、如果一个题i属于一个类别j，连接一条从Xj到Yi容量为1的有向边。

求网络最大流，如果最大流量等于所有类别所需之和，则存在解，否则无解。对于每个类别，从X集合对应点出发的所有满流边，指向的B集合中的顶点就是该类别的所选的题（一个可行解）。

【建模分析】

二分图多重匹配问题。X，Y集合之间的边容量全部是1，保证两个点只能匹配一次，源汇的连边限制了每个点匹配的个数。求出网络最大流，如果流量等于X集合所有点与S边容量之和，那么则说明X集合每个点都有完备的多重匹配。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define M 10010
#define N 1000
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
struct node
{
    int from,to,next,flow;
}e[M];
int tot=-1,st[M],dis[N];
int n,m,x,y,z,k;
void add(int x,int y,int z)
{
    e[++tot].to=y;
    e[tot].from=x;
    e[tot].flow=z;
    e[tot].next=st[x];
    st[x]=tot;
}
void add_edge(int x,int y,int z)
{add(x,y,z),add(y,x,0);}
int bfs(int s,int t)
{
    int now;
    queue<int>que;
    memset(dis,-1,sizeof dis);
    dis[s]=1;
    que.push(s);
    while (!que.empty())
    {
        int now=que.front();
        que.pop();
        for (int i=st[now];~i;i=e[i].next)
            if (dis[e[i].to]<0&&e[i].flow>0)
                dis[e[i].to]=dis[now]+1,
                que.push(e[i].to);
    }
    if (dis[t]>0) return 1;
    return 0;
}
int finds(int x,int y,int low)
{
    int ans;
    if (x==y)
        return low;
    for (int i=st[x];~i;i=e[i].next)
        if (e[i].flow>0 && dis[x]+1==dis[e[i].to] && (ans=finds(e[i].to,y,min(low,e[i].flow))))
        {
            e[i].flow-=ans;
            e[i^1].flow+=ans;
            return ans;
        }
    return 0;
}
int Dinic(int s,int t)
{
    int flow=0;
    while(bfs(s,t))
    {
        while(x=finds(s,t,0x3f3f3f3f))
            flow+=x;
    }
    return flow;
}
//memset(e,-1,sizeof e);
//memset(st,-1,sizeof st);
main()
{
    scanf("%d%d",&k,&n);
    int S=n+k+1,T=S+1,con,sum=0;
    memset(e,-1,sizeof e);
    memset(st,-1,sizeof st);
    for (int i=1;i<=k;i++)
        scanf("%d",&x),add_edge(S,i,x),sum+=x;
    for (int i=1;i<=n;i++)
    {
        add_edge(i+k,T,1);
        scanf("%d",&con);
        for (int j=1;j<=con;j++)
            scanf("%d",&x),add_edge(x,i+k,1);
    }
    int ans=Dinic(S,T);
//  printf("%d\n",ans);
    if (ans==sum)
    for (int i=1;i<=k;i++)
    {
        printf("%d: ",i);
        for (int j=st[i];~j;j=e[j].next)
            if (e[j].flow==0&&!(j&1))
            {
                printf("%d ",e[j].to-k);
                //break;
            }
        puts("");
    }
    else
    puts("No Solution!");
}

网络流24题之七 试题库问题

题目描述

输入输出格式

输入输出样例

网络流24题之七试题库问题