题解

目标就是

\[Maximize\ \lambda = \frac{X-Y}{k}
\]

按照分数规划的一般规律，

构造：

\[g(\lambda) = \lambda k + Y - X
\]

由于总流量不变，我们考虑转移流量。

注意到，对于每条边，我们如果增加其容量则会增加(b[i]+d[i]+lambda)点值，如果减少就是(a[i]-d[i]+lambda)点值。

如果可以构成一个负环，那么就一定可以更优。

所以我们二分\(\lambda\)，check即可。

代码

#include <bits/stdc++.h>

using namespace std;

#define eps 1e-5

struct haha {

  int x, y, a, b, c, d;

};

struct edge {

  int from, to;

  double cost;

};

const int maxn = 5005;

vector<edge> G[maxn];

haha b[maxn];

int n, m;

int vis[maxn], flag;

double dist[maxn];

void add_edge(int from, int to, double cost) {

  G[from].push_back((edge){from, to, cost});

}

void dfs(int i) {

  vis[i] = 1;

  for (int j = 0; j < G[i].size(); j++) {

    edge &e = G[i][j];

    if (dist[e.to] > dist[i] + e.cost) {

      if (vis[e.to])

        flag = 1;

      else {

        dist[e.to] = dist[i] + e.cost;

        dfs(e.to);

      }

    }

  }

  vis[i] = 0;

}

bool check(double lambda) {

  for (int i = 1; i <= n; i++)

    G[i].clear();

  for (int i = 1; i <= m; i++) {

    if (b[i].c)

      add_edge(b[i].y, b[i].x, b[i].a - b[i].d + lambda);

    add_edge(b[i].x, b[i].y, b[i].b + b[i].d + lambda);

  }

  flag = 0;

  memset(vis, 0, sizeof(vis));

  memset(dist, 0, sizeof(dist));

  for (int i = 1; i <= n && !flag; i++) {

    dfs(i);

  }

  return flag;

}

int main() {

  // freopen("input", "r", stdin);

  scanf("%d %d", &n, &m);

  n += 2;

  for (int i = 1; i <= m; i++)

    scanf("%d%d%d%d%d%d", &b[i].x, &b[i].y, &b[i].a, &b[i].b, &b[i].c, &b[i].d);

  double L = 0, R = 10000000;

  while (R - L > eps) {

    double mid = (L + R) / 2;

    if (check(mid))

      L = mid;

    else

      R = mid;

  }

  printf("%.2f\n", L);

}

总结

图上的分数规划问题要考虑分摊到每个边上。
分数规划问题要注意double的赋值。

巴特西

[bzoj3597][scoi2014]方伯伯运椰子——分数规划，负环

题解

代码

总结

最新文章

热门文章