社区讨论

同样的最小生成树,不一样的结局,求大佬指错

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 条回复,欢迎继续交流。

正在加载回复...