[HAOI2006]旅行COMF

[HAOI2006]旅行COMF

根据数据范围求解，有，好了，直接暴力贪心地选择一段值连续的边，然后判断是否联通即可。

所以我们只要预先对边按照排个序，然后用并查集判断是否联通即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 10;

struct Edge {
  int x, y, w;

  Edge(int _x = 0, int _y = 0, int _w = 0) : x(_x), y(_y), w(_w) {}

  void read() {
    scanf("%d %d %d", &x, &y, &w);
  }

  bool operator < (const Edge &t) const {
    return w > t.w;
  }
}a[N];

int n, m, s, t, fa[N];

void init() {
  for (int i = 1; i <= n; i++) {
    fa[i] = i;
  }
}

int find(int rt) {
  return rt == fa[rt] ? rt : fa[rt] = find(fa[rt]);
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    a[i].read();
  }
  scanf("%d %d", &s, &t);
  sort(a + 1, a + 1 + m);
  const int inf = 0x3f3f3f3f;
  int ans_max = inf, ans_min = 1;
  for (int i = 1; i <= m; i++) {
    int cur_max = a[i].w, cur_min = inf, flag = 0;
    init();
    for (int j = i; j <= m; j++) {
      int fx = find(a[j].x), fy = find(a[j].y);
      if (fx != fy) {
        fa[fx] = fy;
      }
      if (find(s) == find(t)) {
        cur_min = a[j].w;
        flag = 1;
        break;
      }
    }
    if (flag) {
      if ((double)cur_max / cur_min < (double)ans_max / ans_min) {
        ans_max = cur_max;
        ans_min = cur_min;
      }
    }
  }
  if (ans_max == inf) {
    puts("IMPOSSIBLE");
  }
  else {
    int d = __gcd(ans_max, ans_min);
    if (d == ans_min) {
      printf("%d\n", ans_max / d);
    }
    else {
      printf("%d/%d\n", ans_max / d, ans_min / d);
    }
  }
  return 0;
}