题目OJ地址:
摘要:
- 时间限制:
- 10000ms 内存限制:
- 128000kB
- 描述: 多年以后,笨笨长大了,成为了电话线布置帅。由于地震使得某市的电话线全部损坏,笨笨是负责接到震中市的负责人、该市周围分布着N(1≤N≤1000)根据1..n顺序编号的废弃的电话线杆,任意两根线杆之间没有电话线连接,一共有p(1≤P≤10000)对电话杆可以拉电话线.其他的由于地震使得无法连接。 第i对电线杆的两个端点分别是ai,bi,它们的距离为li(1≤li≤1000000)。数据中每对(ai,bi)只出现一次。编号为l的电话杆已经接入了全国的电话网络,整个市的电话线全都连到了编号N的电话线杆上。电就是说,笨笨的任务仅仅是找一条将1号和N号电线杆连起来的路径,其余的电话杆并不一定要连入电话网络。 电信公司决定支援灾区免费为此市连接k(0≤k≤n)对由笨笨指定的电话线杆,对于此外的那些电话线,需要为它们付费,总费用决定于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过k对,那么支出为0。 请你计算一下,将电话线引到震中市最少需要在电话线上花多少钱? 【输入】
- 输入文件的第一行包含三个数字n,P,k;
- 第二行到第p+1行,每行分别都为三个整数al,bi,li。
- 【输出】
- 一个整数,表示陔项工程的最小支出,如果不可能完成则输出一1。
- 【样例输入】 5 7 1 1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6 【样例输出】 4 本题应该说还是不难,只是很难写。话说我写了三节晚自习,终于调通了。这也是我第一次写SPFA,之前以为多长的,后来发现其实很短十几行就可以解决。 关于SPFA,参考: 本题的做法是:先SPFA找到起点到终点的最短边数,判断它是否小于k,如果小于就直接输出0,否则开始下面的计算。 我们知道事实上费用为本条路径上第k+1大的边的权。也就是说,如果费用为P,那么路径上一定经过k条权值大于P的边。设s[i]表示到i号节点所需经过的大于P的边的数量的最小值,则可以证明s[i]关于P是单调递减的,故思路就很明显了——二分答案。 二分P,每次SPFA找出到n点所需经过大于P的边的数量的最小值(具体方法和最短路差不多,可以参考代码),然后与k进行比较:如果s[n]>k,说明必须经过大于k条边权大于P的边,即总费用高于P,将P提升;如果s[n]<=k,说明有可能经过小于k条边权小于P的边,即总费用可能小于等于P,将P下调。 应该注意的是之前要先DFS或BFS一遍看看n是否能达到,如果不能直接输出-1。 参考我的代码:
View Code q; 31 while(!q.empty()) q.pop(); 32 q.push(1);mark[1]=1; 33 while(!q.empty()) 34 { 35 int t=q.front(); 36 q.pop(); 37 38 for(int i=0;i
q; 51 while(!q.empty()) q.pop(); 52 q.push(1); 53 for(int i=1;i<=n;i++) 54 val[i]=INF; 55 val[1]=0; 56 57 while(!q.empty()) 58 { 59 int t=q.front(); 60 q.pop(); 61 62 for(int i=0;i 1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 struct node 10 { 11 int val,end; 12 }; 13 14 ifstream fin("phone.in"); 15 ofstream fout("phone.out"); 16 17 #define INF 0x7fffffff 18 19 vector graph[2001]; 20 set se; 21 int val[2001],qual[2001],n,m,whcissb,k,K,mark[2001]; 22 23 inline int min(int a,int b) 24 { 25 return a