P3254 圆桌问题网络流

题目描述

«问题描述：

假设一个试题库中有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


建图非常好建   输出的话枚举公司发出的边 如果流量不为0 说明是满流的然后输出即可

跑到最大流的时候  正向边为0  方向边跑满

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=4e5+44;
const int M=4e6+54;

struct edge {
    int to, next, w;
} e[M << 1];
int head[N], cnt = 1;
void add(int x, int y, int z) {
    e[++cnt] = (edge){y, head[x], z};
    head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0};
    head[y] = cnt;
}
int level[N];
bool bfs(int s, int t) {
    memset(level, 0, sizeof level);
    queue<int> q;
    level[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int pos = q.front();
        q.pop();
        for (int i = head[pos]; i; i = e[i].next) {
            int nx = e[i].to;
            if (!e[i].w || level[nx]) continue;
            level[nx] = level[pos] + 1;
            q.push(nx);
        }
    }
    return level[t];
}
int dfs(int s, int t, int flow) {
    if (s == t) return flow;
    int ret = 0;
    for (int i = head[s]; flow && i; i = e[i].next) {
        int nx = e[i].to;
        if (level[nx] == level[s] + 1 && e[i].w) {
            int tmp = dfs(nx, t, min(flow, e[i].w));
            e[i].w -= tmp;
            e[i ^ 1].w += tmp;
            flow -= tmp;
            ret += tmp;
        }
    }
    if (!ret) level[s] = 0;
    return ret;
}
int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) ret += dfs(s, t, inf);
    return ret;
}

int n,m,s,t,sum;
int main()
{
    RII(n,m);
    rep(i,1,n)
    rep(j,1,m)
    add(i,j+n,1);
    s=n+m+1,t=s+1;

    rep(i,1,n)
    {
        int x;RI(x);add(s,i,x);sum+=x;
    }
    rep(i,n+1,n+m)
    {
        int x;RI(x);add(i,t,x);
    }
    
    int ans=dinic(s,t);
    if(ans!=sum)
        cout<<"0";
    else
    {
        cout<<"1"<<endl;
        rep(i,1,n)
        {
            for(int j=head[i];j;j=e[j].next)
            {
                int v=e[j].to;
                if(v!=s&&!e[j].w)
                printf("%d ",v-n);
            }
            cout<<endl;
        }
    }
    return 0;
}

View Code

很明显 贪心也可以做

P3254 圆桌问题 网络流

题目描述

输入输出格式

输入输出样例

P3254 圆桌问题网络流