3号wa求改

StarSide @ 2024-10-25 20:08:46

#include<bits/stdc++.h>

using namespace std;
typedef struct Node {
    int weight;
    int vertex;
} Node;
int lowcost[10011];
int ans = 0;
vector<Node> G[10011];
int v, e;

void prim(vector<Node> g[], int x) {
    for (int i = 1; i <= v; i++) {
        lowcost[i] = 100000;
    }
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i].vertex;
        int w = g[x][i].weight;
        lowcost[y] = w;
    }
    lowcost[x] = 0;
    for (int cnt = 1; cnt < v; cnt++) {
        int Min = 100000, k = x;
        for (int i = 1; i <= v; i++) {
            if (lowcost[i] < Min && lowcost[i] != 0) {
                Min = lowcost[i];
                k = i;
            }
        }
        ans += Min;
        lowcost[k] = 0;
        x = k;

        for (int j = 0; j < g[x].size(); j++) {
            int y = g[x][j].vertex;
            int w = g[x][j].weight;
            if (lowcost[y] > w) {
                lowcost[y] = w;
            }
        }
    }
}

int main() {
    cin >> v >> e;
    for (int i = 0; i < e; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        Node n;
        n.vertex = x, n.weight = w;
        G[y].push_back(n);
        n.vertex = y, n.weight = w;
        G[x].push_back(n);
    }
    prim(G, 1);
    for (int i = 1; i <= v; i++) {
        if (lowcost[i] == 100000) {
            cout << "orz";
            return 0;
        }
    }
    cout << ans;
}

by zjr2014 @ 2024-11-09 16:31:22

@StarSide

#include<bits/stdc++.h>
using namespace std;
int read(){
    int r=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')r=(r<<3)+(r<<1)+(c^48),c=getchar();
    return r*f;
}
void file(string s){
    s+=".in";
    freopen(s.c_str(),"r",stdin);
    s.pop_back();
    s.pop_back();
    s.pop_back();
    s+=".out";
    freopen(s.c_str(),"w",stdout);
}
void IOS(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int fa[100000001];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
void init(int n){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}
struct Edge{
    int u,v,w;
    bool operator<(const Edge p){
        return w<p.w;
    }
}edge[100000001];
int m,n,u,v,w,cnt,ans;
int main(){
    IOS();
    cin>>n>>m;
    init(n);
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        edge[i].u=u;
        edge[i].v=v;
        edge[i].w=w;
    }
    sort(edge+1,edge+m+1);
    for(int i=1;i<=m;i++){
        u=edge[i].u;
        v=edge[i].v;
        if(find(u)==find(v)){
            continue;
        }
        ans+=edge[i].w;
        merge(u,v);
        cnt++;
        if(cnt==n-1){
            break;
        }
    }
    if(cnt!=n-1){
        cout<<"orz";
    }
    else{
        cout<<ans;
    }
    return 0;
}