做了几道网络流的题后，就感觉这道题还是挺简单的了……
这是一个二分图多重匹配问题，关键还是在建图：图的右侧是k个节点，代表每一个类型的试卷，然后都连一条容量为该类型题数通往汇点的边。图的左侧是每一个试题，因为每一个试题只能用一次，所以和源点连一条容量为1的边。然后如果试题 i 属于第 j 类试题，就在 (i, j + n)之间连一条边（j + n是为了防止编号重复，边全只要大于0就行，因为从源点出发，每一道题都限制了只能用一次）。
然后跑最大流就行了，只要判断最大流是否等于m就行。
输出方案就是对于 i : 1~k，遍历他的所有出边，如果指向 j (1 <= j <= n)，且这条边流了-1，就说明 j 试题被选进了第 i 类试题中。为什么是流了-1呢？因为这条边是反向的，从(j, i)流了1，那么(i, j)就流了-1.
1 #include<cstdio>
2 #include<iostream>
3 #include<cmath>
4 #include<algorithm>
5 #include<cstring>
6 #include<cstdlib>
7 #include<cctype>
8 #include<vector>
9 #include<stack>
10 #include<queue>
11 using namespace std;
12 #define enter puts("")
13 #define space putchar(' ')
14 #define Mem(a) memset(a, 0, sizeof(a))
15 typedef long long ll;
16 typedef double db;
17 const int INF = 0x3f3f3f3f;
18 const db eps = 1e-8;
19 const int maxn = 1025;
20 inline ll read()
21 {
22 ll ans = 0;
23 char ch = getchar(), last = ' ';
24 while(!isdigit(ch)) {last = ch; ch = getchar();}
25 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();}
26 if(last == '-') ans = -ans;
27 return ans;
28 }
29 inline void write(ll x)
30 {
31 if(x < 0) x = -x, putchar('-');
32 if(x >= 10) write(x / 10);
33 putchar(x % 10 + '0');
34 }
35
36 int k, n, t, sum = 0;
37
38 struct Edge
39 {
40 int from, to, cap, flow;
41 };
42 vector<Edge> edges;
43 vector<int> G[maxn << 1];
44 void addEdge(int from, int to, int w)
45 {
46 edges.push_back((Edge){from, to, w, 0});
47 edges.push_back((Edge){to, from, 0, 0});
48 int sz = edges.size();
49 G[from].push_back(sz - 2);
50 G[to].push_back(sz - 1);
51 }
52
53 int dis[maxn << 1];
54 bool bfs()
55 {
56 Mem(dis); dis[0] = 1;
57 queue<int> q; q.push(0);
58 while(!q.empty())
59 {
60 int now = q.front(); q.pop();
61 for(int i = 0; i < (int)G[now].size(); ++i)
62 {
63 Edge& e = edges[G[now][i]];
64 if(!dis[e.to] && e.cap > e.flow)
65 {
66 dis[e.to] = dis[now] + 1;
67 q.push(e.to);
68 }
69 }
70 }
71 return dis[t];
72 }
73 int cur[maxn << 1];
74 int dfs(int now, int res)
75 {
76 if(now == t || res == 0) return res;
77 int flow = 0, f;
78 for(int& i = cur[now]; i < (int)G[now].size(); ++i)
79 {
80 Edge& e = edges[G[now][i]];
81 if(dis[e.to] == dis[now] + 1 && (f = dfs(e.to, min(res, e.cap - e.flow))) > 0)
82 {
83 e.flow += f;
84 edges[G[now][i] ^ 1].flow -= f;
85 flow += f;
86 res -= f;
87 if(res == 0) break;
88 }
89 }
90 return flow;
91 }
92
93 int maxflow()
94 {
95 int flow = 0;
96 while(bfs())
97 {
98 Mem(cur);
99 flow += dfs(0, INF);
100 }
101 return flow;
102 }
103
104 int main()
105 {
106 k = read(); n = read();
107 t = k + n + 1;
108 for(int i = 1; i <= k; ++i) {int x = read(); sum += x; addEdge(n + i, t, x);}
109 for(int i = 1; i <= n; ++i)
110 {
111 int p = read();
112 addEdge(0, i, 1);
113 for(int j = 1; j <= p; ++j) addEdge(i, n + read(), 1);
114 }
115 if(maxflow() != sum) printf("No Solution!\n");
116 else
117 {
118 for(int i = 1; i <= k; ++i)
119 {
120 write(i); putchar(':'); space;
121 for(int j = 0; j < (int)G[i + n].size(); ++j)
122 {
123 Edge e = edges[G[i + n][j]];
124 if(e.to <= n && e.flow == -1) write(e.to), space;
125 }
126 enter;
127 }
128 }
129 return 0;
130 }
View Code