设为首页收藏本站
开启辅助访问 切换到窄版

华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
华师一附中OI组»论坛 › HSYIT › 水区 › 2015 HSYIT代码暂存楼[0]
123456
返回列表 发新帖
楼主: smileandyxu
打印 上一主题 下一主题

2015 HSYIT代码暂存楼[0]

[复制链接]
smileandyxu

1

主题

49

帖子

277

积分

中级会员

Rank: 3Rank: 3

积分
277
51#
 楼主| 发表于 2016-5-17 13:52:32 | 只看该作者
  1. #include <iostream>
  2. using namespace std;
  3. struct node {
  4.     node* ch[2];
  5.     double v;
  6.     int s;
  7.     node(int val): v(val), s(1) { }
  8.     int cmp(double x) const
  9.     {
  10.         if (x == v)
  11.             return -1;
  12.         return x < v ? 0 : 1;
  13.     }
  14. };
  15. const node* null;
  16. void rotate(node* &o, int d)
  17. {
  18.     node* k = o->ch[d ^ 1];
  19.     o->ch[d ^ 1] = k->ch[d];
  20.     k->ch[d] = o;
  21.     k->s = o->s;
  22.     o->s = o->ch[0]->s + o->ch[1]->s;
  23.     o = k;
  24. }
  25. void
  26. int main()
  27. {

  29.     return 0;
  30. }
复制代码
回复 支持 反对

使用道具 举报

smileandyxu

1

主题

49

帖子

277

积分

中级会员

Rank: 3Rank: 3

积分
277
52#
 楼主| 发表于 2016-5-17 16:04:55 | 只看该作者
  1. #include <iostream>
  2. using namespace std;
  3. struct node {
  4.     node* ch[2];
  5.     int v;
  6.     int s;
  7.     int cmp(int x) const
  8.     {
  9.         if (x == v)
  10.             return -1;
  11.         return x < v ? 0 : 1;
  12.     }
  13. };
  14. node* null = new node();
  15. node* newnode(int x)
  16. {
  17.     node* tmp = new node();
  18.     tmp->ch[0] = null;
  19.     tmp->ch[1] = null;
  20.     tmp->v = x;
  21.     tmp->s = 1;
  22.     return tmp;
  23. }
  24. int rank(node* o, int x)
  25. {
  26.     if (o == null)
  27.         return -1;
  28.     if (o->cmp(x) == -1)
  29.         return 1;
  30.     else if (o->cmp(x) == 0)
  31.         return rank(o->ch[0], x);
  32.     else
  33.         return o->ch[0]->s + rank(o->ch[1], x);
  34. }
  35. node* find_kth(node* o, int k)
  36. {
  37.     if (k == 1) {
  38.         while (o->ch[0] != null)
  39.             o = o->ch[0];
  40.         return o;
  41.     }
  42.     else {
  43.         if (o->ch[0]->s >= k)
  44.             return find_kth(o->ch[0], k);
  45.         else
  46.             return find_kth(o->ch[1], k - o->ch[0]->s);
  47.     }
  48. }
  49. node* precursor(node* o, int x)
  50. {
  51.     return find_kth(o, rank(o, x) - 1);
  52. }
  53. node* successor(node* o, int x)
  54. {

  56.     return find_kth(o, rank(o, x) + 1);
  57. }
  58. void rotate(node* &o, int d)
  59. {
  60.     node* k = o->ch[d ^ 1];
  61.     o->ch[d ^ 1] = k->ch[d];
  62.     k->ch[d] = o;
  63.     k->s = o->s;
  64.     o->s = o->ch[0]->s + o->ch[1]->s;
  65.     o = k;
  66. }
  67. void maintain(node* o, bool d)
  68. {
  69.     if (!d) {
  70.         if (o->ch[0]->ch[0]->s > o->ch[1]->s)
  71.             rotate(o, 1);
  72.         else if (o->ch[0]->ch[1]->s > o->ch[1]->s) {
  73.             rotate(o->ch[0], 0);
  74.             rotate(o, 1);
  75.         }
  76.         else
  77.             return;
  78.     }
  79.     else {
  80.         if (o->ch[1]->ch[1]->s > o->ch[0]->s)
  81.             rotate(o, 0);
  82.         else if (o->ch[1]->ch[0]->s > o->ch[0]->s) {
  83.             rotate(o->ch[1], 1);
  84.             rotate(o, 0);
  85.         }
  86.         else
  87.             return;
  88.     }
  89.     cout << "#";
  90.     maintain(o->ch[0], false);
  91.     maintain(o->ch[1], true);
  92.     maintain(o, false);
  93.     maintain(o, true);
  94. }
  95. void insert(node* &o, int x)
  96. {
  97.     if (o == null)
  98.         o = newnode(x);
  99.     else {
  100.         if (o->cmp(x) == 0)
  101.             insert(o->ch[0], x);
  102.         else
  103.             insert(o->ch[1], x);
  104.         ++o->s;
  105.         maintain(o, false);
  106.         maintain(o, true);
  107.     }
  108. }
  109. void erase(node* &o, int x)
  110. {
  111.     if (o->cmp(x) == -1) {
  112.         if (o->ch[0] == null && o->ch[1] == null)
  113.             o = null;
  114.         else if (o->ch[0] == null)
  115.             o = o->ch[1];
  116.         else if (o->ch[1] == null)
  117.             o = o->ch[0];
  118.         else {
  119.             node* tmp = find_kth(o->ch[1], 1);
  120.             o->v = tmp->v;
  121.             erase(o->ch[1], tmp->v);
  122.             --o->s;
  123.         }
  124.     }
  125.     else {
  126.         if (o->cmp(x) == 0)
  127.             erase(o->ch[0], x);
  128.         else {
  129.             erase(o->ch[1], x);
  130.         }
  131.         --o->s;
  132.     }
  133. }
  134. node* T = null;
  135. int n;
  136. int main()
  137. {
  138.     cin >> n;
  139.     null->ch[0] = null;
  140.     null->ch[1] = null;
  141.     for (int i = 0, p; i != n; ++i) {
  142.         int x;
  143.         cin >> p >> x;
  144.         if (p == 1)
  145.             insert(T, x);
  146.         if (p == 2)
  147.             erase(T, x);
  148.         if (p == 3)
  149.             cout << rank(T, x) << endl;
  150.         if (p == 4)
  151.             cout << find_kth(T, x)->v << endl;
  152.         if (p == 5)
  153.             cout << precursor(T, x)->v << endl;
  154.         if (p == 6)
  155.             cout << successor(T, x)->v << endl;
  156.     }
  157.     return 0;
  158. }
复制代码
回复 支持 反对

使用道具 举报

smileandyxu

1

主题

49

帖子

277

积分

中级会员

Rank: 3Rank: 3

积分
277
53#
 楼主| 发表于 2016-5-18 13:53:55 | 只看该作者
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <set>
  4. using namespace std;
  5. set<int> G[501][501];
  6. int F[501][501];
  7. int B[501];
  8. int C[501];
  9. int W[501];
  10. int P[501];
  11. int L[501];
  12. int n;
  13. void mysearch(int i, int p)
  14. {
  15.     if (F[i][p] != 0 || i == 0)
  16.         return;
  17.     else if (W[i] > p) {
  18.         mysearch(B[i], p);
  19.         F[i][p] = F[B[i]][p];
  20.         G[i][p] = G[B[i]][p];
  21.     }
  22.     else if (W[i] == p) {
  23.         F[i][p] = L[i];
  24.         G[i][p].insert(i);
  25.     }
  26.     else {
  27.         mysearch(B[i], p);
  28.         mysearch(B[i], p - W[i]);
  29.         mysearch(C[i], p - W[i]);
  30.         F[i][p] = F[B[i]][p];
  31.         G[i][p] = G[B[i]][p];
  32.         for (int k = 0; k <= p - W[i]; ++k) {
  33.             if (k <= P[i] && p - W[i] - k <= P[i] && p - W[i] - k >= 0) {
  34.                 mysearch(B[i], k);
  35.                 mysearch(C[i], p - W[i] - k);
  36.                 if (F[B[i]][k] + F[C[i]][p - W[i] - k] > F[i][p]) {
  37.                     F[i][p] = F[B[i]][k] + F[C[i]][p - W[i] - k];
  38.                     for (set<int>::iterator iter = G[B[i]][k].begin(); iter != G[B[i]][k].end(); ++iter)
  39.                         G[i][p].insert(*iter);
  40.                     for (set<int>::iterator iter = G[C[i]][p - W[i] - k].begin(); iter != G[C[i]][p - W[i] - k].end(); ++iter)
  41.                         G[i][p].insert(*iter);
  42.                 }
  43.             }
  44.         }
  45.     }
  46. }
  47. int main()
  48. {
  49.     cin >> n;
  50.     for (int i = 1, t; i <= n; ++i) {
  51.         cin >> t >> W[i] >> P[i] >> L[i];
  52.         int k = C[t];
  53.         C[t] = i;
  54.         B[i] = k;
  55.     }
  56.     for (int i = W[1]; i <= P[1] + W[1]; ++i)
  57.         mysearch(1, P[1] + W[1]);
  58.     cout << F[1][P[1] + W[1]];
  59.     cout << endl;
  60.     for (set<int>::iterator iter = G[1][P[1] + W[1]].begin(); iter != G[1][P[1] + W[1]].end(); ++iter)
  61.         cout << *iter << " ";
  62.     return 0;
  63. }
复制代码
回复 支持 反对

使用道具 举报

smileandyxu

1

主题

49

帖子

277

积分

中级会员

Rank: 3Rank: 3

积分
277
54#
 楼主| 发表于 2016-5-31 13:50:56 | 只看该作者
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #define esp 1e-7
  5. using namespace std;
  6. struct edge {
  7.     int beg;
  8.     int end;
  9.     int len;
  10.     int vel;
  11. };
  12. vector<edge> V;
  13. double D[201][501];
  14. int P[201];
  15. int m, n, d;
  16. void add(int a, int b, int v, int l)
  17. {
  18.     edge tmp;
  19.     tmp.beg = a;
  20.     tmp.end = b;
  21.     tmp.vel = v;
  22.     tmp.len = l;
  23.     V.push_back(tmp);
  24. }
  25. void spfa()
  26. {
  27.    
  28. }
  29. int main()
  30. {
  31.     cin >> n >> m >> d;
  32.     for (int i = 0, a, b, v, l; i != n; ++i) {
  33.         cin >> a >> b >> v >> l;
  34.         add(a, b, v, l);
  35.     }
  36.     spfa();
  37.    
  38.     return 0;
  39. }
复制代码
回复 支持 反对

使用道具 举报

smileandyxu

1

主题

49

帖子

277

积分

中级会员

Rank: 3Rank: 3

积分
277
55#
 楼主| 发表于 2016-5-31 15:47:35 | 只看该作者
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #define INF 0x3fffffff
  5. #define eps 1e-8
  6. using namespace std;
  7. struct edge {
  8.     int end;
  9.     int len;
  10.     int vel;
  11. };
  12. vector<edge> V[201];
  13. double D[201][501];
  14. int F[201][501];
  15. int G[201][501];
  16. int m, n, d;
  17. void add(int a, int b, int v, int l)
  18. {
  19.     edge tmp;
  20.     tmp.end = b;
  21.     tmp.vel = v;
  22.     tmp.len = l;
  23.     V[a].push_back(tmp);
  24. }
  25. void spfa()
  26. {
  27.     queue<int> Q;
  28.     queue<int> P;
  29.     bool B[201][501];
  30.     Q.push(0);
  31.     P.push(70);
  32.     B[0][70] = true;
  33.     D[0][70] = 0;
  34.     while (!Q.empty()) {
  35.         int k = Q.front();
  36.         int t = P.front();
  37.         B[k][t] = false;
  38.         Q.pop();
  39.         P.pop();
  40.         for (int i = 0; i != V[k].size(); ++i) {
  41.             if (V[k][i].vel == 0) {
  42.                 if (D[V[k][i].end][t] - D[k][t] + double(V[k][i].len) / double(t) > eps) {
  43.                     D[V[k][i].end][t] = D[k][t] + double(V[k][i].len) / double(t);
  44.                     F[V[k][i].end][t] = k;
  45.                     G[V[k][i].end][t] = t;
  46.                     cout << "change: " << V[k][i].end << "#" << t << " ====> " << k << "#" << t << endl;
  47.                     if (!B[V[k][i].end][t]) {
  48.                         Q.push(V[k][i].end);
  49.                         P.push(t);
  50.                         B[V[k][i].end][t] = true;
  51.                     }
  52.                 }
  53.             }
  54.             else {
  55.                 if (D[V[k][i].end][V[k][i].vel] - D[k][t] + double(V[k][i].len) / double(V[k][i].vel) > eps) {
  56.                     D[V[k][i].end][V[k][i].vel] = D[k][t] + double(V[k][i].len) / double(V[k][i].vel);
  57.                     F[V[k][i].end][V[k][i].vel] = k;
  58.                     G[V[k][i].end][V[k][i].vel] = t;
  59.                     cout << "change: " << V[k][i].end << "#" << V[k][i].vel << " ====> " << k << "#" << t << endl;
  60.                     if (!B[V[k][i].end][V[k][i].vel]) {
  61.                         Q.push(V[k][i].end);
  62.                         P.push(V[k][i].vel);
  63.                         B[V[k][i].end][V[k][i].vel] = true;
  64.                     }
  65.                 }
  66.             }
  67.         }
  68.     }
  69. }
  70. int cnt;
  71. void output(int x, int y)
  72. {
  73.     if (cnt <= 30)
  74.     cout << x << "#" << y << endl;
  75.     ++cnt;
  76.     if (F[x][y] != x && x != 0)
  77.         output(F[x][y], G[x][y]);
  78.     cout << x << " ";
  79. }
  80. int main()
  81. {
  82.     cin >> n >> m >> d;
  83.     for (int i = 0, a, b, v, l; i != m; ++i) {
  84.         cin >> a >> b >> v >> l;
  85.         add(a, b, v, l);
  86.     }
  87.     for (int i = 0; i != n; ++i) {
  88.         for (int j = 0; j <= 500; ++j) {
  89.             D[i][j] = INF;
  90.             F[i][j] = i;
  91.         }
  92.     }
  93.     spfa();
  94.     double tmp = INF;
  95.     int k = 0;
  96.     for (int i = 0; i <= 500; ++i) {
  97.         if (tmp - D[d][i] > eps) {
  98.             tmp = D[d][i];
  99.             k = i;
  100.         }
  101.     }
  102.     cout << "==================================" << endl;
  103.     output(d, k);
  104.     return 0;
  105. }
复制代码
回复 支持 反对

使用道具 举报

smileandyxu

1

主题

49

帖子

277

积分

中级会员

Rank: 3Rank: 3

积分
277
56#
 楼主| 发表于 2016-5-31 15:54:11 | 只看该作者
  1. #include <iostream>
  2. #include <set>
  3. #define INF 0x6fffffff
  4. using namespace std;
  5. set<int> S;
  6. int n, ans;
  7. int main()
  8. {
  9.     cin >> n;
  10.     cin >> ans;
  11.     S.insert(ans);
  12.     for (int i = 0, x; i != n - 1; ++i) {
  13.         cin >> x;
  14.         set<int>::iterator iter = S.find(x);
  15.         int minx = INF;
  16.         ++iter;
  17.         if (iter != S.end())
  18.             minx = min(minx, *iter - x);

  20.     }
  21.     return 0;
  22. }
复制代码
回复 支持 反对

使用道具 举报

smileandyxu

1

主题

49

帖子

277

积分

中级会员

Rank: 3Rank: 3

积分
277
57#
 楼主| 发表于 2016-6-14 15:54:37 | 只看该作者
  1. #include <iostream>
  2. #define father(x) (x >> 1)
  3. #define lchild(x) (x << 1)
  4. #define rchild(x) (x << 1 | 1)
  5. using namespace std;
  6. struct node {
  7.     int sum;
  8.     int add;
  9.     int left;
  10.     int right;
  11. };
  12. node T[800001];
  13. int L, R;
  14. int n, m;
  15. void update(int i)
  16. {
  17.     while (i > 0) {
  18.         T[i].sum = T[lchild(i)].sum + T[rchild(i)].sum;
  19.         i = father(i);
  20.     }
  21. }
  22. void build(int i, int l, int r)
  23. {
  24.     T[i].left = l;
  25.     T[i].right = r;
  26.     if (l != r) {
  27.         int d = (l + r) >> 1;
  28.         build(lchild(i), l, d);
  29.         build(rchild(i), d + 1, r);
  30.         T[i].sum = T[lchild(i)].sum + T[rchild(i)].sum;
  31.     }
  32. }
  33. int add(int i, int l, int r, int x)
  34. {
  35.     if (l == T[i].left && r == T[i].right) {
  36.         T[i].sum += x * (r - l + 1);
  37.         T[i].add += x;
  38.         return x * (r - l + 1);
  39.     }
  40.     else {
  41.         int d = (T[i].left + T[i].right) >> 1;
  42.         int s = 0;
  43.         if (l <= d)
  44.             s += add(lchild(i), l, d, x);
  45.         if (r >= d + 1)
  46.             s += add(rchild(i), d + 1, r, x);
  47.         T[i].sum += s;
  48.         return s;
  49.     }
  50. }
  51. void pushdown(int i)
  52. {
  53.     int len = (T[i].right - T[i].left + 1) >> 1;
  54.     T[lchild(i)].sum += T[i].add * len;
  55.     T[rchild(i)].sum += T[i].add * len;
  56.     T[lchild(i)].add += T[i].add;
  57.     T[rchild(i)].add += T[i].add;
  58.     T[i].add = 0;
  59. }
  60. int query(int i, int l, int r)
  61. {
  62.     if (l == T[i].left && r == T[i].right)
  63.         return T[i].sum;
  64.     else {
  65.         int d = (T[i].left + T[i].right) >> 1;
  66.         T[i].sum = 0;
  67.         pushdown(i);
  68.         if (l <= d)
  69.             T[i].sum += query(lchild(i), l, d);
  70.         if (r >= d + 1)
  71.             T[i].sum += query(rchild(i), d + 1, r);
  72.         return T[i].sum;
  73.     }
  74. }
  75. void print()
  76. {
  77.     cout << " ==> ";
  78.     for (int i = 1; i <= R; ++i)
  79.         cout << T[i].sum << " ";
  80.     cout << endl;
  81. }
  82. int main()
  83. {
  84.     cin >> n;
  85.     L = 1;
  86.     while (L < n)
  87.         L <<= 1;
  88.     R = L * 2 - 1;
  89.     cout << L << endl;
  90.     for (int i = 0; i != n; ++i)
  91.         cin >> T[L + i].sum;
  92.     build(1, 1, L);
  93.     cin >> m;
  94.     for (int i = 0, p, l, r, x; i != m; ++i) {
  95.         cin >> p;
  96.         if (p == 1) {
  97.             cin >> l >> r >> x;
  98.             add(1, l, r, x);
  99.         }
  100.         if (p == 2) {
  101.             cin >> l >> r;
  102.             cout << query(1, l, r) << endl;
  103.         }
  104.         print();
  105.     }
  106.     return 0;
  107. }
  108. /*
  109. 6
  110. 1 1 4 5 2 3
  111. 4
  112. 1 1 3 4
  113. 1 2 4 3
  114. 2 2 3
  115. 2 1 4
  116. */
复制代码
回复 支持 反对

使用道具 举报

smileandyxu

1

主题

49

帖子

277

积分

中级会员

Rank: 3Rank: 3

积分
277
58#
 楼主| 发表于 2016-6-15 13:46:49 | 只看该作者
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <stack>
  4. using namespace std;
  5. int P[200001];
  6. int Q[200001];
  7. int head, tail;
  8. int m, d, t, n;
  9. int main()
  10. {
  11.     cin >> m >> d;
  12.     for (int i = 0; i != m; ++i) {
  13.         char c;
  14.         int x;
  15.         cin >> c >> x;
  16.         if (c == 'A') {
  17.             ++n;
  18.             x = (x + t) % d;
  19.             while (head < tail && Q[tail - 1] <= x)
  20.                 --tail;
  21.             Q[tail] = x;
  22.             P[tail] = tail;
  23.             ++tail;
  24.         }
  25.         if (c == 'Q') {
  26.             int p = lower_bound(P, P + tail, tail - x) - P;
  27.             t = Q[p];
  28.             cout << Q[p] << endl;
  29.         }
  30.     }
  31.     return 0;
  32. }
  33. /*
  34. 8 10000
  35. A 101
  36. A 200
  37. Q 1
  38. Q 2
  39. A 10
  40. Q 1
  41. Q 2
  42. Q 3
  43. */
复制代码
回复 支持 反对

使用道具 举报

smileandyxu

1

主题

49

帖子

277

积分

中级会员

Rank: 3Rank: 3

积分
277
59#
 楼主| 发表于 2016-6-15 17:08:12 | 只看该作者
  1. #include <iostream>
  2. #define INF 0x3fffffff
  3. using namespace std;
  4. inline int abs(int x)
  5. {
  6.     return (x > 0 ? x : -x);
  7. }
  8. struct node {
  9.     node* ch[2];
  10.     int v;
  11.     int s;
  12. };
  13. node* null = new node();
  14. node* newnode(int x)
  15. {
  16.     node* tmp = new node();
  17.     tmp->ch[0] = null;
  18.     tmp->ch[1] = null;
  19.     tmp->v = x;
  20.     tmp->s = 1;
  21.     return tmp;
  22. }
  23. node* prec(node* o, node* p, int v)
  24. {
  25.     if (o == null)
  26.         return p;
  27.     else if (v < o->v)
  28.         return prec(o->ch[0], p, v);
  29.     return prec(o->ch[1], o, v);
  30. }
  31. node* succ(node* o, node* p, int v)
  32. {
  33.     if (o == null)
  34.         return p;
  35.     else if (v > o->v)
  36.         return prec(o->ch[1], p, v);
  37.     return prec(o->ch[0], o, v);
  38. }
  39. void rotate(node* &o, int d)
  40. {
  41.     node* k = o->ch[d ^ 1];
  42.     o->ch[d ^ 1] = k->ch[d];
  43.     k->ch[d] = o;
  44.     k->s = o->s;
  45.     o->s = o->ch[0]->s + o->ch[1]->s + 1;
  46.     o = k;
  47. }
  48. void maintain(node* &o, bool d)
  49. {
  50.     if (!d) {
  51.         if (o->ch[0]->ch[0]->s > o->ch[1]->s)
  52.             rotate(o, 1);
  53.         else if (o->ch[0]->ch[1]->s > o->ch[1]->s) {
  54.             rotate(o->ch[0], 0);
  55.             rotate(o, 1);
  56.         }
  57.         else
  58.             return;
  59.     }
  60.     else {
  61.         if (o->ch[1]->ch[1]->s > o->ch[0]->s)
  62.             rotate(o, 0);
  63.         else if (o->ch[1]->ch[0]->s > o->ch[0]->s) {
  64.             rotate(o->ch[1], 1);
  65.             rotate(o, 0);
  66.         }
  67.         else
  68.             return;
  69.     }
  70.     maintain(o->ch[0], false);
  71.     maintain(o->ch[1], true);
  72.     maintain(o, false);
  73.     maintain(o, true);
  74. }
  75. void insert(node* &o, int v)
  76. {
  77.     if (o == null)
  78.         o = newnode(v);
  79.     else {
  80.         ++o->s;
  81.         insert(o->ch[v >= o->v], v);
  82.         maintain(o, false);
  83.         maintain(o, true);
  84.     }
  85. }
  86. void print(node* o)
  87. {
  88.     if (o != null) {
  89.         print(o->ch[0]);
  90.         cout << o->v << " ";
  91.         print(o->ch[1]);
  92.     }
  93. }
  94. node* T;
  95. int n, ans;
  96. int main()
  97. {
  98.     null->ch[0] = null;
  99.     null->ch[1] = null;
  100.     T = null;
  101.     cin >> n;
  102.     for (int i = 0, x; i != n; ++i) {
  103.         cin >> x;
  104.         node* p = prec(T, null, x);
  105.         node* q = succ(T, null, x);
  106.         int t = ans;
  107.         if (p == null)
  108.             ans += q->v - x;
  109.         else if (q == null)
  110.             ans += x - p->v;
  111.         else
  112.             ans += min(q->v - x, x - p->v);
  113.         cout <<"==>" <<  ans - t << endl;
  114.         insert(T, x);
  115.     }
  116.     cout << ans;
  117.     return 0;
  118. }
复制代码
回复 支持 反对

使用道具 举报

smileandyxu

1

主题

49

帖子

277

积分

中级会员

Rank: 3Rank: 3

积分
277
60#
 楼主| 发表于 2016-8-19 16:24:28 | 只看该作者
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <cctype>
  5. #define INF 0x7fffffff
  6. using namespace std;
  7. inline int getint()
  8. {
  9.     char c = getchar();
  10.     while (!isdigit(c))
  11.         c = getchar();
  12.     int x = 0;
  13.     while (isdigit(c)) {
  14.         x = x * 10 + c - '0';
  15.         c = getchar();
  16.     }
  17.     return x;
  18. }
  19. int END[4000001], FLOW[4000001], NEXT[4000001];
  20. int DIS[1000001], GAP[1000001], HEAD[1000001];
  21. int S, T;
  22. int n, m, eid;
  23. void addedge(int u, int v, int w)
  24. {
  25.     END[eid] = v, FLOW[eid] = w, NEXT[eid] = HEAD[u], HEAD[u] = eid++;
  26.     END[eid] = u, FLOW[eid] = 0, NEXT[eid] = HEAD[v], HEAD[v] = eid++;
  27. }
  28. void init()
  29. {
  30.     n = getint();
  31.     m = getint();
  32.     for (int i = 1; i <= m * n; ++i)
  33.         HEAD[i] = -1;
  34.     for (int i = 1; i <= n; ++i) {
  35.         for (int j = 1, w; j <= m - 1; ++j) {
  36.             w = getint();
  37.             addedge((i - 1) * m + j, (i - 1) * m + j + 1, w);
  38.         }
  39.     }
  40.     for (int i = 1; i <= n - 1; ++i) {
  41.         for (int j = 1, w; j <= m; ++j) {
  42.             w = getint();
  43.             addedge((i - 1) * m + j, i * m + j, w);
  44.         }
  45.     }
  46.     for (int i = 1; i <= n - 1; ++i) {
  47.         for (int j = 1, w; j <= m - 1; ++j) {
  48.             w = getint();
  49.             addedge((i - 1) * m + j, i * m + j + 1, w);
  50.         }
  51.     }
  52. }
  53. int augment(int pos, int flow)
  54. {
  55.     if (pos == m * n)
  56.         return flow;
  57.     else {
  58.         int cur, aug;
  59.         cur = 0;
  60.         for (int i = HEAD[pos]; i != -1; i = NEXT[i]) {
  61.             int j = END[i];
  62.             if (FLOW[i] && DIS[pos] == DIS[j] + 1) {
  63.                 aug = augment(j, min(flow - cur, FLOW[i]));
  64.                 FLOW[i] -= aug;
  65.                 FLOW[i ^ 1] += aug;
  66.                 cur += aug;
  67.                 if (cur == flow || DIS[S] >= m * n)
  68.                     return cur;
  69.             }
  70.         }
  71.         if (!cur) {
  72.             if (--GAP[DIS[pos]] == 0) {
  73.                 DIS[S] = m * n;
  74.                 return cur;
  75.             }
  76.             int mindis = m * n;
  77.             for (int i = HEAD[pos]; i != -1; i = NEXT[i])
  78.                 if (FLOW[i])
  79.                     mindis = min(mindis, DIS[END[i]] + 1);
  80.             DIS[pos] = mindis;
  81.             ++GAP[DIS[pos]];
  82.         }
  83.         return cur;
  84.     }
  85. }
  86. int isap()
  87. {
  88.     int max_flow = 0;
  89.     S = 1;
  90.     T = m * n;
  91.     GAP[0] = m * n; //***//
  92.     while (DIS[S] < m * n)
  93.         max_flow += augment(S, INF);
  94.     return max_flow;
  95. }
  96. int main()
  97. {
  98.     init();
  99.     if (m == 1 && n == 1)
  100.         printf("%d", 0);
  101.     else
  102.         printf("%d", isap());
  103.     return 0;
  104. }
复制代码
回复 支持 反对

使用道具 举报

123456
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持：DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 13:50 , Processed in 0.126099 second(s), 20 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表