kruscal 50pts WA求助
查看原帖
kruscal 50pts WA求助
472650
Kirito_Chen楼主2022/4/23 18:09

代码如下:

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>		
#include <vector>		
#include <queue>		
#include <string>
#include <cstring>      
#include <map>			
#include <stack>		
#include <set>			
#define p pair<int, int>
using namespace std;
const int maxn = 10005;
const int maxm = 10005;
struct edge
{
    int x, y;
    double w;
}; 
vector <edge> a;
p tree[maxn];

double cal (p a, p b)
{
	return sqrt(pow(a.first - b.first,2) + pow(a.second - b.second, 2));
}

int f[maxn], jump[maxn];
int n, m, cnt;
double ans = 0;

bool cmp(edge x, edge y)
{
    return x.w < y.w;
}

void init()
{
    for (int i = 0; i <= n; i++)
        f[i] = i;
}

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

void merge(int x, int y, double w)
{
    int fx = find(x);
    int fy = find(y);
    if (fx != fy)
    {
        f[fy] = fx;
        ans = max(ans, w);
        cnt++;
    }
}

int main()
{
    cin >> n;
    // input
    for (int i = 1; i <=n; i++)
    	cin >> jump[i];
    cin>>m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        // cout<<x<<" "<<y<<endl;
        tree[i] = make_pair(x,y);
    }
    for (int i = 1; i <= m-1; i++)
    	for (int j = i + 1; j<=m; j++)
    	{
    		edge cur = {i,j,cal(tree[i], tree[j])};
    		a.push_back(cur);
    	}
    		
    sort(a.begin(), a.end(), cmp);
    // for (edge e : a)
    	// cout<<e.x<<" "<<e.y<<" "<<e.w<<endl;
    //便利一遍边,merge
	init();
	for (int i = 0; i < a.size(); i++)
    {
        merge(a[i].x, a[i].y, a[i].w);
        if (cnt == m - 1)
            break;
    }
	long long ret = 0;
    for (int i = 1; i<=n; i++)
    	if (jump[i] >= ans)
    		ret++;
    cout << ret;
    return 0;
}

这是提交记录

希望神犇帮我看眼哪出问题了,万分感谢

2022/4/23 18:09
加载中...