讨论 / 犇犇的搜狗输入法,比其他蒟蒻输入法好多了.
sgzxfjh 2019-12-22 15:31:03
点我顶贴 收藏 删除
(づ ̄3 ̄)づ╭❤~

(@o@)…

_(:з」∠)_

\(^o^)/~

ლ(′◉❥◉`ლ)

#1 sgzxfjh@2019-12-22 15:31:13
回复 删除
什么玩意儿

#2 1支1cc的肾上腺素@2020-05-05 15:13:00
回复 删除
Win10:蛤?(ノ`Д)ノ
#3 不会编程@2020-05-07 17:39:48
回复 删除
?????????
#4 Coin1234@2020-07-04 17:50:41
回复 删除
Kruskal

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=1005;

int n,m,ans;

int fa[maxn];

struct edge{

int x,y,v;

}e[maxn*maxn];

int find(int x) //查找父亲节点

{

if(fa[x]==x) return x;

return fa[x]=find(fa[x]);

}

bool cmp(struct edge a,struct edge b)

{

return a.v<b.v;

}

void kruskall()

{

int cnt=0;

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(cnt==n-1) break;

int fx=find(e[i].x);

int fy=find(e[i].y);

if(fx!=fy)

{

fa[fx]=fy; //合并两棵树

cnt++;

ans+=e[i].v;

}

}

printf("%d",ans);

}

int main()

{

int x,y,a;

scanf("%d%d",&n,&m);

for(int i=1;i<=m;i++)

{

scanf("%d%d%d",&x,&y,&a);

e[i].x=x;

e[i].y=y;

e[i].v=a;

}

kruskall();

return 0;

}

Prim

#include<cstdio>

#include<cstring>

#include<algorithm>

#define inf 0x3f3f3f3f

using namespace std;

const int maxn=1005;

int n,m,ans,cnt=1;

int fa[maxn],head[maxn],dis[maxn],vis[maxn];

struct edge{

int x,y,v,next;

}e[maxn*maxn];

void addedge(int x,int y,int a)//邻接矩阵

{

e[cnt].x=x;

e[cnt].y=y;

e[cnt].v=a;

e[cnt].next=head[x];

head[x]=cnt++;

}

void primm()

{

int mi;

memset(dis,inf,sizeof(dis));

dis[1]=0;

int u;

for(int i=1;i<=n;i++)

{

mi=inf;

for(int j=1;j<=n;j++)

if(!vis[j]&&mi>dis[j])

{

mi=dis[j];u=j;

}

vis[u]=1;

ans+=mi;

for(int k=head[u];k!=-1;k=e[k].next)

{

if(dis[e[k].y]>e[k].v)

dis[e[k].y]=e[k].v;

}

}

printf("%d",ans);

}

int main()

{

int x,y,a;

scanf("%d%d",&n,&m);

memset(head,-1,sizeof(head));

for(int i=1;i<=m;i++)

{

scanf("%d%d%d",&x,&y,&a);

addedge(x,y,a);

addedge(y,x,a);

}

primm();

return 0;

}

#5 Coin1234@2020-07-04 17:50:59
回复 删除
Prim

#include<cstdio>

#include<cstring>

#include<algorithm>

#define inf 0x3f3f3f3f

using namespace std;

const int maxn=1005;

int n

,m,ans,cnt=1;

int fa[maxn],head[maxn],dis[maxn],vis[maxn];

struct edge{

int x,y,v,next;

}e[maxn*maxn];

void addedge(int x,int y,int a)//邻接矩阵

{

e[cnt].x=x;

e[cnt].y=y;

e[cnt].v=a;

e[cnt].next=head[x];

head[x]=cnt++;

}

void primm()

{

int mi;

memset(dis,inf,sizeof(dis));

dis[1]=0;

int u;

for(int i=1;i<=n;i++)

{

mi=inf;

for(int j=1;j<=n;j++)

if(!vis[j]&&mi>dis[j])

{

mi=dis[j];u=j;

}

vis[u]=1;

ans+=mi;

for(int k=head[u];k!=-1;k=e[k].next)

{

if(dis[e[k].y]>e[k].v)

dis[e[k].y]=e[k].v;

}

}

printf("%d",ans);

}

int main()

{

int x,y,a;

scanf("%d%d",&n,&m);

memset(head,-1,sizeof(head));

for(int i=1;i<=m;i++)

{

scanf("%d%d%d",&x,&y,&a);

addedge(x,y,a);

addedge(y,x,a);

}

primm();

return 0;

}

查看更多回复
提交回复