放牧代码和思想
专注自然语言处理、机器学习算法

POJ 3662 Telephone Lines 题解 《挑战程序设计竞赛》

目录

POJ 3662 Telephone Lines

拉电线:N个电线杆P条线可选,K条线内免费,否则花费免费额度外最长的那一根。求最小花费。

3.1不光是查找值!“二分搜索”

最小化第k大的值

Dijkstra结合二分解决,题还行,是谁写了这么蠢的题干,出来我保证不打死你。“the phone company is willing to provide Farmer John with K (0 ≤ K < N) lengths of cable for free.”这句话的正确理解是,K条线免费,长度任意;而不是一条长度为K的电线。这是解题的关键,出题人写完题目没有考虑英语渣渣的感受,length of是一根的意思,lengths of就是复数根的意思……英语渣伤不起

下面看看怎么把它转换成最短路问题:

设mid为某条线的长度,长于mid的线放到免费额度里,否则自己掏钱。如果存在一个临界值x,使得长于x的电线数量恰好等于K,这个临界值对应的解就是最优解。如何计算长于mid的电线数量呢?排序比较肯定不行的,因为不知道这条电线用不用得上。所以需要Dijkstra,又因为在mid固定的条件下,电线的花费只取决于长度是否大于mid,所以可以将大于的取为1,小于的取为0。这样花费就可以计算了,并且花费等于长于mid的电线数量,也就是需要自己掏钱的电线的数量。

二分条件敲定了之后就是普通的二分问题了,假定长度mid以下的都免费,对长度二分。当二分结束的时候,就到达了临界状态“花钱与不花钱的临界”,此状态就是答案了。

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

#define MAX_V 1000 + 16
#define MAX_L 1000000

// 从顶点from指向顶点to的权值为cost的边
struct edge
{
	int to, cost;
	edge(){}
	edge(int to, int cost) : to(to), cost(cost){}
};

// first 最短路径,second顶点编号
typedef pair<int, int> P;

// 边
vector<edge> G[MAX_V];

// 最短距离
int d[MAX_V];
// V是顶点数,E是边数
int V, E;

// 求解从顶点s出发到所有点的最短距离
// x表示x单位之内免费
// 返回需要的电线数量
int dijkstra_ex(int s, int x)
{
	priority_queue<P, vector<P>, greater<P> > que;
	memset(d, 0x3f, V * sizeof(int));
	d[s] = 0;
	que.push(P(0, s));

	while (!que.empty())
	{
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		for (int i = 0; i < G[v].size(); ++i)
		{
			edge e = G[v][i];
			int new_d = d[v] + (e.cost >= x ? 1 : 0);
			if (d[e.to] > new_d)
			{
				d[e.to] = new_d;
				que.push(P(d[e.to], e.to));
			}
		}
	}
	return d[V - 1];
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int K;
	cin >> V >> E >> K;
	for (int i = 0; i < E; ++i)
	{
		int from, to, cost;
		cin >> from >> to >> cost;
		--from;
		--to;
		G[from].push_back(edge(to, cost));
		G[to].push_back(edge(from, cost));
	}
	int lb = 0, ub = MAX_L + 2;
	while (ub - lb > 1)
	{
		int mid = (ub + lb) >> 1;
		if (dijkstra_ex(0, mid) > K)
		{// mid 太取小了
			lb = mid;
		}
		else
		{
			ub = mid;
		}
	}
	cout << (lb > MAX_L ? -1 : lb) << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////
12848537 hankcs 3662 Accepted 516K 297MS C++ 1799B 2014-05-07 14:21:07

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 3662 Telephone Lines 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 2

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #2

    图论弱的一笔

    爱你的龙哥1年前 (2016-04-03)回复
  2. #1

    我去,怪不得我样例手算都算不出!!!

    一根会动的弦2年前 (2015-08-30)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机