[BZOJ 5091][Lydsy0711月赛]摘苹果

秒,秒啊.jpg

首先根据期望线性性,每个点的期望可以分开算。不妨设\(f_{i, j}\)表示\(j\)在某个第\(i\)步被走到的概率。那么每个点\(j\)的期望访问次数就是\(\sum_{i = 0}^k f_{i, j}\)。

然后考虑去求那个\(f_{i, j}\)。显然\(f_{0, j} = \frac{d_j}{2m}\)。但是考虑\(f_{1, j}\)的转移方程:

\[f_{1, j} = \sum \frac{f_{0, u}}{d_u}\]

然后展开之后发现每个\(\frac{f_{0, u}}{d_u}\)都是\(\frac{1}{2m}\),于是乎\(f_{1, j} = \frac{d_j}{2m}\)。

如此一来,对于任意\(i\),都有\(d_{i, j} = \frac{d_j}{2m}\),然后就很好做了……

代码:

/**************************************************************
    Problem: 5091
    User: danihao123
    Language: C++
    Result: Accepted
    Time:532 ms
    Memory:2384 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const ll ha = 1000000007LL;
ll pow_mod(ll a, ll b) {
  if(!b) return 1LL;
  ll ans = pow_mod(a, b >> 1);
  ans = (ans * ans) % ha;
  if(1LL & b) ans = (ans * a) % ha;
  return ans;
}
ll inv(ll v) {
  return pow_mod(v, ha - 2LL);
}
 
const int maxn = 100005;
ll a[maxn], d[maxn];
int main() {
  int n, m, k; scanf("%d%d%d", &n, &m, &k);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &a[i]);
  }
  for(int i = 1; i <= m; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    d[u] ++; d[v] ++;
  }
  ll ans = 0;
  ll inv_2m = inv(2 * m);
  for(int i = 1; i <= n; i ++) {
    ans += (((d[i] * inv_2m) % ha) * a[i]) % ha;
    if(ans >= ha) ans -= ha;
  }
  ans = (ans * (ll(k))) % ha;
  printf("%lld\n", ans);
  return 0;
}

[BZOJ 3156]防御准备

又做了一个简单的斜率优化题TAT

首先,设\(f_i\)表示最后一个放塔的点事\(i\)时的最优解,那么将原方程化简得:

\[f_i = a_i + \frac{i^2 - i}{2} + max(-ij + \frac{j^2 + j}{2} + f_j)\]

然后求直线形式,得到:

\[ij + d_i = f_j + \frac{j^2 + j}{2}\]

用类似于玩具装箱(上一篇题解)的方式搞一搞即可。

代码:

/**************************************************************
	Problem: 3156
	User: danihao123
	Language: C++
	Result: Accepted
	Time:2496 ms
	Memory:16480 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <deque>
#include <cmath>
#include <climits>
typedef long long ll;
typedef ll T;
struct Point {
  T x, y;
  Point(T qx = 0LL, T qy = 0LL) {
    x = qx; y = qy;
  }
};
typedef Point Vector;
Vector operator +(const Vector &a, const Vector &b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
  return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
  return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
  return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
  return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
  return (a.x * b.y - a.y * b.x);
}

const int maxn = 1000005;
T f[maxn], a[maxn];
int n;
void dp() {
  f[1] = a[1];
  std::deque<Point> Q;
  Q.push_back(Point(1LL, f[1] + 1LL));
  for(T i = 2; i <= n; i ++) {
    T k = i;
    Vector st(1LL, k);
    while(Q.size() > 1 && times(Q[1] - Q[0], st) > 0LL) {
      Q.pop_front();
    }
    f[i] = a[i] + ((i * i - i) / 2LL);
    f[i] += Q.front().y - Q.front().x * i;
    Point ins(i, f[i] + ((i * i + i) / 2LL));
    while(Q.size() > 1 && times(ins - Q.back(), Q.back() - Q[Q.size() - 2]) > 0LL) {
      Q.pop_back();
    }
    Q.push_back(ins);
  }
}

int main() {
  scanf("%d", &n);
  for(int i = n; i >= 1; i --) {
    scanf("%lld", &a[i]);
  }
  dp();
  ll ans = f[n];
#ifdef LOCAL
  printf("f[n] : %lld\n", ans);
#endif
  for(T i = 1; i < n; i ++) {
#ifdef LOCAL
    printf("f[%d] : %lld\n", i, f[i]);
#endif
    ans = std::min(ans, f[i] + (n - i + 1LL) * (n - i) / 2LL);
  }
  printf("%lld\n", ans);
  return 0;
}

[BZOJ 1010][HNOI2008]玩具装箱toy

很久之前是学过并写过斜率优化的……但是很快就忘了。现在感觉自己理解了,感觉是真的懂了……抽空写篇文章解释一下吧……

先单独说这一个题。将DP方程完全展开,并且设\(P_i = S_i + i\),\(c = L + 1\),可得:

\[f_i = c^2 + P_i^2 - 2P_i c + max(P_j^2 + 2P_j c + f_j - 2P_i P_j)\]

然后\(c^2 + P_i^2 - 2P_i c\)这部分是常数项不需要管了,我们就想想max里面那些(姑且设之为\(d_i\))咋整好了。

设\(d_i = P_j^2 + 2P_j c + f_j - 2P_i P_j\),稍作移项,得:

\[2P_i P_j + d_i = P_j^2 + 2P_j c + f_j\]

于是乎,\(d_i\)可以看做斜率为\(2P_i\)的直线过点\((P_j, P_j^2 + 2P_j c + f_j)\)得到的截距。而那些点我们之前都知道了,问题就变成了已知斜率,求过某点集中的点的最大截距。

想象一个固定斜率的直线从下往上扫,那么碰到的第一个点就是最优解。首先这个点一定在下凸壳上,其次下凸壳上这点两侧的线段的斜率肯定一个比\(2P_i\)大另一个比它小。并且最好的一点是这个斜率还是单调的,那么分界点一定是单调递增的。

代码:

/**************************************************************
    Problem: 1010
    User: danihao123
    Language: C++
    Result: Accepted
    Time:132 ms
    Memory:2416 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <deque>
#include <cmath>
typedef long long ll;
typedef ll T;
struct Point {
  T x, y;
  Point(T qx = 0LL, T qy = 0LL) {
    x = qx; y = qy;
  }
};
typedef Point Vector;
Vector operator +(const Vector &a, const Vector &b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
  return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
  return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
  return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
  return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
  return (a.x * b.y - a.y * b.x);
}
 
const int maxn = 50005;
T C[maxn], S[maxn], P[maxn];
T f[maxn];
int n; ll c;
void process() {
  for(int i = 1; i <= n; i ++) {
    S[i] = S[i - 1] + C[i];
    P[i] = S[i] + (ll(i));
  }
}
void dp() {
  std::deque<Point> Q;
  Q.push_back(Point(0LL, 0LL));
  for(int i = 1; i <= n; i ++) {
    ll k = 2 * P[i];
    Vector st(1, k);
    while(Q.size() > 1 && times(Q[1] - Q[0], st) > 0LL) {
      Q.pop_front();
    }
    f[i] = c * c + P[i] * P[i] - 2LL * P[i] * c;
    f[i] += Q.front().y - k * Q.front().x;
#ifdef LOCAL
    printf("f[%d] : %lld\n", i, f[i]);
#endif
    Vector ins(P[i], f[i] + P[i] * P[i] + 2LL * P[i] * c);
    while(Q.size() > 1 && times(ins - Q.back(), Q.back() - Q[Q.size() - 2]) > 0LL) {
#ifdef LOCAL
      printf("Deleting (%lld, %lld)...\n", Q.back().x, Q.back().y);
#endif
      Q.pop_back();
    }
    Q.push_back(ins);
#ifdef LOCAL
    printf("Inserting (%lld, %lld)...\n", ins.x, ins.y);
#endif
  }
}
 
int main() {
  scanf("%d%lld", &n, &c); c ++;
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &C[i]);
  }
  process(); dp();
  printf("%lld\n", f[n]);
  return 0;
}

[BZOJ 2561]最小生成树

窝只会做水体了qwq

因为这条边既存在在最大生成树里,又存在在最小生成树里。那就说明\(u\)到\(v\)的路径上,在最大生成树上这条边是最小的,在最小生成树上这条边是最大的。

所以说我们不能用大于\(L\)的边来联通\(u\)和\(v\),也不能用小于\(L\)的边,于是乎……跑两次最小割即可。

代码:

/**************************************************************
	Problem: 2561
	User: danihao123
	Language: C++
	Result: Accepted
	Time:1528 ms
	Memory:15952 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <algorithm>
#include <queue>
const int maxn = 20005;
const int maxm = 200005;
const int maxe = maxm << 2;
int n, m;
int first[maxn];
int next[maxe], to[maxe], flow[maxe], cap[maxe];
int gcnt = 0;
inline void init_graph() {
  gcnt = 0;
  std::fill(first + 1, first + 1 + n, 0);
}
inline void add_edge(int u, int v, int f) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  to[gcnt] = v;
  flow[gcnt] = 0; cap[gcnt] = f;
}
inline int rev(int i) {
  return (((i - 1) ^ 1) + 1);
}
inline void ins_edge(int u, int v, int f) {
  add_edge(u, v, f);
  add_edge(v, u, 0);
}

int line[maxm][3];
int d[maxn];
int s, t;
inline bool bfs() {
  static bool vis[maxn];
  std::fill(vis + 1, vis + 1 + n, false);
  std::fill(d + 1, d + 1 + n, 0);
  std::queue<int> Q;
  Q.push(s); vis[s] = true; d[s] = 1;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(!vis[v] && cap[i] > flow[i]) {
        d[v] = d[u] + 1; vis[v] = true;
        Q.push(v);
      }
    }
  }
  return vis[t];
}
int cur[maxn];
int dfs(int x, int a) {
  if(a == 0 || x == t) return a;
  int ans = 0;
  for(int &i = cur[x]; i; i = next[i]) {
    int v = to[i];
    int f;
    if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
      ans += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[x] = -1;
  return ans;
}
int dinic() {
  int ans = 0;
  while(bfs()) {
    for(int i = 1; i <= n; i ++) cur[i] = first[i];
    ans += dfs(s, 0x7fffffff);
  }
  return ans;
}

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int *l = line[i];
    scanf("%d%d%d", &l[0], &l[1], &l[2]);
  }
  int L; scanf("%d%d%d", &s, &t, &L);
  for(int i = 1; i <= m; i ++) {
    int *l = line[i];
    if(l[2] < L) {
      ins_edge(l[0], l[1], 1);
      ins_edge(l[1], l[0], 1);
    }
  }
  int ans = dinic();
  init_graph();
  for(int i = 1; i <= m; i ++) {
    int *l = line[i];
    if(l[2] > L) {
      ins_edge(l[0], l[1], 1);
      ins_edge(l[1], l[0], 1);
    }
  }
  ans += dinic();
  printf("%d\n", ans);
  return 0;
}

[BZOJ 3158]千钧一发

好有意思的题呢qwq

首先观察到一点,我们可以把所有装置按照\(a_i\)的奇偶性进行分类(也可以说是黑白染色?)。容易发现任意偶数的最大公约数都至少是2,所以任意偶数间不会互相冲突。然后任意两个奇数的平方和一定不是完全平方数,可以这么证一下(感谢金爷!):

那两个奇数可以分别设成\(2x + 1\)和\(2y + 1\),然后他们的平方和就是\(4(x^2 + y^2 + x + y) + 2\)。然后思考一点,就是一个奇数的平方一定是奇数,所以说那个平方和是一个偶数。但是,如果一个完全平方数是偶数,那么它的算术平方根一定是偶数。然而,一个偶数的平方一定是4的倍数。但我们求出的平方和膜4得2,所以不行。

所以说冲突只存在于奇偶性不同的数中。然后用无限大的边来表示冲突关系,最小割高一波即可。

代码(常数卡卡卡……只能用pb_ds的蛤希表了):

/**************************************************************
	Problem: 3158
	User: danihao123
	Language: C++
	Result: Accepted
	Time:9676 ms
	Memory:130460 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
typedef long long ll;
ll gcd(ll a, ll b) {
  if(!b) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}
__gnu_pbds::gp_hash_table<ll, bool> S2;
void process_S2() {
  for(ll i = 1LL; i * i <= 2000000000000LL; i ++) {
    S2[i * i] = true;
  }
}


const int maxno = 1050;
const int maxm = 2000500;
int first[maxno];
int next[maxm], to[maxm], cap[maxm], flow[maxm];
int gcnt = 0;
void add_edge(int u, int v, int f) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  to[gcnt] = v;
  cap[gcnt] = f;
  flow[gcnt] = 0;
}
int rev(int i) {
  if(1 & i) {
    return i + 1;
  } else {
    return i - 1;
  }
}
void ins_edge(int u, int v, int f) {
  add_edge(u, v, f); add_edge(v, u, 0);
}

int n;
int s, t;
int d[maxno];
bool bfs() {
  static bool vis[maxno];
  memset(vis, 0, sizeof(vis));
  d[s] = 1; vis[s] = true;
  std::queue<int> Q; Q.push(s);
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(cap[i] > flow[i] && !vis[v]) {
        d[v] = d[u] + 1; vis[v] = true;
        Q.push(v);
      }
    }
  }
  return vis[t];
}
int cur[maxno];
int dfs(int u, int a) {
  if(a == 0 || u == t) return a;
  int fl = 0;
  for(int &i = cur[u]; i; i = next[i]) {
    int v = to[i]; int f;
    if(d[v] == d[u] + 1 && (f = dfs(v, std::min(cap[i] - flow[i], a))) > 0) {
      fl += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[u] = -1;
  return fl;
}
int tot;
int dinic() {
  int ans = 0;
  while(bfs()) {
    for(int i = 0; i <= tot; i ++) cur[i] = first[i];
    ans += dfs(s, 0x7fffffff);
  }
  return ans;
}

const int maxn = 1005;
ll A[maxn]; int B[maxn];
int main() {
  process_S2();
  scanf("%d", &n); tot = n + 1;
  s = 0, t = tot;
  std::vector<int> odd, even;
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &A[i]);
    if(1LL & A[i]) {
      odd.push_back(i);
    } else {
      even.push_back(i);
    }
  }
  int ans = 0;
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &B[i]); ans += B[i];
    if(1LL & A[i]) {
      ins_edge(i, t, B[i]);
    } else {
      ins_edge(s, i, B[i]);
    }
  }
  for(int i = 0; i < even.size(); i ++) {
    int p1 = even[i];
    for(int j = 0; j < odd.size(); j ++) {
      int p2 = odd[j];
      if(gcd(A[p1], A[p2]) == 1LL && S2.find(A[p1] * A[p1] + A[p2] * A[p2]) != S2.end()) {
        ins_edge(p1, p2, 0x7f7f7f7f);
      }
    }
  }
  ans -= dinic();
  printf("%d\n", ans);
  return 0;
}

[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神犇的题解,比我透彻多了。

代码:

/**************************************************************
    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。

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

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

代码:

/**************************************************************
	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 1070][SCOI2007]修车

啊啊啊我为什么要去颓费用流啊……

这个题可以保证每个人的车最后都会被修,所以说也就是让你最小化总等待时间辣!

直接考虑给一个技术人员建时间轴是麻烦而不可取的。我们考虑一点,对于每一个技术人员,若总共修了\(t\)辆车,那么第\(i\)个来找他修车的人会影响后面人的等待时间,换言之我们可以认为第\(i\)个来修车的人给答案做出了\(c\cdot (t - i + 1)\)(这里用\(c\)表示他自己的修车时间,注意他也会影响他自己)的贡献,似乎可以苟最小费用最大流呢。

但问题在于我们并不能提前知道\(t\)是多少,并且这样的话费用不是递增的,一个人可能会优先考虑到后面的位置去修车。那么我们考虑倒过来,去考虑倒数第\(i\)个来修车的人的贡献,显然这个贡献是\(c\cdot i\)。然后接下来就肥肠简单了,,,

代码:

/**************************************************************
	Problem: 1070
	User: danihao123
	Language: C++
	Result: Accepted
	Time:576 ms
	Memory:13928 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 = 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;
int tot;
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 pos[105][105][2];
int main() {
  scanf("%d%d", &m, &n);
  int s = 0, t = 1; tot = 1;
  for(int i = 1; i <= n; i ++) {
    ins_edge(s, ++ tot, 1);
  }
  for(int i = 1; i <= m; i ++) {
    for(int j = 1; j <= n; j ++) {
      pos[i][j][0] = ++ tot;
      pos[i][j][1] = ++ tot;
      ins_edge(tot - 1, tot, 1);
      ins_edge(tot, t, 1);
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= m; j ++) {
      int T; scanf("%d", &T);
      for(int k = 1; k <= n; k ++) {
        int id = pos[j][k][0]; int id2 = pos[j][k][1];
        ins_edge(i + 1, id, 1, k * T);
      }
    }
  }
  int f = 0; ll c = 0;
  mcmf(s, t, f, c);
#ifdef LOCAL
  printf("%d\n", f);
#endif
  printf("%.2lf\n", (double(c)) / (double(n)));
  return 0;
}

[BZOJ 1449][JSOI2009]球队收益

二次函数费用流的入门题……我真太弱了……

可以给比赛、队伍都建点,然后\(S\)向每个比赛连容量为1的边,每个比赛向队伍连容量为\(1\)的边,来表示赢家是谁。这样一来一次比赛只有一个队伍赢了。

考虑怎么处理那个二次函数费用。费用函数为\(f(x, y) = C x^2 + D y^2\),由于一个队伍的总比赛次数是已知的,所以\(y\)不需要,不妨假设一个队伍有\(t\)场比赛,则费用函数为\(f(x) = C x^2 + D(t - x)^2\)。

对这个函数做差分:\(\Delta f(x) = f(x + 1) - f(x) = 2Cx - 2D(t - x) + C + D\),然后这个差分是单调不降的。因此我们对所有差分都从队伍向\(T\)连边(费用为这一点的差分),这样一来的话会优先选择费用小的边,保证这个队伍的费用一直合法。

代码:

/**************************************************************
	Problem: 1449
	User: danihao123
	Language: C++
	Result: Accepted
	Time:732 ms
	Memory:1448 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <cassert>
typedef long long ll;
const int maxn = 5005;
const int maxm = 1005;
const int maxno = maxn + maxm + 5;
const int maxe = (1000 * 2 + 1000 * 3) * 2 + 50;
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) {
  add_edge(u, v, f, c);
  add_edge(v, u, 0, -c);
}

int n, m;
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 + n + m + 2, LINF);
  std::fill(inq, inq + n + m + 2, false);
  std::fill(a, a + n + m + 2, 0);
  std::fill(p, p + n + m + 2, 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));
}

ll win[maxn], lose[maxn], C[maxn], D[maxn];
ll tot[maxn];
int main() {
  scanf("%d%d", &n, &m);
  ll ans = 0;
  for(int i = 1; i <= n; i ++) {
    scanf("%lld%lld%lld%lld", &win[i], &lose[i], &C[i], &D[i]);
    tot[i] = win[i] + lose[i];
  }
  int s = 0, t = n + m + 1;
  for(int i = 1; i <= m; i ++) {
    int a, b; scanf("%d%d", &a, &b);
    ins_edge(0, i + n, 1, 0);
    ins_edge(i + n, a, 1, 0);
    ins_edge(i + n, b, 1, 0);
    tot[a] ++; tot[b] ++;
  }
  for(int i = 1; i <= n; i ++) {
    ans += C[i] * win[i] * win[i] + D[i] * (tot[i] - win[i]) * (tot[i] - win[i]);
    for(ll j = win[i]; j <= (tot[i] - lose[i] - 1LL); j ++) {
      ins_edge(i, t, 1, 2LL * C[i] * j - 2LL * D[i] * (tot[i] - j) + C[i] + D[i]);
    }
  }
  int f = 0; mcmf(s, t, f, ans);
  printf("%lld\n", ans);
  return 0;
}

[BZOJ 1857][SCOI2010]传送带

三分套三分入门题……

策略肯定是从A走到AB上一点,然后再走到CD上的一个点,再向D走。

很显然答案函数是一个关于那两个点下凸的东西(不会证?GeoGebra之类的东西画一下就好啦!还不如像我这样口胡),所以我们可以先对第一维三分,然后套上对第二维的三分……

代码:

/**************************************************************
	Problem: 1857
	User: danihao123
	Language: C++
	Result: Accepted
	Time:244 ms
	Memory:820 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <cmath>
typedef double R;
const R eps = 1e-6;
int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    if(x < 0) return -1;
    else return 1;
  }
}
struct Point {
  R x, y;
  Point(R qx = 0, R qy = 0) {
    x = qx; y = qy;
  }
};
typedef Point Vector;
Vector operator +(const Vector &a, const Vector &b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
  return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(R x, const Vector &v) {
  return Point(v.x * x, v.y * x);
}
Vector operator *(const Vector &v, R x) {
  return Point(v.x * x, v.y * x);
}
R dot(const Vector &a, const Vector &b) {
  return a.x * b.x + a.y * b.y;
}
R times(const Vector &a, const Vector &b) {
  return a.x * b.y - a.y * b.x;
}
R dist(const Point &a, const Point &b) {
  return sqrt(dot(a - b, a - b));
}
bool cmp(const Point &a, const Point &b) {
  if(sign(a.x - b.x) == 0) {
    return a.y < b.y;
  } else {
    return a.x < b.x;
  }
}
Point A, B, C, D;
R p, q, r;
Vector D_AB, D_DC;
R f(const Point &AB, const Point &CD) {
  return (dist(AB, A) / p + dist(CD, D) / q + dist(AB, CD) / r);
}
R F(Point AB) {
  R L = 0, R = 1;
  int T = 200;
  while(T --) {
    double M1 = L + (R - L) / 3;
    double M2 = R - (R - L) / 3;
    Point P1 = D + M1 * D_DC;
    Point P2 = D + M2 * D_DC;
    double f1 = f(AB, P1), f2 = f(AB, P2);
    if(f1 < f2) {
      R = M2;
    } else {
      L = M1;
    }
  }
  return f(AB, D + L * D_DC);
}
R solve() {
  R L = 0, R = 1;
  int T = 200;
  while(T --) {
    double M1 = L + (R - L) / 3;
    double M2 = R - (R - L) / 3;
    Point P1 = A + M1 * D_AB;
    Point P2 = A + M2 * D_AB;
    double F1 = F(P1), F2 = F(P2);
    if(F1 < F2) {
      R = M2;
    } else {
      L = M1;
    }
  }
  return F(A + L * D_AB);
}

int main() {
  scanf("%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y);
  scanf("%lf%lf%lf%lf", &C.x, &C.y, &D.x, &D.y);
  scanf("%lf%lf%lf", &p, &q, &r);
  D_AB = B - A; D_DC = C - D;
  printf("%.2lf\n", solve());
  return 0;
}