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//////////////////////////////////

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