NirvanaCeleste @ 2024-06-10 17:20:05
#include <bits/stdc++.h>
using namespace std;
int n,m,tot,ans;
bool vis[1000100];
struct op{
int vlu,to;
op(int a,int b){vlu=a,to=b;}
friend bool operator < (const op aa,const op bb){//重载小于号 注意不能重载大于号
if(aa.vlu != bb.vlu) return aa.vlu < bb.vlu;
}
};
struct node {
int to,vlu;
} pll;
vector<node> adj[1000100];
priority_queue <op> stk;
void insert_edge(int u,int v,int w) {
pll.to = v;
pll.vlu = w;
adj[u].push_back(pll);
pll.to = u;
adj[v].push_back(pll);
pll.to = pll.vlu = 0;
}
void put_stk(int x) {
vis[x] = 1;
for(int i=0; i<adj[x].size(); ++i) {
int v = adj[x][i].to,w = adj[x][i].vlu;
if(!vis[v]) stk.push(op(w,v));
}
}
int pop_stk() {
int pop_temp = 0;
while(vis[stk.top().to] && !stk.empty()) stk.pop();
if(!stk.empty()){
pop_temp = stk.top().vlu;
put_stk(stk.top().to);
stk.pop();
}
return pop_temp;
}
void prim(int x) {
memset(vis,0,sizeof(vis));
vis[x] = 1;
put_stk(x);
while(!stk.empty()) ans += pop_stk();
}
void dfs(int x) {
vis[x] = 1;
for(int i=0; i<adj[x].size(); ++i) {
int v = adj[x][i].to;
if(!vis[v]) dfs(v);
}
return;
}
bool pd() {
dfs(1);
for(int i=1; i<=n; i++) if(!vis[i]) return 0;
return 1;
}
int main() {
cin>>n>>m;
int u,v,w;
for(int i=1; i<=m; i++) {
scanf("%d %d %d",&u,&v,&w);
insert_edge(u,v,w);
}
if(m >= n - 1 && pd()) {
prim(1);
cout<<ans;
} else cout<<"orz";
return 0;
}#include <bits/stdc++.h>
using namespace std;
int f[1000100];
int n,m,tot,ans;
bool vis[1000100];
struct edge{
int pre,to,w;
}e[1000100];
vector<int> adj[1000100];
bool cmp(edge px,edge py){return px.w < py.w;}
void insert_edge(int u,int v,int w){
e[++tot].pre = u;
e[tot].to = v;
e[tot].w = w;
adj[u].push_back(v);
adj[v].push_back(u);
}
int find(int x){
if(f[x] == x) return x;
else return f[x] = find(f[x]);
}
void kpp(){
int fa = 0,fb = 0;
for(int i=1;i<=tot;i++){
fa = find(e[i].pre),fb = find(e[i].to);
if(fa != fb) f[fa] = fb,ans += e[i].w;
}
}
void dfs(int x){
vis[x] = 1;
for(int i=0;i<adj[x].size(); ++i){
int v = adj[x][i];
if(!vis[v]) dfs(v);
}
return;
}
bool pd(){
dfs(1);
for(int i=1;i<=n;i++) if(!vis[i]) return 0;
return 1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) f[i] = i;
int u,v,w;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&u,&v,&w);
insert_edge(u,v,w);
}
if(m >= n - 1 && pd()){
sort(e+1,e+tot+1,cmp);
kpp();
cout<<ans;
}
else cout<<"orz";
return 0;
} by NirvanaCeleste @ 2024-06-12 11:56:49
#include <bits/stdc++.h>
using namespace std;
const int M = 1000100;
int n,m,ans,cnt;
bool vis[M];
struct op {
int op_vlu,op_to;
op(int a,int b) {
op_vlu = a , op_to = b;
}
friend bool operator < (const op &aa,const op &bb) {
return aa.op_vlu > bb.op_vlu;
}
};
struct node {
int to,vlu;
};
vector<node> adj[M];
priority_queue <op> stk;
void insert_edge(int u,int v,int w) {
node pll;
pll.vlu = w;
pll.to = v;
adj[u].push_back(pll);
}
void put_stk(int x) {
cnt++;//
vis[x] = 1;
for(int i=0; i<adj[x].size(); ++i) {
int xv = adj[x][i].to,xw = adj[x][i].vlu;
if(!vis[xv]) stk.push(op(xw,xv));
}
}
int pop_stk() {
int pop_temp = 0,push_temp = 0;
while(vis[stk.top().op_to] && !stk.empty()) stk.pop();
if(!stk.empty()) {
pop_temp = stk.top().op_vlu;
push_temp = stk.top().op_to;
stk.pop();
put_stk(push_temp);
// cnt++;// 为什么不能在这cnt++,因为第一个点加不上去，在这写需要让cnt=1
// put_stk(stk.top().op_to); 不能这样写，改变了堆的结构
// stk.pop();
}
return pop_temp;
}
void prim(int x) {
put_stk(x);
while(!stk.empty() && cnt <= n) {
ans += pop_stk();
// cnt++;//
/*
如果你在pop_stk()中调用cnt++，那么可能会出现以下情况：
你从优先队列中选择了一条边，并尝试将其对应的节点加入到生成树中。
但是，由于某种原因（例如，该节点已经是一个环的一部分，或者该边与
之前的某条边形成了更小的权重），你实际上并没有将这个节点加入到生
成树中（即没有调用put_stk(push_temp);）。
然而，由于你在pop_stk()中递增了cnt，你已经错误地表示了这个节点已
经被加入到生成树中。
这会导致cnt的值比实际加入到生成树中的节点数量要大，进而可能导致算法在
错误的时间点终止（即当cnt > n时），从而得到一个不完整的最小生成树（或
者根本没有找到最小生成树）。
因此，为了确保cnt正确地表示了已经加入到最小生成树中的节点数量，你应该
在将节点加入到生成树中（即调用put_stk(x)）时递增cnt，而不是在选择边（
即调用pop_stk()）时递增。
*/
}
}
int main() {
cin>>n>>m;
int u,v,w;
for(int i=1; i<=m; i++) {
scanf("%d %d %d",&u,&v,&w);
insert_edge(u,v,w);
insert_edge(v,u,w);
}
memset(vis,0,sizeof(vis));
prim(1);
if(cnt == n) cout<<ans;
else cout<<"orz";
return 0;
}by NirvanaCeleste @ 2024-06-12 11:57:10
已结