50pts,WA后五个点求调
查看原帖
50pts,WA后五个点求调
566168
川寰boy楼主2024/1/29 15:22
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <deque>

using namespace std;

#define rd read()
#define int long long

const int N = 5e3 + 10;
const int MOD = 998244353;
const int INF = 0x7fffffff;
const int Fill = 0x3f;
const int FillINF = 0x3f3f3f3f;

int read()
{
    char ch;
    int type = 1, n = 0;
    ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            type = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        n = (n << 1) + (n << 3) + (ch ^ 48);
        ch = getchar();
    }
    return n * type;
}

int n, m, s, t, p, q, ansp = INF, ansq = 0;
int fa[N * 2];
long double min_ = 1e11;

struct edge
{
    int u, v, weight;
    bool operator<(const edge &k) const
    {
        return weight > k.weight;
    }
} G[N * 2];

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

void union_(int x, int y)
{
    int fax = find(x);
    int fay = find(y);
    if (fax == fay)
    {
        return;
    }
    fa[x] = y;
}

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

void solve()
{
    int i, j;
    n = rd, m = rd;
    init();
    for (i = 1; i <= m; i++)
    {
        G[i].u = rd;
        G[i].v = rd;
        G[i].weight = rd;
        union_(G[i].u, G[i].v);
        // union_(G[i].v, G[i].u);
    }
    s = rd, t = rd;
    if (find(s) != find(t))
    {
        printf("IMPOSSIBLE");
        return;
    }
    sort(G + 1, G + m + 1);
    for (i = 1; i <= m; i++)
    {
        init();
        for (j = i; j <= m; j++)
        {
            union_(G[j].u, G[j].v);
            // union_(G[j].v, G[j].u);
            if (find(s) == find(t))
            {
                // long double t = (long double)(1.0 * G[i].weight) / (long double)(1.0 * G[j].weight);
                // if (min_ > t)
                // {
                //     min_ = t;
                //     p = G[i].weight, q = G[j].weight;
                //     break;
                // }
                p = G[i].weight, q = G[j].weight;
                if (ansp * q > p * ansq)
                {
                    ansp = p, ansq = q;
                }
                break;
            }
        }
    }
    if (ansp % ansq)
    {
        printf("%d/%d", ansp / __gcd(ansp, ansq), ansq / __gcd(ansp, ansq));
    }
    else
    {
        printf("%d", ansp / ansq);
    }
}

signed main()
{
    int T;
    int i, j;
    T = 1;
    while (T--)
    {

        solve();
    }
    return 0;
}

交叉相乘比较和浮点数比较都试了,分一样,求调

2024/1/29 15:22
加载中...