35pts玄关求调

P3366 【模板】最小生成树

3ksc03_is_sb @ 2024-07-22 10:43:38

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
using namespace std;
int nimm[5001];
int a[5001][5001];
bool b[5001];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        if(a[x][y]==0){
            a[x][y]=z;
            a[y][x]=z;
        }
        else{
            a[x][y]=min(z,a[x][y]);
            a[y][x]=min(z,a[y][x]);
        }
    }
    memset(nimm,0x7f,sizeof(nimm));
    nimm[1]=0;
    memset(b,1,sizeof(b));
    for(int i=1;i<=n;i++){
        long long k=0;
        for(int j=1;j<=n;j++){
            if(b[j]==1&&(nimm[j]<nimm[k])&&a[i][j]!=0){
                k=j;
            }
        }

        b[k]=0;
        for(int j=1;j<=n;j++){
            if(b[j]==1&&(a[k][j]<nimm[j])&&a[k][j]!=0){
                nimm[j]=a[k][j];
            }
        }
    }
    int YHP=0;
    int num=0;
    for(int i=1;i<=n;i++){
        if(nimm[i]==0) num++;
        YHP+=nimm[i];
    }
    if(num==1) cout<<YHP;
    else cout<<"orz";
    return 0;
}

（名字被人改了QWQ ）

by 3ksc03_is_sb @ 2024-07-22 11:30:10

第二版58pts

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
using namespace std;
int nimm[5001];
int a[5001][5001];
bool b[5001];
bool ap[5001][5001];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        if(x==y) continue;
        if(ap[x][y]==0){
            a[x][y]=z;
            a[y][x]=z;
            ap[x][y]=1;
            ap[y][x]=1;
        }
        else{
            a[x][y]=min(z,a[x][y]);
            a[y][x]=min(z,a[y][x]);
        }
    }
    memset(nimm,0x7f,sizeof(nimm));
    nimm[1]=0;
    memset(b,1,sizeof(b));
    for(int i=1;i<=n;i++){
        int k=0;
        for(int j=1;j<=n;j++){
            if(b[j]==1&&(nimm[j]<nimm[k])&&ap[i][j]!=0){
                k=j;
            }
        }

        b[k]=0;
        for(int j=1;j<=n;j++){
            if(b[j]==1&&(a[k][j]<nimm[j])&&ap[k][j]!=0){
                nimm[j]=a[k][j];
            }
        }
    }
    int YHP=0;
    int num=0;
    for(int i=1;i<=n;i++){
//      cout<<nimm[i]<<" ";
        if(nimm[i]>=114514){
            num++;
        }
        YHP+=nimm[i];
    }
    if(num==2) cout<<"orz";
    else cout<<YHP;
    return 0;
}

by wwwidk1234 @ 2024-07-22 11:30:31

@3ksc03_is_sb 

// Problem: P3366 【模板】最小生成树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3366
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
using namespace std;
int nimm[5001];
int a[5001][5001];
bool vis[5001];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        if(a[x][y]==0){
            a[x][y]=z;
            a[y][x]=z;
        }
        else{
            a[x][y]=min(z,a[x][y]);
            a[y][x]=min(z,a[y][x]);
        }
    }
    memset(nimm,0x7f,sizeof(nimm));
    nimm[1]=0;
    long long ans=0;
    for(int i=1;i<=n;i++){
        long long k=0;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&(nimm[j]<nimm[k]))
                k=j;

        if(k==0) return 0&puts("orz");

        vis[k]=1;ans+=nimm[k];
        // cerr<<k<<' '<<nimm[k]<<endl;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&(a[k][j]<nimm[j])&&a[k][j]!=0)
                nimm[j]=a[k][j];
    }
    int YHP=0;
    int num=0;
    for(int i=1;i<=n;i++){
        if(nimm[i]==0) num++;
        YHP+=nimm[i];
    }
    if(num==1) cout<<ans;
    else cout<<"orz";
    return 0;
}
// https://www.luogu.com.cn/discuss/863149
// b->vis

by wwwidk1234 @ 2024-07-22 11:32:12

@3ksc03_is_sb

  1. 有点没看懂你后面这一段 for(int i=1;i<=n;i++){if(nimm[i]==0) num++;YHP+=nimm[i];} 写的啥
  2. 你的i是已选择的边数，a[i][j]!=0 错了。
  3. 下次建议给代码加点注释，不然可读性太差调代码也麻烦。

by wwwidk1234 @ 2024-07-22 11:33:59

@3ksc03_is_sb 在你第一版基础上改的，第二版没看到。

by 3ksc03_is_sb @ 2024-07-22 11:34:42

谢谢，已关

by wwwidk1234 @ 2024-07-22 11:35:44

@3ksc03_is_sb 后面那段好像可以去掉，试了下如果选出来的 k=0 那么直接判定无解即可。

验证码 CYNO 赛诺 祭

|