「HNOI2009」最小圈

题目链接:洛谷3199

Description

给你一张有向带权图,求出图中的最小比率生成环。

Data Range

$n\leq 3000,m\leq 10000,w_{i,j}\leq 10^7$

Solution

考虑$01$分数规划。

记录$x_i[0..1]$表示当前这一条边是否取,那么答案就是$min(\frac{\sum w_i}{\sum x_i})$,记录最小比率为$M$。

那么转化式子为$\frac{\sum w_i\times x_i}{\sum x_i}\leq M$,化简得到$\sum x_i \times (\sum w_i-M)\leq 0$。

显然前面的一部分$>0$,所以就是后面一部分的答案$\leq 0$,而$M$很明显具有单调性。问题就变成了二分$M$,每一条边的权值$-M$后判断原图是否有环即可。

Code

#include <bits/stdc++.h>
#define REP(i, s, t) for (int i = (s), i##ed = (t); i <= i##ed; ++ i)
using namespace std;
const int MAXN = 3005;
const int MAXM = 10005;
struct _edge {
  int to, nt; 
  double w;
} E[MAXM];
int H[MAXN], edge_cnt;
void add_edge(int u, int v, double w) {
  E[++ edge_cnt] = (_edge) {v, H[u], w};
  H[u] = edge_cnt;
}
int n, m;
bool flg;
double dis[MAXN];
bool vis[MAXN];
void spfa(int u) {
  vis[u] = 1;
  for (int e = H[u]; e; e = E[e].nt) {
    int v = E[e].to;
    if (dis[v] > dis[u] + E[e].w) {
      if (vis[v] || flg) { flg = 1; break; }
      dis[v] = dis[u] + E[e].w;
      spfa(v);
    }
  }
  vis[u] = 0;
}
bool check(double x) {
  memset(dis, 0, sizeof dis);
  REP(i, 1, edge_cnt) E[i].w -= x;
  flg = 0;
  REP(i, 1, n) {
    spfa(i);
    if (flg) break;
  }
  REP(i, 1, edge_cnt) E[i].w += x;
  return flg;
}
int main() {
  scanf("%d%d", &n, &m);
  REP(i, 1, m) {
    int u, v; double w; 
    scanf("%d%d%lf", &u, &v, &w);
    add_edge(u, v, w);
  }
  double l = -1e7, r = 1e7;
  REP(it, 1, 170) {
    double mid = (l + r) / 2.0;
    if (check(mid)) r = mid;
    else l = mid;
  }
  printf("%.8lf\n", l);
  return 0;
}
最后修改:2019 年 08 月 25 日 12 : 35 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论