poj 2560 Freckles

题目连接

http://poj.org/problem?id=2560

Freckles

Description

In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad‘s back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley‘s engagement falls through. 
Consider Dick‘s back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.

Input

The first line contains 0 < n <= 100, the number of freckles on Dick‘s back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle.

Output

Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.

Sample Input

3
1.0 1.0
2.0 2.0
2.0 4.0

Sample Output

3.41
$n$个点用$Prim$求最小生成树,开始用的$double$类型$\%lf$控制精度$g++$不停地wa后改为$float,\%f$过了/(ㄒoㄒ)/~~

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
using std::set;
using std::pair;
using std::swap;
using std::multiset;
using std::priority_queue;
#define pb(e) push_back(e)
#define sz(c) (int)(c).size()
#define mp(a, b) make_pair(a, b)
#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cls(arr, val) memset(arr, val, sizeof(arr))
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define tr(c, i) for(iter(c) i = (c).begin(); i != (c).end(); ++i)
const int N = 110;
const int INF = 0x3f3f3f3f;
typedef unsigned long long ull;
struct P {
	float x, y;
	P(float i = 0.0, float j = 0.0) :x(i), y(j) {}
	inline float calc(const P &k) const {
		return sqrt((x - k.x) * (x - k.x) + (y - k.y) * (y - k.y));
	}
}A[N];
struct PDI {
	int v;
	float s;
	PDI(int i = 0, float j = 0.0) :v(i), s(j) {}
	inline bool operator<(const PDI &k) const {
		return s > k.s;
	}
};
struct Prim {
	bool vis[N];
	int tot, head[N];
	float mincost[N];
	struct edge { int to; float w; int next; }G[(N * N) << 1];
	inline void init(int n) {
		tot = 0;
		rep(i, n + 1) {
			head[i] = -1;
			vis[i] = false;
			mincost[i] = INF;
		}
	}
	inline void add_edge(int u, int v, float w) {
		G[tot] = (edge){ v, w, head[u] }; head[u] = tot++;
	}
	inline void built(int n) {
		rep(i, n) scanf("%f %f", &A[i].x, &A[i].y);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j) continue;
				add_edge(i + 1, j + 1, A[i].calc(A[j]));
			}
		}
	}
	inline void prim(int s = 1) {
		float ans = 0.0;
		priority_queue<PDI> q;
		q.push(PDI(s));
		for (int i = head[s]; ~i; i = G[i].next) {
			edge &e = G[i];
			q.push(PDI(e.to, mincost[e.to] = e.w));
		}
		vis[s] = true;
		while (!q.empty()) {
			PDI t = q.top(); q.pop();
			int u = t.v;
			if (vis[u]) continue;
			vis[u] = true;
			ans += mincost[u];
			for (int i = head[u]; ~i; i = G[i].next) {
				edge &e = G[i];
				if (mincost[e.to] > e.w && !vis[e.to]) {
					q.push(PDI(e.to, mincost[e.to] = e.w));
				}
			}
		}
		printf("%.2f\n", ans);
	}
	inline void solve(int n) {
		init(n), built(n), prim();
	}
}go;
int main() {
#ifdef LOCAL
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w+", stdout);
#endif
	int n;
	while (~scanf("%d", &n)) {
		go.solve(n);
	}
	return 0;
}
时间: 09-02

poj 2560 Freckles的相关文章

POJ 2560 Freckles Prime算法题解

本题是求最小生成树. 给出的是坐标节点,然后需要根据这些坐标计算出各个点之间的距离. 除此就是标准的Prime算法了,能使用Prime的基本上都可以使用Kruskal. 这些经典的算法一定要多写,熟练掌握,否则很难灵活运用的. 而且经典的算法之所以为经典,原因之一是没那么容易自己凭空想象出来的,所以要熟练. #include <stdio.h> #include <string.h> #include <queue> #include <float.h> #

POJ 2560 Freckles(最小生成树)

原题地址:http://poj.org/problem?id=2560 Freckles Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 7863   Accepted: 3776 Description In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a pictu

POJ 2560 Freckles Prime问题解决算法

这个问题正在寻求最小生成树. 给定节点的坐标,那么我们需要根据各个点之间的这些坐标来计算距离. 除了这是标准的Prime算法的,能源利用Prime基本上,你可以使用Kruskal. 经典的算法必须填写,熟练度.否则它是非常困难的利用. 并且经典的算法之所以为经典.原因之中的一个是没那么easy自己凭空想象出来的,所以要熟练. #include <stdio.h> #include <string.h> #include <queue> #include <floa

Poj(2560),最小生成树,Prim

题目链接:http://poj.org/problem?id=2560 只想说“全都是套路”,关键建图. #include <stdio.h> #include <string.h> #include <math.h> #define INF 0x3f3f3f3f int n; double maps[300][300]; bool vis[300]; double dis[300]; struct Point { double x; double y; }points

POJ 2560

1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 #include<iomanip> 5 #define MAXN 105 6 #define inf 1000000000 7 using namespace std; 8 9 typedef double elem_t; 10 11 double point[MAXN][2]; 12 double _m[MAXN][MAXN]; 1

图论 500题——主要为hdu/poj/zoj

转自——http://blog.csdn.net/qwe20060514/article/details/8112550 =============================以下是最小生成树+并查集======================================[HDU]1213   How Many Tables   基础并查集★1272   小希的迷宫   基础并查集★1325&&poj1308  Is It A Tree?   基础并查集★1856   More i

POJ 1135.Domino Effect

Domino Effect Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 10325   Accepted: 2560 Description Did you know that you can use domino bones for other things besides playing Dominoes? Take a number of dominoes and build a row by standing

POJ 2355 Find a multiple(组合数学-抽屉原理)

Find a multiple Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 5881   Accepted: 2560   Special Judge Description The input contains N natural (i.e. positive integer) numbers ( N <= 10000 ). Each of that numbers is not greater than 15000

POJ - 3186 Treats for the Cows (区间DP)

题目链接:http://poj.org/problem?id=3186 题意:给定一组序列,取n次,每次可以取序列最前面的数或最后面的数,第n次出来就乘n,然后求和的最大值. 题解:用dp[i][j]表示i~j区间和的最大值,然后根据这个状态可以从删前和删后转移过来,推出状态转移方程: dp[i][j]=max(dp[i+1][j]+value[i]*k,dp[i][j-1]+value[j]*k) 1 #include <iostream> 2 #include <algorithm&