求助!从昨天调到今天,发现了错误但是不理解
  • 板块CF125E MST Company
  • 楼主E_huanJX泛舟客
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/12/10 08:32
  • 上次更新2023/10/26 23:59:18
查看原帖
求助!从昨天调到今天,发现了错误但是不理解
546246
E_huanJX泛舟客楼主2022/12/10 08:32

也不能叫做发现了错误,但是找到了有问题的位置(这其实不是我代码,是我拿别的AC代码魔改的,把排序改成我的写法就挂了)。

原本能AC的代码是把和1相连的与不和1相连的分开来,然后按照边权排序。排序函数:return w < b.w; 可以 AC。我只把排序函数改成:

bool operator<(node b) 
{ 
    if(w!=b.w) 
        return w < b.w; 
    return (x==1||y==1)>(b.x==1||b.y==1);
}

就WA了,且最后一行不管是> < >= <=都会WA。

有人看看什么原因吗!!?拜谢!!!!

完整 AC 代码:(按上述方法改了比较函数就 WA)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &x)
{
    x = 0;
    char c = getchar(), f = 0;
    for (; c < 48 || c > 59; c = getchar())
        if (!(c ^ 45))
            f = 1;
    for (; c >= 48 && c <= 57; c = getchar())
        x = (x << 1) + (x << 3) + (c ^ 48);
    f ? x = -x : 0;
}
struct node
{
    int x, y;
    double w;
    int id;
    bool operator<(node b) 
    { 
        // if(w!=b.w) 
            return w < b.w; 
        // return (x==1||y==1)>=(b.x==1||b.y==1);
    }
} e[100005], e1[100005], e2[100005],bk[100005];
int n, m, K, fa[10005], t1, t2;
inline int getf(int x) { return fa[x] == x ? x : fa[x] = getf(fa[x]); }
inline char mrg(int x, int y)
{
    x = getf(x), y = getf(y);
    if (x ^ y)
        return fa[x] = y, 1;
    else
        return 0;
}
// ↑并查集

inline char check(ll w)
{
    int cnt = 0;
    memcpy(e,bk,sizeof bk);

    for(int i=1;i<=m;i++) 
        if(e[i].x==1||e[i].y==1) 
            e[i].w+=w / 10000.0;
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
        if (mrg(e[i].x, e[i].y))
            cnt += (e[i].x == 1 || e[i].y == 1);
    for(int i=1;i<=m;i++) 
        if(e[i].x==1||e[i].y==1) 
            e[i].w-=w / 10000.0;
    return cnt <= K; // 计算有多少个点与 1 相连
} // ↑二分check函数
int main()
{
    read(n), read(m), read(K);
    ll le = -1e9 - 7, ri = 1e9 + 7; // 值域,尽量大
    for (int i = 1, x, y, w; i <= m; i++)
    {
        read(x), read(y), read(w);
        if (x == 1 || y == 1)
            e1[++t1] = (node){x, y, w, i};
        else
            e2[++t2] = (node){x, y, w, i};
        // e[i]={x,y,w,i};
    }
    for (int i = 1; i <= t1; i++)
        e[i] = e1[i];
    for (int i = 1; i <= t2; i++)
        e[i + t1] = e2[i];
    memcpy(bk,e,sizeof e);
    // ↑把边分类   ↓wqs二分主体(一行
    while (le < ri)
    {
        ll md = (le + ri) >>1;
        if (check(md))
            ri = md ;
        else
            le = md + 1;
    }
    if (!check(ri))
        return puts("-1"), 0;
    else
        printf("%d\n", n - 1);
    memcpy(e,bk,sizeof bk);
    for(int i=1;i<=m;i++) 
        if(e[i].x==1||e[i].y==1) 
            e[i].w+=ri / 10000.0;
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
        if (mrg(e[i].x, e[i].y))
            printf("%d ", e[i].id);
    return putchar('\n'), 0; // ↑输出方案,check 直接赋值一遍(
}
2022/12/10 08:32
加载中...