HDU 1102(最小生成树)

2024-09-01 05:08
文章标签 最小 生成 hdu 1102

本文主要是介绍HDU 1102(最小生成树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:给一个图,以及已知一些边已经存在,求除了给出的这些边,至少需要多长的边才能使所有结点相连接。

 

kruskal:

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct edge
{
int u, v, w;
edge() {}
edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
bool operator <(const edge& rhs) const
{
return w > rhs.w;
}
};
int map[101][101];
int set[101];
int find(int x)
{
return set[x] == -1 ? x : set[x] = find(set[x]);
}
int kruskal(int n)
{
priority_queue<edge> q;
int ans = 0, i, j;
for (i = 1; i <= n; ++i)
for (j = 1; j < i; ++j)
q.push(edge(i, j, map[i][j]));
while (!q.empty())
{
edge p = q.top(); q.pop();
int x = find(p.u), y = find(p.v);
if (x != y) set[x] = y, ans += p.w;
}
return ans;
}
int main()
{
int n, q, i, j;
while (scanf("%d", &n) != EOF)
{
memset(set, -1, sizeof set);
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
{
scanf("%d", &map[i][j]);
map[j][i] = map[i][j];
}
scanf("%d", &q);
while (q--)
{
scanf("%d%d", &i, &j);
map[i][j] = map[j][i] = 0;
}
printf("%d\n", kruskal(n));
}
}


prim:

#include <cstdio>
#include <cstring>
#include <queue>
#include <climits>
using namespace std;
struct edge
{
int u, v, w;
edge() {}
edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
bool operator <(const edge& rhs) const
{
return w > rhs.w;
}
};
int map[101][101];
/*
int prim(int n)
{
int i;
bool visited[101];
int distance[101];
memset(visited, false, sizeof visited);
for (i = 1; i <= n; ++i) distance[i] = INT_MAX;
int v = 1, dist;
distance[v] = 0;
int sum = 0;
while (visited[v] == false)
{
visited[v] = true;
sum += distance[v];
for (i = 1; i <= n; ++i)
if (visited[i] == false && map[v][i] < distance[i])
distance[i] = map[v][i];
dist = INT_MAX;
for (i = 1; i <= n; ++i)
if (visited[i] == false && dist > distance[i])
{
dist = distance[i];
v = i;
}
}
return sum;
}
*/
int prim(int n)
{
bool visited[101];
memset(visited, false, sizeof visited);
visited[1] = true;
int i, sum = 0, j, flag, min;
for (i = 1; i < n; ++i)
{
min = INT_MAX;
for (j = 1; j <= n; ++j)
if (!visited[j] && map[1][j] < min)
{
min = map[1][j];
flag = j;
}
visited[flag] = true;
sum += map[1][flag];
for (j = 1; j <= n; ++j)
if (!visited[j] && map[1][j] > map[flag][j])
map[1][j] = map[flag][j];
}
return sum;
}
int main()
{
int n, q, i, j;
while (scanf("%d", &n) != EOF)
{
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
{
scanf("%d", &map[i][j]);
map[j][i] = map[i][j];
}
scanf("%d", &q);
while (q--)
{
scanf("%d%d", &i, &j);
map[i][j] = map[j][i] = 0;
}
printf("%d\n", prim(n));
}
}


 

这篇关于HDU 1102(最小生成树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1126024

相关文章

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人,是不是经常需要制作各种PPT来分享我的生活和想法。但是,你们知道,有时候灵感来了,时间却不够用了!😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手!🌟 什么是Kimi? 一款月之暗面科技有限公司开发的AI办公工具,帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师,Kimi都能够为你的办公文

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :