poj题目求助,判断是否唯一最小生成树的,大佬看看
  • 板块题目总版
  • 楼主KomorKomor
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/16 20:22
  • 上次更新2024/7/16 21:31:10
查看原帖
poj题目求助,判断是否唯一最小生成树的,大佬看看
1106289
KomorKomor楼主2024/7/16 20:22
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#define ll long long
#define inff 1e18
#define inf 1e9
using namespace std;

struct edge
{
    int u,v,w,id;
};
vector<edge> vv;

vector<int> mst;
int n,m,a[200];

bool cmp(edge a,edge b)
{
    return a.w<b.w;
}

int find(int x)
{
    if(a[x]==x) return x;
    else return a[x]=find(a[x]);
}

void add(int x,int y)
{
    int xx=find(x),yy=find(y);
    if(xx!=yy)  a[xx]=yy;
}

int kru(int x)
{
    int ans=0,cnt=0;
    for(int i=1;i<=n;i++)   a[i]=i;
    for(auto e:vv)
    {
        if(e.id==x) continue ;
        int u=e.u,v=e.v,w=e.w;
        if(find(u)!=find(v))
        {
            ans+=w; cnt++;
            if(x==0)    mst.push_back(e.id);
            if(cnt==n-1)    return ans;
        }
    }
    return -1;
}

void solve()
{
    cin>>n>>m;
    vv.clear(),mst.clear();
    for(int i=1;i<=n;i++)   a[i]=i;

    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        vv.push_back({u,v,w,i});
    }

    sort(vv.begin(),vv.end(),cmp);

    int mst_value=kru(0);

    for(auto e:mst)
    {
        int temp=kru(e);
        if(mst_value==temp)
        {
            cout<<"Not Unique!";
            return ;
        }
    }

    cout<<mst_value<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t=1;  cin>>t;
    while(t--)  solve();
    return 0;
}

调一天了,不知道为什么一直给我错,吐血

2024/7/16 20:22
加载中...