[luoguP2763] 试题库问题（最大流）

传送门

每个类别和它所有的试题连一条权值为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

上一篇：[luoguP2766] 最长递增子序列问题（最大流）

下一篇：[luoguP2774] 方格取数问题（最大点权独立集）

---

最大流 网络流