julihui325 @ 2024-08-01 16:45:26
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
int x=0;
short f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
struct edge{
int to,nxt,w;
}e[400010];
struct node{
int id,dist;
bool operator < (node x) const{
return x.dist<dist;
}
};
int head[200010],tot;
void add(int u,int v,int w){
e[++tot].to=v;
e[tot].nxt=head[u];
e[tot].w=w;
head[u]=tot;
}
int n,m,dis[5010];
bool vis[5010];
priority_queue <node> q;
int main(){
int u,v,w,cnt=0,ans=0;
n=read(),m=read();
for(int i=1;i<=m;i++){
u=read();
v=read();
w=read();
add(u,v,w);
add(v,u,w);
}
for(int i=1;i<=n;i++)
dis[i]=0x3f3f3f3f;
q.push((node){1,0});
while(!q.empty()||cnt<n-1){
node t=q.top();
q.pop();
u=t.id;
if(vis[u])
continue;
vis[u]=1;
ans+=t.dist;
cnt++;
for(v=head[u];v;v=e[v].nxt){
if(e[v].w<dis[e[v].to]){
dis[e[v].to]=e[v].w;
q.push((node){e[v].to,e[v].w});
}
}
}
if(cnt<n-1)
printf("orz");
else
cout<<ans;
return 0;
}
by jimmy0926 @ 2024-08-01 16:54:08
@julihui325 最后一个点是 orz。
by jimmy0926 @ 2024-08-01 16:55:42
图不一定是连通图 + priority_queue 常数不小
by jimmy0926 @ 2024-08-01 16:56:53
我不太看得懂你的代码
by jimmy0926 @ 2024-08-01 16:57:49
加点注释吧。
我喜欢用 Kruskal。
by qazsedcrfvgyhnujijn @ 2024-08-01 17:00:32
先判图是否连通
好像 kruskal 在不连通图会输出错误结果,而 prim 会 TLE
by jimmy0926 @ 2024-08-01 17:01:01
&您的
by jimmy0926 @ 2024-08-01 17:02:08
球关
验证码 ak9f 祭
by jimmy0926 @ 2024-08-01 17:08:00
您也可以改用 Kruskal。给一份板子呆码
#include <bits/stdc++.h>
#define made_by_jimmy0926 return 0
typedef long long ll;
int n, m, ptr;
ll ans;
int h[5001], f[5001];
struct Edge {
int start;
int to;
int val;
bool operator < (const Edge x) const {
return val < x.val;
}
} eg[200001];
void init() {
std::sort(eg + 1, eg + 1 + m);
for (int i = 1; i <= n; ++i) {
f[i] = i;
h[i] = 1;
}
}
int find(int x) {
if (f[x] == x)
return x;
return f[x] = find(f[x]);
}
inline void merge(int u, int v) {
u = find(u), v = find(v);
if (h[u] < h[v])
std::swap(u, v);
if (u != v) {
f[v] = u;
h[u] += (h[u] == h[v]);
}
}
bool isdiff(int u, int v) {
return find(u) != find(v);
}
inline bool judge() {
for (int i = 2; i <= n; ++i)
if (find(f[i]) != find(f[i - 1]))
return false;
return true;
}
bool kruskal() {
if (m < n - 1)
return false;
init();
int cnt = 0;
for (int i = 1; i <= m && cnt < n - 1; ++i)
if (isdiff(eg[i].start, eg[i].to)) {
// printf("choose : %d %d %d\n", eg[i].start, eg[i].to, eg[i].val);
++cnt;
ans += eg[i].val;
merge(eg[i].start, eg[i].to);
}
if (cnt < n - 1)
return false;
// printf("judging.\n");
return judge();
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
eg[++ptr] = {u, v, w};
}
bool ok = kruskal();
if (!ok)
printf("orz");
else
printf("%lld", ans);
made_by_jimmy0926;
}
较优解至少比一大群面向数据编程的【数据删除】要好
by julihui325 @ 2024-08-01 17:19:18
@jimmy0926 笑点解析:kruskal刚调完,20分钟,prim两小时hhh&已关
by julihui325 @ 2024-08-01 17:19:55
@qazsedcrfvgyhnujijn 谢谢大佬,已关