（图论）51NOD 1212 无向图最小生成树
2024-08-26 09:42:38
N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。
输入
第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000)
第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)
输出
输出最小生成树的所有边的权值之和。
输入样例
9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8
输出样例
37
解:Kruskal算法（排序后添加边）的两种实现（时间消耗差不多）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h> typedef struct Graph
{
int s,e,w;
}graph; int cmp(const void *a,const void *b)
{
return (*(graph *)a).w>(*(graph *)b).w?:-;
} graph p[];
int vis[]; int main()
{
int n,m;
while(scanf_s("%d%d",&n,&m)!=EOF)
{
int i,j,ans=;
memset(vis,,n);
for(i=;i<m;i++) scanf_s("%d%d%d",&p[i].s,&p[i].e,&p[i].w);
qsort(p,m,sizeof(graph),cmp);
vis[p[].s]=;
vis[p[].e]=;
ans+=p[].w;
for(i=;i<n-;i++)
{
for(j=;j<m;j++)
{
if((vis[p[j].s]==&&vis[p[j].e]==)||(vis[p[j].s]&&vis[p[j].e]))
continue;
else
{
vis[p[j].s]=;
vis[p[j].e]=;
ans+=p[j].w;
break;
}
}
}
printf("%d\n",ans);
}
return ;
}
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h> typedef struct GRAPH
{
int s, e, w;
}graph; int cmp(const void *a, const void *b)
{
return ((graph *)a)->w > ((graph *)b)->w ? : -;
} graph p[];
int *vis[]; int main()
{
int n, m;
while (scanf_s("%d%d", &n, &m) != EOF)
{
int ans = ;
for (int i = ; i < m; ++i) scanf_s("%d%d%d", &p[i].s, &p[i].e, &p[i].w);
qsort(p, m, sizeof(graph), cmp);
for (int i = , j = ; i < m; ++i)
{
int *tmp = (int *)malloc(sizeof(int));
if (vis[p[i].e] == NULL)
{
if (vis[p[i].s] == NULL)
{
*tmp = j++;
vis[p[i].e] = vis[p[i].s] = tmp;
}
else
{
vis[p[i].e] = vis[p[i].s];
free(tmp);
}
}
else if (vis[p[i].s] == NULL)
{
vis[p[i].s] = vis[p[i].e];
free(tmp);
}
else
{
int *a, *b;
for (a = vis[p[i].s]; *a > ; a = *a);
for (b = vis[p[i].e]; *b > ; b = *b);
if (*a == *b)
{
free(tmp);
continue;
}
else
{
*tmp = *a;
*b = *a = tmp;
}
}
ans += p[i].w;
}
printf("%d\n", ans);
}
}
Prim算法（排序后添加点）（写的不好，时间消耗比上面的长）：
#include <stdio.h>
#include <malloc.h>
#include <string.h> #define MIN(a,b) (pt[a]->pr<pt[b]->pr?a:b) typedef struct POINT
{
struct POINT *p;
int ed,pr;
}point; point *pt[];
int vis[][];
int main()
{
int n, m;
while (scanf_s("%d%d", &n, &m) != EOF)
{
int ans = ;
while (m--)
{
int a, b, c;
scanf_s("%d%d%d", &a, &b, &c);
point *tmp1 = (point *)malloc(sizeof(point)), *tmp2 = (point *)malloc(sizeof(point));
tmp1->ed = b;
tmp2->ed = a;
tmp1->pr = tmp2->pr = c;
if (pt[a] == NULL|| tmp1->pr < pt[a]->pr)
{
tmp1->p = pt[a];
pt[a] = tmp1;
}
else for (point *tmp0 = pt[a], *tmp = pt[a]; tmp0 != NULL; tmp = tmp->p)
{
if (tmp == NULL||tmp1->pr < tmp->pr)
{
tmp1->p = tmp0->p;
tmp0->p = tmp1;
break;
}
tmp0 = tmp;
}
if (pt[b] == NULL || tmp2->pr < pt[b]->pr)
{
tmp2->p = pt[b];
pt[b] = tmp2;
}
else for (point *tmp0 = pt[a], *tmp = pt[b]; tmp0 != NULL; tmp = tmp->p)
{
if (tmp == NULL || tmp2->pr < tmp->pr)
{
tmp2->p = tmp0->p;
tmp0->p = tmp2;
break;
}
tmp0 = tmp;
}
}
vis[][] = ;
vis[][] = ;
for (int i = ; i < n; i++)
{
int tmp = ;
for (int j = ; j <= i; j++)
{
if (pt[vis[][j]] == NULL) continue;
else if(vis[][pt[vis[][j]]->ed]!=)
{
if ( == tmp) tmp = vis[][j];
else tmp = MIN(tmp, vis[][j]);
}
else
{
pt[vis[][j]] = pt[vis[][j]]->p;
j--;
}
}
vis[][i+] = pt[tmp]->ed;
vis[][pt[tmp]->ed] = ;
ans += pt[tmp]->pr;
pt[tmp] = pt[tmp]->p;
}
printf("%d\n", ans);
}
}
最新文章
- 关于POI解析Excel文件（03和07版本不同）的问题
- C#中属性与字段的用法
- dropdownlist分页
- 03_MySQL中文乱码处理_02_确保MySQL插入数据不乱码的解决方法
- iOS程序的完整启动过程（有storyboard）
- 日期、时间选择器（DatePicker和TimePicker）的功能与用法
- css3hover效果
- asp.net core 2.0 Microsoft.Extensions.Logging 文本文件日志扩展
- ORA-01940: cannot drop a user that is currently connected解决方法
- socketpair创建双向通信的管道（全双工通信）
- net core体系-web应用程序-4asp.net core2.0 项目实战（1）-5项目数据库操作封装操作-EF框架
- 关于esp32的系统初始化启动过程及设计学习方法
- 大数据时代的Python金融应用-Day1-Python与金融应用概述
- @Builder与@NoArgsConstructor | Lombok
- TZOJ 4912 炮兵阵地(状压dp)
- spring + mybatis合集
- Kubernetes init container
- [CodeForces]CodeForces - 1025F Disjoint Triangles
- 登录验证码的生成Java代码
- Javascript 模块化指北