怎么特判无解？

暗影之梦 @ 2021-10-22 20:22:18

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int n,m,ans,cnt;
int fa[50001];
struct edge
{
    int u,v,w;
}e[200001];
bool cmp(edge a,edge b)
{
    return a.w<b.w;
}
int find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(find(e[i].u)!=find(e[i].v))
        {
            ans+=e[i].w;
            fa[find(e[i].u)]=find(e[i].v);
//          if(++cnt==n-1) continue;
        }
    }
    if(cnt==m) cout<<"orz"<<endl;
    else cout<<ans<<endl;
    return 0;
}

by _tourist @ 2021-10-22 20:23:33

@暗影之梦 实际上这题的数据并没有不连通的情况qwq

by 暗影之梦 @ 2021-10-22 20:23:58

@LeoWayyyyyyy 有一个,数据13

by int64 @ 2021-10-22 20:24:15

@LeoWayyyyyyy 错

by 暗影之梦 @ 2021-10-22 20:24:22

不过已经解决了，谢谢

by 暗影之梦 @ 2021-10-22 20:25:15

把自己正确的代码放上来让后面的oier参照一下如何特判。

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int n,m,ans,cnt;
int fa[50001];
struct edge
{
    int u,v,w;
}e[200001];
bool cmp(edge a,edge b)
{
    return a.w<b.w;
}
int find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(find(e[i].u)!=find(e[i].v))
        {
            ans+=e[i].w;
            fa[find(e[i].u)]=find(e[i].v);
            if(++cnt==n-1)
            {
                cout<<ans<<endl;
                return 0;
            }
        }
    }
    cout<<"orz"<<endl;
    return 0;
}

by underline__jian @ 2021-11-25 21:22:32

@暗影之梦 所以说我Prime要怎么特判啊 QWQ

by underline__jian @ 2021-11-25 21:23:03

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+15,mxn=5e3+15;
struct node{
    int t,d;
    bool operator<(const node &a) const {return d>a.d;}
};
int n,m,vis[mxn];
vector<node> e[mxn];
priority_queue<node> q;
inline int read(){
    char ch=getchar();
    int s=0,f=1;
    while(!(ch>='0'&&ch<='9')){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0'; ch=getchar();}
    return s*f;
}
ll prim(){
    ll ans=0;
    int cnt=0;
    q.push((node){1,0});
    while(!q.empty()&&cnt<=n){
        node k=q.top();
        q.pop();
        if(vis[k.t]) continue;
        vis[k.t]=1;
        ans+=k.d;
        cnt++;
        for(int i=0;i<e[k.t].size();i++)
            if(!vis[e[k.t][i].t]) q.push((node){e[k.t][i].t,e[k.t][i].d});
    }
    return ans;
}
int main(){
    n=m=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),z=read();
        e[x].push_back((node){y,z});e[y].push_back((node){x,z});
    }
    printf("%lld",prim());
    return 0;
}

by Benny_Li @ 2022-10-05 20:09:13

打表罢（