翻车笔记_ [HAOI2006]旅行comf [并查集, SB题]

完了完了不会并查集了…

懵逼的 题目

扯淡的 题解

一看省选题满脑子图论骚操作…无果…

昊哥表示我联赛前就A了(Orzzzzz)然后开始在旁边翻题解…瞄到两个字 “排序”…

艹 sb题…

按照$cost$从大到小排序, 然后枚举最大的$cost$, 然后顺着枚举…枚举一条边就把他的两个端点加在并查集里, 直到$S, T$在一个并查集里…更新答案…

这要是考场出这玩意我不就完了嘛…

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**************************************************************
Problem: 1050
User: Cansult
Language: C++
Result: Accepted
Time:2644 ms
Memory:1352 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (500 + 5)
#define MAXM (5000 + 5)
#define INF (30000 + 5)
#define pii pair<int, int>
using namespace std;
struct edg
{
int from, to, cost;
}b[MAXM];
int fa[MAXN], n, m, s, t;
pii ans;
int find(int x)
{ return (fa[x] == x ? x : (fa[x] = find(fa[x]))); }
void uni(int x, int y)
{ fa[find(y)] = find(x); }
bool cmp(edg x, edg y)
{ return x.cost > y.cost; }
int gcd(int x, int y)
{ return (!y ? x : gcd(y, x % y)); }
bool cmpp(pii x, pii y)
{
int tx = gcd(x.second, y.second);
int fx = x.first * (y.second / tx), fy = y.first * (x.second / tx);
return fx > fy;
}
void solve()
{
ans = make_pair(INF, 1);
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
fa[j] = j;
for (int j = i; j <= m; j++)
if (find(b[j].from) != find(b[j].to))
{
uni(b[j].from, b[j].to);
if (find(s) == find(t))
{
if (cmpp(ans, make_pair(b[i].cost, b[j].cost)))
ans = make_pair(b[i].cost, b[j].cost);
break;
}
}
}
}
int main(int argc, char const *argv[])
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d%d", &b[i].from, &b[i].to, &b[i].cost);
scanf("%d%d", &s, &t);
sort(b + 1, b + m + 1, cmp);
solve();
if (ans != make_pair(INF, 1))
{
int tg = gcd(ans.first, ans.second);
ans.first /= tg, ans.second /= tg;
if (ans.second != 1)
printf("%d/%d\n", ans.first, ans.second);
else
printf("%d\n", ans.first);
}
else
puts("IMPOSSIBLE");
return 0;
}

By 药丸的 Cansult