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

可以给比赛、队伍都建点，然后\(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;
}

• 相关文章
• 全局相关文章