首页 > 代码库 > 【BZOJ2409】 地下车会

【BZOJ2409】 地下车会

Description

小Y喜欢速度与激情,于是他参加了地下车会。  地下车会设有N 个
分赛区,M种赛事。每个分赛区有C[i]场比赛。由于地下车会经营者
想要赚到更多的钱,规定小 Y 必须参加某一些赛区的一些赛事。且
每个赛区至少参加L[i]场比赛。小Y不想在一个地区逗留太久惹上麻
烦,所以每个赛区他最多参加P[i]场比赛。可能是因为经营者对新手
有歧视心理,规定了小 Y 每种赛事最多只能进行 A[i]场比赛。小 Y
这个月资金有点紧张,他算了算自己最多只能够维护车子跑 K 场比
赛。由于小 Y 是新手,所以他希望积累更多的经验,也就是跑尽可
能多的赛事。

Input

第一行三个数N,M,K,用空格隔开。 
接下来N行,每行第一个数C[i],接下来 C[i]个数,代表每场比赛的
种类,种类可能重复。 
接下来一行一个数F,代表规定条数。 
接下来 F 行,每行两个数 A,B,代表小 Y 必须参加 A 赛区的 B 种
赛事一次及以上。一种规定只会出现一次。 
接下来一行M个数,代表A[i]。 
接下来N行,每行两个数P[i],L[i]。

Output

第一行一个数ans,表示小Y最多能跑几场赛事。

Sample Input

5 5 15
5 1 1 2 2 3
6 2 2 3 4 5 5
3 1 2 3
6 1 2 3 4 5 5
4 3 3 4 4
3
1 2
2 5
5 3
2 2 3 2 3
4 2
4 2
2 1
5 3
3 1

Sample Output

12

HINT

 

前 100% 的数据, 1<=N<=500 , 1<=M<=500 , 1<=C[i]<=500 ,

1<=F<=100000 

【友情提示】 

对于所有的数据, 1<=L[i]<=P[i]<=C[i], 1<=A[i]<=10^4, K<= 200000,

数据保证合法。 

Solution

依题意构图,跑上下界最大流。

Code

  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4   5 #define maxn 510  6 #define R register  7 #define inf 0x7fffffff  8 #define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))  9 int id2[maxn], id3[maxn], tot, num[maxn][maxn]; 10 int s, t, ans, deg[maxn << 2]; 11 bool req[maxn][maxn]; 12 struct Edge { 13     Edge *next, *rev; 14     int to, cap; 15 } *cur[maxn << 2], *last[maxn << 2], e[maxn * maxn << 2], *ecnt = e; 16 inline void link(R int a, R int b, R int w) 17 { 18     *++ecnt = (Edge) {last[a], ecnt + 1, b, w}; last[a] = ecnt; 19     *++ecnt = (Edge) {last[b], ecnt - 1, a, 0}; last[b] = ecnt; 20 } 21 int q[maxn << 2], dep[maxn << 2]; 22 inline bool bfs() 23 { 24     memset(dep, -1, (t + 1) << 2); 25     R int head = 0, tail = 1; dep[q[1] = t] = 0; 26     while (head < tail) 27     { 28         R int now = q[++head]; 29         for (R Edge *iter = last[now]; iter; iter = iter -> next) 30             if (iter -> rev -> cap && dep[iter -> to] == -1) 31                 dep[q[++tail] = iter -> to] = dep[now] + 1; 32     } 33     return dep[s] != -1; 34 } 35 int dfs(R int x, R int f) 36 { 37     if (x == t) return f; 38     R int used = 0; 39     for (R Edge* &iter = cur[x]; iter; iter = iter -> next) 40         if (iter -> cap && dep[iter -> to] + 1 == dep[x]) 41         { 42             R int v = dfs(iter -> to, dmin(f - used, iter -> cap)); 43             iter -> cap -= v; 44             iter -> rev -> cap += v; 45             used += v; 46             if (f == used) return f; 47         } 48     return used; 49 } 50 void dinic() 51 { 52     while (bfs()) 53     { 54         memcpy(cur, last, sizeof last); 55         ans += dfs(s, inf); 56     } 57 } 58 int main() 59 { 60     R int n, m, k; tot = 1; scanf("%d%d%d", &n, &m, &k); link(s, 1, k); 61     for (R int i = 1; i <= m; ++i) id3[i] = ++tot; 62     for (R int i = 1; i <= n; ++i) 63     { 64         R int c; scanf("%d", &c); 65         id2[i] = ++tot; 66         for (R int j = 1; j <= c; ++j) 67         { 68             R int x; scanf("%d", &x); 69             ++num[i][x]; 70         } 71     } 72     R int F; scanf("%d", &F); 73     for (R int i = 1; i <= F; ++i) 74     { 75         R int a, b; scanf("%d%d", &a, &b); req[a][b] = 1; 76     } 77     t = ++tot; 78     for (R int i = 1; i <= m; ++i) 79     { 80         R int a; scanf("%d", &a); 81         link(id3[i], t, a); 82     } 83     for (R int i = 1; i <= n; ++i) 84     { 85         R int p, l; scanf("%d%d", &p, &l); 86         link(1, id2[i], p - l); deg[1] += l; deg[id2[i]] -= l; 87     } 88     for (R int i = 1; i <= n; ++i) 89         for (R int j = 1; j <= m; ++j) 90             if (req[i][j]) 91             { 92                 link(id2[i], id3[j], num[i][j] - 1); 93                 ++deg[id2[i]]; --deg[id3[j]]; 94             } 95             else if (num[i][j]) link(id2[i], id3[j], num[i][j]); 96     R int os = s, ot = t; link(t, s, inf); 97     s = ++tot; t = ++tot; 98     for (R int i = 1; i <= tot; ++i) deg[i] > 0 ? link(i, t, deg[i]) : link(s, i, -deg[i]); 99     dinic();100     s = os; t = ot; ans = 0;101     dinic();102     printf("%d\n", ans);103     return 0;104 }

 

【BZOJ2409】 地下车会