题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
//思路:每次找到d最小的一个点放入集合,用该点去更新与该点有连边的,
//没连边的无影响
//点a到集合的距离d:点a与集合中所有点之间的连边的min
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10, INF = 0x3f3f3f3f;
int d[N], w[N];
int n, m;
bool vis[N];
int ne[N], e[N], idx, h[N];
void add(int a, int b, int c)//建图
{
e[idx] = b, w[idx] = c, ne[idx] = h[a];
h[a] = idx;
idx++;
}
int prim()
{
memset(d, 0x3f, sizeof(d));
int res = 0;
d[1]=0;
for (int i = 0; i < n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
{
if (!vis[j] && (t == -1 || d[j] < d[t]))
t = j;
}//找点
if (i && d[t] == INF)//至少有一个不联通
return INF;
if (i)
res += d[t];
vis[t] = true;
for (int i = h[t]; i != -1; i = ne[i])//找t的连边
{
int j = e[i];
d[j] = min(d[j], w[i]);
}
}
return res;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);//这里也可以用邻接矩阵
add(b, a, c);
}
int t = prim();//不能直接prim(),因为会进行两次prime();
if (t == INF)
cout << "impossible" << endl;
else
cout << t << endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla