浙江财经大学
信工学院ACM集训队

ECNU 3247 铁路修复计划

本文由 Ocrosoft 于 2017-05-13 19:52:09 发表

铁路修复计划

Time limit per test: 2.0 seconds

Time limit all tests: 15.0 seconds

Memory limit: 256 megabytes

在 A 国有很多城际铁路。这些铁路都连接两个城市(城市从 1 到 n 编号),可以双向通行,使得任意两个城市之间都由铁路网联系起来。

不过在一次星球大战之后,所有的铁路都经历了不同程度的损伤以至于无法通行了。由于经费紧缺,A 国政府不愿意再出资造新的铁路。对于原有的城际铁路,根据铁路的实际情况,有以下两种处理办法:

  1. 使用国内技术进行修复:主要针对损坏情况不是很严重的铁路。国内公司会对铁路状况进行评估,然后如实开出铁路修复的费用。
  2. 使用国外技术进行修复:主要针对损坏情况严重的铁路。国外公司也会对铁路情况进行评估,然后按照铁路实际修复费用的 k 倍来收费(其中 k 是一个由国外公司决定的实数,不管怎么说,优惠是不可能的,所以 k≥1)。

A国政府修复铁路的总预算是 M,目标是要让任意两个城市之间都能通过铁路联系起来。在预算不够且能够完成目标的条件下,显然没必要修复每一条铁路。

国外公司通过不知什么途径了解到了 A 国政府的总预算 M,他们现在要把 k 定下来,并且希望 k 尽可能得大。但 k又不能太大,不然,如果 A 国政府发现无法完成任务的话,整个订单都会泡汤。

Input

测试数据包含不超过 30 个测试文件。每个测试文件是单个测试点。

第一行是三个整数 n,m,M (2≤n≤105,n−1≤m≤min{105,n(n−1)2},1≤M≤1015)。

接下来 m 行,每行四个整数 ui,vi,ti,fi。表示一条城际铁路,连接着 ui 和 vi 城市,ti 表示铁路实际修复费用。fi=1 表示只能由国外公司修复,fi=0 表示由国内公司修复。(1≤ui,vi≤n,ui≠vi,1≤ti≤106,fi∈{0,1})。输入保证两个城市之间不会存在多条铁路。

输入保证:

  • 在国外公司不乱收费 (k=1) 的情况下,使用预算能完成要求。
  • 完全不使用国外技术,只使用国内技术,是不能完成目标的。

Output

求 k 的最大值。输出答案与标准答案相差不超过 10−6 即判为正确。

Examples

input
3 3 9
1 2 1 1
1 3 2 0
2 3 1 1

output
7.000000

input
3 3 9
1 2 1 1
1 3 2 1
2 3 2 1

output
3.000000

Source

2017 华东师范大学网赛

Solution:

首先挺神奇的,数据组数并不多,用cin读取n,m,M(后面的数据用scanf)就会超时,而取消stdin同步之后,变成了WA。全部用scanf的时候12s-13s。

官方题解:二分k,然后每次对边重新赋值排序后,就是经典的 MST 问题了。

k最大也是1e15,所以[1,1e15]二分k,对每个k,重新计算每条边的价值,并排序,接着Kruskal。

#include <set>
#include <list>
#include <map>
#include <ratio>
#include <stack>
#include <regex>
#include <ctime>
#include <string>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <sstream>
#include <numeric>
#include <iostream>
#include <complex>
#include <algorithm>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define ms(a) memset(a,0,sizeof(a))
#define rep(a,v,b) for(int a=v;a<b;a++)
#define repe(a,v,b) for(int a=v;a<=b;a++)
#define tp(_pair_or_tuple,_index) get<_index>(_pair_or_tuple)
typedef long long LL;
const LL LINF = LLONG_MAX;
const int INF = INT_MAX;
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-7;
const double PI = acos(-1.0);
using namespace std;
template <typename T>
T GCD(T a, T b)
{
	if (!b)return a;
	return GCD(b, a%b);
}
template <typename T>
T LCM(T a, T b)
{
	return a*b / GCD(a, b);
}

struct edge { int u, v, tw, f; double w; } edges[MAXN];
int n, m, cnt;
double M, sum;
int pre[MAXN];
inline void init() { for (int i = 1; i <= n; i++)pre[i] = i; }
inline bool cmp(edge a, edge b) { return a.w < b.w; }
int find(int x)
{
	if (pre[x] != x)pre[x] = find(pre[x]);
	return pre[x];
}
bool Union(int x, int y)
{
	int fx = find(x), fy = find(y);
	if (fx == fy)return false;
	pre[fx] = fy;
	return true;
}
int main()
{
	scanf("%d%d%lf", &n, &m, &M);
	//cin>>n>>m>>M;
	for (int i = 1; i <= m; i++) scanf("%d%d%d%d", &edges[i].u, &edges[i].v, &edges[i].tw, &edges[i].f);
	double l = 0, r = 1e15 + 10, mid;
	while (r - l > eps)
	{
		mid = l + (r - l) / 2;
		for (int i = 1; i <= m; i++)
		{
			if (edges[i].f)edges[i].w = 1.0*edges[i].tw*mid;
			else edges[i].w = 1.0*edges[i].tw;
		}
		sum = 0; cnt = 0; init();
		sort(edges + 1, edges + m + 1, cmp);
		for (int i = 1; i <= m; i++)
		{
			if (Union(edges[i].u, edges[i].v))
			{
				sum += edges[i].w;
				if (++cnt == n - 1)break;
			}
		}
		if (sum > M)r = mid;
		else l = mid;
	}
	printf("%.6lf\n", l);
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » ECNU 3247 铁路修复计划

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址