【题目链接】点击打开链接

【解题方法】这道题和圆桌问题没什么区别,都属于多重匹配。方法完全一样。

【问题分析】

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

【建模方法】

建立二分图,每个类别为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集合每个点都有完备的多重匹配。


//
//Created by just_sort 2016/12/30
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define MP(x, y) make_pair(x,y)
const int maxn = 2e4+10;
const int maxm = 2e5;
const int m = 1e4;
const int maxs = 10;
const int INF = 1e9;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head

struct G
{
    int v, cap, next;
    G() {}
    G(int v, int cap, int next) : v(v), cap(cap), next(next) {}
} E[maxm];
int p[maxn], T;
int d[maxn], temp_p[maxn], qw[maxn]; //d顶点到源点的距离标号,temp_p当前狐优化,qw队列
void init()
{
    memset(p, -1, sizeof(p));
    T = 0;
}
void add(int u, int v, int cap)
{
    E[T] = G(v, cap, p[u]);
    p[u] = T++;
    E[T] = G(u, 0, p[v]);
    p[v] = T++;
}
bool bfs(int st, int en, int n)
{
    int i, u, v, head, tail;
    for(i = 0; i <= n; i++) d[i] = -1;
    head = tail = 0;
    d[st] = 0;
    qw[tail] = st;
    while(head <= tail)
    {
        u = qw[head++];
        for(i = p[u]; i + 1; i = E[i].next)
        {
            v = E[i].v;
            if(d[v] == -1 && E[i].cap > 0)
            {
                d[v] = d[u] + 1;
                qw[++tail] = v;
            }
        }
    }
    return (d[en] != -1);
}
int dfs(int u, int en, int f)
{
    if(u == en || f == 0) return f;
    int flow = 0, temp;
    for(; temp_p[u] + 1; temp_p[u] = E[temp_p[u]].next)
    {
        G& e = E[temp_p[u]];
        if(d[u] + 1 == d[e.v])
        {
            temp = dfs(e.v, en, min(f, e.cap));
            if(temp > 0)
            {
                e.cap -= temp;
                E[temp_p[u] ^ 1].cap += temp;
                flow += temp;
                f -= temp;
                if(f == 0)  break;
            }
        }
    }
    return flow;
}
int dinic(int st, int en, int n)
{
    int i, ans = 0;
    while(bfs(st, en, n))
    {
        for(i = 0; i <= n; i++) temp_p[i] = p[i];
        ans += dfs(st, en, INF);
    }
    return ans;
}
vector <int> type[50];
int main()
{
    init();
    int k, n;
    scanf("%d%d", &k, &n);
    int sum = 0;
    for(int i = 1; i <= k; i++){
        int x;
        scanf("%d", &x);
        sum += x;
        add(n + i, n + k + 1, x);
    }
    for(int i = 1; i <= n; i++){
        int p, x;
        add(0, i, 1);
        scanf("%d", &p);
        while(p--){
            scanf("%d", &x);
            add(i, n + x, 1);
        }
    }
    int ans = dinic(0, n + k + 1, n + k + 1);
    if(ans != sum)
    {
        printf("No Solution!\n");
        return 0;
    }
    for(int i = 0; i < 50; i++) type[i].clear();
    for(int i = 1; i <= n; i++){
        for(int j = p[i]; ~j; j = E[j].next){
            int v = E[j].v;
            if(v > n && E[j].cap == 0){
                type[v - n].push_back(i);
                break;
            }
        }
    }
    for(int i = 1; i <= k; i++){
        printf("%d: ", i);
        int sz = type[i].size();
        for(int j = 0; j < sz; j++){
            printf("%d ", type[i][j]);
        }
        printf("\n");
    }
    return 0;
}