完了完了不会并查集了…

懵逼的 题目

扯淡的 题解

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

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

艹 sb题…

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

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

沙茶的 代码

/**************************************************************
    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