传送门
每个类别和它所有的试题连一条权值为1的边。
增加一个超级源点s，s和每个类别连一条权值为选当前类别数量的边。
增加一个超级汇点t，每个试题和t连一条权值为1的边。
求最大流即可。
——代码
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define min(x, y) ((x) < (y) ? (x) : (y)) 6 #define N 1100 7 #define M 3000001 8 9 int k, n, m, cnt, s, t, sum; 10 int num[N], a[N][N]; 11 int head[N], to[M], next[M], val[M], dis[N], cur[N]; 12 13 inline int read() 14 21 22 inline void add(int x, int y, int z) 23 29 30 inline bool bfs() 31 49 } 50 } 51 return 0; 52 } 53 54 inline int dfs(int u, int maxflow) 55 70 } 71 return ret; 72 } 73 74 int main() 75 86 memset(head, 1, sizeof(head)); 87 for(i = 1; i <= n; i++) add(i, t, 1), add(t, i, 0); 88 for(i = 1; i <= k; i++) add(s, i + n, num[i]), add(i + n, s, 0); 89 for(i = 1; i <= k; i++) 90 for(j = 1; j <= a[i][0]; j++) 91 add(i + n, a[i][j], 1), add(a[i][j], i + n, 0); 92 while(bfs()) 93 97 if(sum ^ m) 98 102 for(i = n + 1; i <= n + k; i++) 103 110 return 0; 111 }View Code
上一篇：[HDU3518]Boring counting（后缀数组）
下一篇：[luoguP2890] [USACO07OPEN]便宜的回文Cheapest Palindrome（DP）
网络流 最大流
