社区讨论

求写法问题WA on s2#1

P1195口袋的天空参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mlhovvn1
此快照首次捕获于
2026/02/11 15:09
上周
此快照最后确认于
2026/02/13 10:55
6 天前
查看原帖
怎么改才不用特判尼?
CPP
#include<bits/stdc++.h>
using namespace std;
const long long M = 2e5 + 5;
const long long N = 5005;
long long n , m , fa[N] , k;
long long find(long long x)
{
    return (fa[x] == x) ? x : (fa[x] = find(fa[x]));
}
struct E{
    long long u , v , w;  
}e[1000005];
bool cmp(E a,E b)
{
    return a.w < b.w;
}
long long ans = 0;
long long zxscs()
{
    long long cnt = 0;
    sort(e + 1 , e + m + 1,cmp);
    for(long long i= 1;i <= m;i++)
    {
        if(cnt >= n - k)
            break;
        long long fu = find(e[i].u);
        long long fv = find(e[i].v);
        if(fu != fv)
        {
            fa[fu] = fv;
            cnt ++ , ans += e[i].w;
        }
        if(cnt >= n - k)
            break;
    }
    if(cnt >= n - k)
        return 1;
    else
        return -1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    if(n < k)
    {cout << "No Answer";return 0;}
    for(long long i = 0;i <= n;i++)
        fa[i] = i;
    for(long long i = 1;i <= m;i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    if(zxscs()!=-1)cout<<ans;
    else cout << "No Answer";
    return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...