洛谷 P4843 清理雪道
? 解题记录 ? ? 洛谷 ? ? 网络流 ? ? 上下界网络流 ?    2018-12-05 23:08:48    359    0    0

题目描述

滑雪场坐落在FJ省西北部的若干座山上。

从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向。

你的团队负责每周定时清理雪道。你们拥有一架直升飞机,每次飞行可以从总部带一个人降落到滑雪场的某个地点,然后再飞回总部。从降落的地点出发,这个人可以顺着斜坡向下滑行,并清理他所经过的雪道。

由于每次飞行的耗费是固定的,为了最小化耗费,你想知道如何用最少的飞行次数才能完成清理雪道的任务。

输入输出格式

输入格式:

 

输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。

接下来的n行,描述1~n号地点出发的斜坡,第i行的第一个数为mi (0 <= mi < n) ,后面共有mi个整数,由空格隔开,每个整数aij互不相同,代表从地点i下降到地点aij的斜坡。每个地点至少有一个斜坡与之相连。

 

输出格式:

 

输出文件的第一行是一个整数k – 直升飞机的最少飞行次数。

 

输入输出样例

输入样例#1: 复制
  1. 8
  2. 1 3
  3. 1 7
  4. 2 4 5
  5. 1 8
  6. 1 8
  7. 0
  8. 2 6 5
  9. 0
输出样例#1: 复制
  1. 4​​

 

 打一打上下界网络流,其实就是个下界最小流。

显然,一条边至少被经过一次,就是流量至少为1,然后可以从每一个点出发,每一个点终止,就源点连所有点连1,所有点连汇点连1就行了。

注意上下界最小流要先求出可行流再反向增广。


  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<queue>
  6. #define LL long long
  7. using namespace std;
  8. const int maxn = 2e2 + 5;
  9. const int maxm = 5e4 + 5;
  10. const LL inf = 0x3f3f3f3f3f3f3f3f;
  11. const int iinf = 0x3f3f3f3f;
  12. struct edge {
  13. int v, w, next;
  14. } e[maxm];
  15. int head[maxn], cnt;
  16. void adde(const int &u, const int &v, const int &w) {
  17. e[cnt] = (edge) {v, w, head[u]};
  18. head[u] = cnt++;
  19. e[cnt] = (edge) {u, 0, head[v]};
  20. head[v] = cnt++;
  21. }
  22.  
  23. int layer[maxn], iter[maxn], SS, TT, n, m, S, T, u, v, w;
  24.  
  25. void ADDE(const int &u, const int &v, const int &l, const int &r) {
  26. //cerr << u << "------" << l << "," << r << "----->" << v << endl;
  27. adde(SS, v, l);
  28. adde(u, TT, l);
  29. adde(u, v, r - l);
  30. }
  31.  
  32. bool bfs(int s, int t) {
  33. queue<int > q;
  34. memcpy(iter, head, sizeof(head));
  35. memset(layer, 0, sizeof(layer));
  36. layer[s] = 1, q.push(s);
  37. while(!q.empty()) {
  38. int u = q.front(); q.pop();
  39. for(register int i = head[u]; ~i; i = e[i].next) {
  40. int v = e[i].v;
  41. if(!e[i].w || layer[v]) continue;
  42. layer[v] = layer[u] + 1;
  43. q.push(v);
  44. }
  45. }
  46. return layer[t];
  47. }
  48.  
  49. LL dfs(int u, int t, LL mn) {
  50. LL ret = 0, tmp;
  51. if(u == t)
  52. return mn;
  53. for(register int &i = iter[u]; ~i; i = e[i].next) {
  54. int v = e[i].v;
  55. if(!e[i].w || layer[v] != layer[u] + 1) continue;
  56. tmp = dfs(v, t, min((LL)e[i].w, mn - ret));
  57. e[i].w -= tmp, e[i ^ 1].w += tmp, ret += tmp;
  58. if(ret == mn) return ret;
  59. }
  60. return ret;
  61. }
  62.  
  63. LL Dinic(int s, int t) {
  64. LL ans = 0;
  65. while(bfs(s, t))
  66. ans += dfs(s, t, inf);
  67. return ans;
  68. }
  69.  
  70. int L[maxn], R[maxn], id[maxn], od[maxn], icnt;
  71. LL solve() {
  72. LL res = Dinic(SS, TT);
  73. res = e[cnt - 1].w;
  74. for(register int i = head[SS]; ~i; i = e[i].next)
  75. e[i].w = e[i ^ 1].w = 0;
  76. for(register int i = head[TT]; ~i; i = e[i].next)
  77. e[i].w = e[i ^ 1].w = 0;
  78. e[cnt - 1].w = e[cnt - 2].w = 0;
  79. return res - Dinic(T, S);
  80. }
  81.  
  82. int main() {
  83. memset(head, -1, sizeof(head));
  84. scanf("%d", &n);
  85. for(register int i = 1; i <= n; ++i)
  86. L[i] = ++icnt, R[i] = ++icnt;
  87. S = ++icnt, T = ++icnt, SS = ++icnt, TT = ++icnt;
  88. for(register int i = 1; i <= n; ++i) {
  89. scanf("%d", &u);
  90. for(register int j = 1; j <= u; ++j)
  91. scanf("%d", &v), ADDE(i, v, 1, iinf);
  92. }
  93. for(register int i = 1; i <= n; ++i)
  94. ADDE(S, i, 0, iinf), ADDE(i, T, 0, iinf);
  95. adde(T, S, iinf);
  96. printf("%lld", solve());
  97. return 0;
  98. }


上一篇: LOJ#2541. 「PKUWC2018」猎人杀

下一篇: SP705 SUBST1 - New Distinct Substrings

359 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航