Submission #2072929

---

Source Code Expand

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
using namespace std;
#define SIZE 20
class unionfind
{
public:
	int par[SIZE];
	int ran[SIZE];
	int ren[SIZE];
	void init()
	{
		for (int i = 0; i<SIZE; i++)
		{
			par[i] = i;
			ran[i] = 0;
			ren[i] = 1;
		}
	}
	int find(int a)
	{
		if (a == par[a])return a;
		else return par[a] = find(par[a]);
	}
	void unite(int a, int b)
	{
		a = find(a);
		b = find(b);
		if (a == b)return;
		if (ran[a]>ran[b])
		{
			par[b] = a;
			ren[a] += ren[b];
		}
		else
		{
			par[a] = b;
			ren[b] += ren[a];
		}
		if (ran[a] == ran[b])ran[b]++;
	}
};
unionfind uf[1 << 15];
double cst[1 << 15];
double x[15], y[15], a[15];
double dp[1 << 15];
typedef pair<int, int>pii;
typedef pair<double, pii>pdi;
int main()
{
	int num;
	scanf("%d", &num);
	for (int i = 0; i < num; i++)scanf("%lf%lf%lf", &x[i], &y[i], &a[i]);
	vector<pdi>v;
	for (int i = 0; i < num; i++)for (int j = i + 1; j < num; j++)v.push_back(make_pair(sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j])), make_pair(i, j)));
	sort(v.begin(), v.end());
	for (int i = 0; i < (1 << num); i++)uf[i].init();
	for (int i = 0; i < v.size(); i++)
	{
		int s = v[i].second.first, t = v[i].second.second;
		double d = v[i].first;
		for (int p = 0; p < (1 << num); p++)
		{
			if ((p&(1 << s)) != 0 && (p&(1 << t)) != 0)
			{
				if (uf[p].find(s) != uf[p].find(t))
				{
					cst[p] -= d;
					uf[p].unite(s, t);
				}
			}
		}
	}
	for (int p = 1; p < (1 << num); p++)
	{
		int cnt = 0;
		for (int i = 0; i < num; i++)if (p&(1 << i))cst[p] += a[i], cnt++;
		cst[p] /= cnt;
	}
	dp[0] = 1000000000000000000.0;
	for (int p = 0; p < (1 << num); p++)
	{
		int mask = (1 << num) - 1 - p;
		int now = mask;
		for (;;)
		{
			if (now == 0)break;
			dp[p + now] = max(dp[p + now], min(dp[p], cst[now]));
			now--;
			now &= mask;
		}
	}
	printf("%.20lf\n", dp[(1 << num) - 1]);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:55:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &num);
                   ^
./Main.cpp:56:70: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < num; i++)scanf("%lf%lf%lf", &x[i], &y[i], &a[i]);
                                                                      ^

Judge Result