danihao123's Blog

[BZOJ 1061][NOI2008]志愿者招募

膜了一发BYVoid的题解……竟然搞懂了

这首先是个非常简单的线性规划，就是有若干限制（每天要求的志愿者），形如：

$P_i = X_a + X_b +\ldots + X_c\geq A_i$

（这里用 $X_i$ 表示第 $i$ 类志愿者雇佣了多少个， $P_i$ 表示第 $i$ 天的志愿者总数， $A_i$ 同原题面）

且最小化总费用。

既然我们我知道 $P_i\geq A_i$ ，那么说明 $P_i$ 一定可以表示为 $A_i + Y_i$ （ $Y_i\geq 0$ ）。然后这样限制就变成了：

$P_i = X_a + X_b +\ldots + X_c + Y_i = A_i$

这个长得很像可以流量平衡的样子，但是流量的变动是表示不了的……

然后假设 $P_0 = 0$ 且 $P_{n + 1} = 0$ ，这样就可以对限制差分一下，我们就有了 $n + 1$ 个限制，然后这个式子就可以流量平衡做了（因为不考虑常数项的话，同一变量只可能在两个限制中出现，并且一正一负，这样就可以通过一个限制送给另一个限制流量来表示了。至于常数项，通过源或者汇连边即可表达）。

然后由于志愿者无限，所以这个东西也一定有解……

我局的我这么渣各位看官看懂的可能性基本上是零……还是推荐BYVoid神犇的题解，比我透彻多了。

代码：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

/**************************************************************
    Problem: 1061
    User: danihao123
    Language: C++
    Result: Accepted
    Time:3164 ms
    Memory:6824 kb
****************************************************************/
  
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <utility>
#include <algorithm>
#include <queue>
#include <cassert>
typedef long long ll;
int m, n;
const int maxno = 100005;
const int maxe = 100005;
int first[maxno];
int next[maxe], from[maxe], to[maxe]; ll flow[maxe], cap[maxe];
ll cost[maxe];
int gcnt = 0;
void add_edge(int u, int v, ll f, ll c) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  from[gcnt] = u; to[gcnt] = v;
  cap[gcnt] = f; flow[gcnt] = 0;
  cost[gcnt] = c;
}
int rev(int i) {
  return ((i - 1) ^ 1) + 1;
}
int ins_edge(int u, int v, ll f, ll c = 0LL) {
#ifdef LOCAL
  printf("Inserting Edge (%d, %d, %lld, %lld)\n", u, v, f, c);
#endif
  add_edge(u, v, f, c);
  add_edge(v, u, 0, -c);
  return gcnt - 1;
}
  
const ll LINF = 0x7f7f7f7f7f7f7f7fLL;
int tot;
bool spfa(int s, int t, ll &f, ll &c) {
  static ll d[maxno];
  static bool inq[maxno];
  static ll a[maxno]; static int p[maxno];
  std::fill(d, d + tot + 1, LINF);
  std::fill(inq, inq + tot + 1, false);
  std::fill(a, a + tot + 1, 0LL);
  std::fill(p, p + tot + 1, 0);
  d[s] = 0;
  std::queue<int> Q; Q.push(s); inq[s] = true;
  a[s] = LINF;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    inq[u] = false;
    for(int i = first[u]; i; i = next[i]) {
      if(cap[i] > flow[i]) {
        int v = to[i];
        if(d[v] > d[u] + cost[i]) {
          d[v] = d[u] + cost[i];
          a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i;
          if(!inq[v]) {
            Q.push(v); inq[v] = true;
          }
        }
      }
    }
  }
  if(a[t] == 0LL) return false;
  f += a[t];
  c += a[t] * d[t];
  for(int e = p[t]; e; e = p[from[e]]) {
    flow[e] += a[t];
    flow[rev(e)] -= a[t];
  }
  return true;
}
void mcmf(int s, int t, ll &f, ll &c) {
  while(spfa(s, t, f, c));
}
  
const int maxn = 1005, maxm = 10005;
int E[maxn];
int A[maxn], D[maxn];
int main() {
  scanf("%d%d", &n, &m);
  int s = 0, t = n + 2; tot = n + 2;
  for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
  for(int i = 1; i <= n + 1; i ++) {
    D[i] = A[i] - A[i - 1];
    if(D[i] >= 0) {
      E[i] = ins_edge(s, i, D[i]);
    } else {
      E[i] = ins_edge(i, t, -D[i]);
    }
  }
  for(int i = 1; i <= n; i ++) {
    ins_edge(i + 1, i, LINF);
  }
  while(m --) {
    int S, T, C; scanf("%d%d%d", &S, &T, &C);
    ins_edge(S, T + 1, LINF, C);
  }
  ll f = 0, c = 0; mcmf(s, t, f, c);
  printf("%lld\n", c);
  return 0;
}

[BZOJ 3171][TJOI2013]循环格

流量平衡入门中……

我竟然想民白了……

这个题就是要求每个点在且仅在一个环中，这样每个点的入、出度都是1。出度肯定是1，接下来我们想想怎么保证入度为1。

我们建两排点（也可以说是拆点？），一排表示流出，一排表示接受。然后流出点向相邻的接收点连边，费用的话考虑是否和原来这一格的方向不一样就行了。

这个不需要判断是否满流啥的……因为一定有解（比如说每个行构成一个环啥的）。

代码：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

/**************************************************************
  Problem: 3171
  User: danihao123
  Language: C++
  Result: Accepted
  Time:28 ms
  Memory:13844 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
const int maxn = 20;
typedef long long ll;
char S[maxn][maxn];
int tot = 0; int num[maxn][maxn][2];
int R, C;
char D[4] = {'L', 'R', 'U', 'D'};
int tow(int i, int j, char dir, int flag) {
  int dx = 0, dy = 0;
  if(dir == 'L') {
    dx = -1;
  } else if(dir == 'R') {
    dx = 1;
  } else if(dir == 'U') {
    dy = -1;
  } else if(dir == 'D') {
    dy = 1;
  }
  int nx = (i + dy + R) % R;
  int ny = (j + dx + C) % C;
  return num[nx][ny][flag];
}
const int maxno = 100005;
const int maxe = 400005;
int first[maxno];
int next[maxe], from[maxe], to[maxe], flow[maxe], cap[maxe];
ll cost[maxe];
int gcnt = 0;
void add_edge(int u, int v, int f, ll c) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  from[gcnt] = u; to[gcnt] = v;
  cap[gcnt] = f; flow[gcnt] = 0;
  cost[gcnt] = c;
}
int rev(int i) {
  return ((i - 1) ^ 1) + 1;
}
void ins_edge(int u, int v, int f, ll c = 0LL) {
#ifdef LOCAL
  printf("Inserting Edge (%d, %d, %d, %lld)\n", u, v, f, c);
#endif
  add_edge(u, v, f, c);
  add_edge(v, u, 0, -c);
}
 
const ll LINF = 0x7f7f7f7f7f7f7f7fLL;
bool spfa(int s, int t, int &f, ll &c) {
  static ll d[maxno];
  static bool inq[maxno];
  static int a[maxno], p[maxno];
  std::fill(d, d + tot + 1, LINF);
  std::fill(inq, inq + tot + 1, false);
  std::fill(a, a + tot + 1, 0);
  std::fill(p, p + tot + 1, 0);
  d[s] = 0;
  std::queue<int> Q; Q.push(s); inq[s] = true;
  a[s] = 0x7fffffff;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    inq[u] = false;
    for(int i = first[u]; i; i = next[i]) {
      if(cap[i] > flow[i]) {
        int v = to[i];
        if(d[v] > d[u] + cost[i]) {
          d[v] = d[u] + cost[i];
          a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i;
          if(!inq[v]) {
            Q.push(v); inq[v] = true;
          }
        }
      }
    }
  }
  if(a[t] == 0) return false;
  f += a[t];
  c += (ll(a[t])) * d[t];
  for(int e = p[t]; e; e = p[from[e]]) {
    flow[e] += a[t];
    flow[rev(e)] -= a[t];
  }
  return true;
}
void mcmf(int s, int t, int &f, ll &c) {
  while(spfa(s, t, f, c));
}
 
int main() {
  tot = 1; int s = 0, t = 1;
  scanf("%d%d", &R, &C);
  for(int i = 0; i < R; i ++) {
    scanf("%s", S[i]);
    for(int j = 0; j < C; j ++) {
      num[i][j][0] = ++ tot;
      num[i][j][1] = ++ tot;
    }
  }
  for(int i = 0; i < R; i ++) {
    for(int j = 0; j < C; j ++) {
      ins_edge(s, num[i][j][0], 1);
      ins_edge(num[i][j][1], t, 1);
      for(int it = 0; it < 4; it ++) {
        int u = num[i][j][0];
        int v = tow(i, j, D[it], 1);
        ins_edge(u, v, 1, (D[it] == S[i][j]) ? 0LL : 1LL);
      }
    }
  }
  int f = 0; ll c = 0;
  mcmf(s, t, f, c);
  printf("%lld\n", c);
  return 0;
}

[BZOJ 1061][NOI2008]志愿者招募

[BZOJ 3171][TJOI2013]循环格

danihao123

搜索

分类

标签云

最新评论

最新留言

神犇的Blog

RSS

功能

计数器