- #include#include#include using namespace std;
- const int inf = 0x3f3f3f3f;
- struct edge {
- int from,
- v,
- flow;
- }
- e[50010];
- int S = 0,
- T,
- tot = 1,
- first[4000],
- q[4000],
- a[25][25],
- cur[4000],
- d[4000],
- p[4000],
- n,
- m,
- k;
- void insert(int u, int v, int w) {
- tot++;
- e[tot].v = v;
- e[tot].flow = w;
- e[tot].from = first[u];
- first[u] = tot;
- tot++;
- e[tot].v = u;
- e[tot].flow = 0;
- e[tot].from = first[v];
- first[v] = tot;
- }
- bool bfs() {
- memset(d, -1, sizeof(d));
- int head = 0,
- tail = 1;
- q[0] = 0;
- d[0] = 0;
- while (head != tail) {
- int x = q[head++];
- if (head >= 501) head = 0;
- for (int i = first[x]; i; i = e[i].from) if (d[e[i].v] == -1 && e[i].flow > 0) {
- q[tail++] = e[i].v;
- if (tail >= 501) tail = 0;
- d[e[i].v] = d[x] + 1;
- }
- }
- if (d[T * 22 + n + 1] == -1) return 0;
- return 1;
- }
- int dfs(int x, int a) {
- if (x == T * 22 + n + 1 || a == 0) return a;
- int flow = 0,
- f;
- for (int & i = cur[x]; i; i = e[i].from) if (d[e[i].v] == d[x] + 1 && (f = dfs(e[i].v, min(a, e[i].flow))) > 0) {
- e[i].flow -= f;
- e[i ^ 1].flow += f;
- flow += f;
- a -= f;
- if (a == 0) break;
- }
- return flow;
- }
- int main() {
- scanf("%d%d%d", &n, &m, &k);
- for (int i = 1; i <= m; i++) {
- scanf("%d%d", &p[i], &a[i][0]);
- for (int j = 1; j <= a[i][0]; j++) {
- scanf("%d", &a[i][j]);
- if (a[i][j] == -1) a[i][j] = n + 1;
- }
- }
- for (T = 1; T <= 100; T++) {
- for (int i = 0; i <= n + 1; i++) {
- insert((T - 1) * 22 + i, T * 22 + i, inf);
- }
- for (int i = 1; i <= m; i++) {
- int u = (T - 1) * 22 + a[i][(T - 1) % a[i][0] + 1];
- int v = T * 22 + a[i][T % a[i][0] + 1];
- insert(u, v, p[i]);
- }
- while (bfs()) {
- for (int i = 0; i <= T * 22 + n + 1; i++) cur[i] = first[i];
- k -= dfs(0, inf);
- }
- if (k <= 0) {
- printf("%d", T);
- return 0;
- }
- }
- printf("0");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1956952.html