AOJ 2224 Save your cat 题解 《挑战程序设计竞赛》

AOJ 2224 Save your cat

拯救猫咪：巫女建了一个魔法阵，由N个魔法桩和连接它们的M条魔法篱笆组成。每个由篱笆形成的圈子都至少困住了一只猫咪，而拆篱笆需要耗费等比例的圣水，求最小花费。

2.5 它们其实都是“图”

最小生成树

水题一道，最大生成树之后，不在树中的边就是要拆的篱笆。

有个小插曲，开始给了#define MAX_N 10000 + 1 ，#define MAX_E 10000 + 1 报WA：

后来一想组合数嘛，#define MAX_E MAX_N * (MAX_N – 1) / 2 

然后就

后来再加大那么一点点：

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <iomanip>
using namespace std;

// 并查集相关数据与算法
#define MAX_N 10000 + 16
int parent[MAX_N];
int height[MAX_N];

void init(const int& n)
{
	for (int i = 0; i < n; ++i)
	{
		parent[i] = i;
		height[i] = 0;
	}
}

int find(const int& x)
{
	if (parent[x] == x)
	{
		return x;
	}
	else
	{
		return parent[x] = find(parent[x]);
	}
}

void unite(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x == y)
	{
		return;
	}

	if (height[x] < height[y])
	{
		parent[x] = y;
	}
	else
	{
		parent[y] = x;
		if (height[x] == height[y])
		{
			++height[x];
		}
	}
}

bool same(const int& x, const int& y)
{
	return find(x) == find(y);
}
// End Of 并查集

#define MAX_E MAX_N * MAX_N / 2 + 1
struct edge
{
	int u, v;
	double cost;
	edge(int u = 0, int v = 0, double cost = 0) : u(u), v(v), cost(cost) {}
	bool operator < (const edge & e2) const
	{
		return cost > e2.cost;
	}
};

edge es[MAX_E];
int V, E;
double kruskal()
{
	sort(es, es + E);    // 按照权值从小到大排序
	init(V);
	double res = 0;
	for (int i = 0; i < E; ++i)
	{
		edge e = es[i];
		if (!same(e.u, e.v))
		{
			unite(e.u, e.v);
		}
		else
		{
			res += e.cost;
		}
	}

	return res;
}

pair<int, int> pile[MAX_N];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	cin >> V >> E;
	
	for (int i = 0; i < V; ++i)
	{
		cin >> pile[i].first >> pile[i].second;
	}

	for (int i = 0; i < E; ++i)
	{
		cin >> es[i].u >> es[i].v;
		--es[i].u; --es[i].v;
		int dx = pile[es[i].u].first - pile[es[i].v].first;
		int dy = pile[es[i].u].second - pile[es[i].v].second;
		es[i].cost = sqrt(dx * dx + dy * dy);
	}

	cout.setf(ios::showpoint);
	cout.precision(3);
	cout.setf(ios::fixed);
	cout << kruskal() << endl;
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

就AC了，看来题目中说的N (2 ≤ N ≤ 10000) 有待商榷。

 知识共享署名-非商业性使用-相同方式共享：码农场 » AOJ 2224 Save your cat 题解 《挑战程序设计竞赛》