P1194 Kruskal全wa!求调
  • 板块题目总版
  • 楼主florr_ida
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/12/17 19:16
  • 上次更新2023/12/17 19:18:24
查看原帖
P1194 Kruskal全wa!求调
457444
florr_ida楼主2023/12/17 19:16

kruskal全wa求助! P1194 买礼物

#include<bits/stdc++.h>
using namespace std;
struct edge
{
    int u,v,w;
}ed[250005];
int k;
int n,m,ans=0,t[250005],total;
bool cmp(edge a,edge b)
{
    return a.w<b.w;
}
int find(int u)
{
    return t[u]==u ? u : find(t[u]);
}
void init()
{
    for(int i=0;i<=n;i++)
    {
        t[i]=i;
    }
}
void init2(int x,int y,int z)
{
    k++;
        ed[k].u=x;
        ed[k].v=y;
        ed[k].w=z;
}
int kruskal()
{
    init();
    sort(ed+1,ed+m+2,cmp);
    int xxxx=1;
    while(xxxx<=k)
    {
        int b=find(ed[xxxx].u);
        int c=find(ed[xxxx].v);
        if(b==c) {xxxx++; continue;}
        t[c]=b;
        ans+=ed[xxxx].w;
        total++;
        if(total>=m) break;
        xxxx++;
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++)
        {
            int w;
            cin>>w;
            if(i<j&&w!=0) init2(i,j,w);
        }
    }
    for(int i=1;i<=m;i++)
        {
            init2(0,i,n);
        }
    kruskal();
    cout<<ans;
    return 0;
}
2023/12/17 19:16
加载中...