社区讨论
同样的最小生成树,不一样的结局,求大佬指错
P1546[USACO3.1] 最短网络 Agri-Net参与者 6已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mi6m0ml1
- 此快照首次捕获于
- 2025/11/20 07:04 4 个月前
- 此快照最后确认于
- 2025/11/20 07:04 4 个月前
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct x_x{
int x;int y;int c;
};
x_x a[10001];
bool f[101][101];
bool ff[101];
int n,m,x,y,i,j;
bool ccc(x_x aa,x_x bb)
{
if(aa.c<bb.c) return true;
return false;
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&x);
if(!f[i][j]&&i!=j)
{a[++m].x=i;a[m].y=j;a[m].c=x;}
f[i][j]=true;
}
sort(a+1,a+m+1,ccc);
x=0;y=0;
for(i=1;i<=m;i++)
{
if(y==n-1) {cout<<x<<endl;exit(0);}
if(!ff[a[i].x]||!ff[a[i].y])
{
ff[a[i].x]=ff[a[i].y]=true;
x+=a[i].c;y++;
}
}
return 0;
}
虽然不愿接受,但是如果真的是我连最小生成树都不会打了,大佬们指出来我也会万分感谢的
回复
共 6 条回复,欢迎继续交流。
正在加载回复...