原题链接

题目大意

试题库有n道题，每道题有多个类别，现在要抽m道题组试卷，试卷对每种类型题目的数量有要求，每道题虽可以有多种类型，但却只能与一种类型相匹配。问是否有满足要求的组卷方案，若有则输出方案，若没有则输出“No Solution!”.

解题思路

还是按对象与关系的思路分析，对象有：试卷、试题、类别;
关系有：试卷对类别的数量要求、试题与类别的对应关系，试题的数量要求。
建图：试卷到$类别i$连容量为$k_i$的边，试题与类别按题目所给关系建立从类别指向试题的容量为1的边，试题向汇点连容量为1的边，判断$maxflow$是否等于$m$即可

#AC代码

输入样例

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 6 8
2: 7 9 10
3: 2 3 4 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (unsigned int)(-1)>>1;
const int MAX_V=1500;
struct edge {
	int to,cap,rev;
};

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];  
void add_edge(int from,int to,int cap) {
	G[from].push_back((edge) {
		to,cap,G[to].size()
	});
	G[to].push_back((edge) {
		from,0,G[from].size()-1
	});
}
void bfs(int s) {
	memset(level,-1,sizeof(level));

	queue<int> que;

	level[s]=0;

	que.push(s);

	while(!que.empty()) {
		int v = que.front();
		que.pop();

		for(int i=0; i<G[v].size(); i++) {
			edge &e = G[v][i];

			if(e.cap > 0 && level[e.to]<0) {
				level[e.to] = level[v] +1;
				que.push(e.to);
			}
		}
	}
}

int dfs(int v,int t,int f) {
	if(v == t)return f;

	for(int &i=iter[v]; i<G[v].size(); i++) {
		edge &e = G[v][i];
		if(e.cap > 0 && level[v] < level[e.to]) {
			int d =dfs(e.to,t,min(f,e.cap));

			if(d>0) {
				e.cap -= d;

				G[e.to][e.rev].cap += d;

				return d;
			}
		}
	}

	return 0;
}

int max_flow(int s, int t) {
	int flow = 0;

	for(;;) {
		bfs(s);

		if(level[t]<0)return flow;
		memset(iter,0,sizeof(iter));

		int f;

		while((f= dfs(s,t,INF))>0) {
			flow += f;
		}
	}
}

int main(){
    int k,n,m=0;
    cin>>k>>n;
    int s=0,t=k+n+1;
    int c,d;
    for(int i=1;i<=k;++i){
        cin>>c;
        m+=c;
        add_edge(s,i,c);
    }
    for(int i=k+1;i<=k+n;++i){
        cin>>c;
        for(ll j=1;j<=c;++j){
            cin>>d;
            add_edge(d,i,1);
        }
        add_edge(i,t,1);
    }

    int ans=max_flow(s,t);
    
    if(ans==m){
        for(int i=1;i<=k;++i){
            cout<<i<<":";
            for(int j=0;j<G[i].size();++j){
                edge &e = G[i][j];
                if(e.cap==0&&e.to>=k+1&&e.to<=k+n){
                    cout<<" "<<e.to-k;
                }
            }
            cout<<endl;
        }
    }
    else{
        cout<<"No Solution!";
    }
}