求大佬解答
查看原帖
求大佬解答
546477
DESCENDANTSOFDRAGON楼主2023/5/16 22:04

P1194 为什么样例的第二个就卡住了

#include<bits/stdc++.h>
#define maxn 2000005
using namespace std;
struct node{
    int x, y, z;
} edge[maxn];
int fa[maxn];
int ans;
int cnt;
int a, b;
int now = 0;
int find(int x)
{
    return fa[x] == x ? fa[x] : (fa[x] = find(fa[x]));
}
bool cmp(node a,node b)
{
    return a.z < b.z;
}
void kruskal()
{
    sort(edge + 1, edge + now + 1, cmp);
	for (int i = 1; i <= now && cnt<=b; i++)
		if(find(edge[i].x) != find(edge[i].y))
		{
        	fa[find(edge[i].x)] = find(edge[i].y);
			ans += edge[i].z;
			cnt++;
			if(cnt>=b-1)
				break;
		}
}
int main (){
	cin >> a >> b;
	for (int i = 0; i <= b; i++)
        fa[i] = i;
	for (int i = 1; i <= b; i++)
	{
		for (int j = 1; j <= b; j++)
		{
			int az;
			cin >> az;
			if(j>i && az!=0)
			{
				now++;
				i = edge[i].x;
				j = edge[i].y;
				az = edge[i].z;
			}
		}
	}
	for (int i = 1; i <= b; i++)
	{
		now++;
		edge[now].x = 0;
		edge[now].y = i;
		edge[now].z = a;
	}
	kruskal();
	cout << ans << endl;
	system("pause"); 
    return 0;
}
2023/5/16 22:04
加载中...