社区讨论
求写法问题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 条回复,欢迎继续交流。
正在加载回复...