清爽kruskal链表插入排序MLE求调
查看原帖
清爽kruskal链表插入排序MLE求调
1122193
FarmerDrone楼主2024/4/12 22:10

是复杂度不行吗?

#include <bits/stdc++.h>
using namespace std;

int father[220];

class SIDE
{
public:
	int u;
	int v;
	int w;
};

inline bool cmp(SIDE a, SIDE b)
{
	return a.w < b.w;
}

int find(int x)
{
	if (father[x] == x)
		return x;
	else
		return father[x] = find(father[x]);
}

int main()
{
	int n, m, cnt;
	long long ans;
	cin >> n >> m;
	list <SIDE> side;
	SIDE a;
	list <SIDE> ::iterator it;	
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &a.u, &a.v, &a.w);
		cnt = 0, ans = 0;
		for (it = side.begin(); it != side.end(); it++)
			if (cmp(a, *it))
				side.insert(it, a);
		if (side.size() < i)
			side.push_back(a);
		for (int j = 1; j <= n; j++)
			father[j] = j;
		it = side.begin();
		while (cnt < n - 1)
		{
			if (it == side.end())
			{
				cout << "-1\n";
				goto f1;
			}
			if (find(it->u) == find(it->v))
			{
				it++;
				continue;
			}
			ans += it->w;
			cnt++;
			father[find(it->u)] = find(it->v);
			it++;
		}
		cout << ans << "\n";
		f1:;
	}
	return 0;	
}
2024/4/12 22:10
加载中...