[SPFA] [bisection] set up telephone line

LinkLinkLink

luogu P1948luogu\ P1948luogu P1948

DescriptionDescriptionDescription

Farmer John plans to lead the telephone line to his farm, but the telecom company does not intend to provide him with free services. Therefore, FJ must pay a certain fee to the telecom company.
Around the farm of FJ, there are n (1 < = n < = 1000) abandoned telephone lines numbered in order of 1... N
No telephone line is connected between any two telephone line poles. A total of P (1 < = P < = 10000) phone pairs
Telephone lines can be pulled between poles, and the rest cannot be connected because they are too far apart. The two ends of the i-th pair of telephone poles are a respectively_ i,B_ i. The distance between them is L_ i (1 <= L_i <= 1,000,000). Ensure that each pair of {A_i, B_i} only appears once at most in the data. The telephone pole numbered 1 has been connected to the national telephone network, and the telephone lines of the whole farm are all connected to the telephone pole numbered n. In other words, FJ's task is only to find a path to connect telephone poles 1 and N, and the rest of the telephone poles do not have to be connected to the telephone network.
After negotiation, the telecom company finally agreed to connect K (0 < = k < n) to the telephone pole designated by FJ for free. For other telephone lines, FJ needs to pay for them, which is equal to the length of the longest telephone line (each telephone line is connected to only one pair of telephone poles). If there are no more than k pairs of telephone poles to be connected, the total expenditure of FJ is 0.
Please calculate how much FJ needs to spend on the telephone line at least.

InputInputInput

Line 1: 3 integers separated by spaces: N, P, and K
Line 2... P+1: line i+1: three integers separated by spaces: AiA_iAi​,BiB_iBi​,LiL_iLi​

OutputOutputOutput

Line 1: output an integer, which is the minimum expenditure of FJ on this project. If the task cannot be completed, output - 1.

SampleSampleSample InputInputInput

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

SampleSampleSample OutputOutputOutput

4

HintHintHint

Input Description:
There are five abandoned telephone poles. Telephone pole 1 cannot be directly connected to telephone poles 4 and 5. Telephone poles 5 cannot be directly connected to telephone poles 1 and 3. All other telephone poles can be connected with telephone lines. Telecom companies can connect a pair of telephone poles for FJ free of charge.

Output Description:
FJ selects the following connection scheme: 1 - > 3; 3->2; 2 - > 5, the length of telephone lines required between the three pairs of telephone poles is 4, 3 and 9 respectively. FJ asked the telecom company to provide the telephone line with a length of 9, so the maximum length of the telephone line he needs to buy is 4.
Data points 1 ~ 4: n < = 10, P < = 20;
Data points 5 ~ 6: n < = 50, P < = 200;
Data points 7 ~ 9: n < = 1000, P < = 1000;
Data points 10 ~ 11: n < = 1000, P < = 5000;
Data points 12 ~ 13: n < = 1000, P < = 10000;

TrainTrainTrain ofofof ThoughtThoughtThought

We split the money that FJ has to pay for midmidmidmid in the end, so the circuit larger than this midmidmidmid is the circuit we want to connect to the company, so we set the edge weight to 1
Then set the less than to 0, and then run SPFA. If dis [n] dis [n] dis [n] > KKK, it is not feasible, and then just keep scoring two points

CodeCodeCode

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;

int n, t, p, k, flag, ans;
int h[10001], dis[10001], c[10001];

struct node
{
	int to, next, val, q;
}w[20001];

void add(int x, int y, int z)
{
	w[++t] = (node){y, h[x], z, 0}; h[x] = t;
	w[++t] = (node){x, h[y], z, 0}; h[y] = t;
	
}

void spfa()
{
	memset(c, 0, sizeof(c));
	for (int i = 1; i <= n; ++i)
		dis[i] = 1e9;
	dis[1] = 0;
	c[1] = 1;
	queue<int>Q;
	Q.push(1);
	while(Q.size())
	{
		int pq = Q.front();
		Q.pop();
		for (int i = h[pq]; i; i = w[i].next)
		{
			int y = w[i].to;
			if (dis[y] > dis[pq] + w[i].q)
			{
				dis[y] = dis[pq] + w[i].q;
				if (!c[y]) {
					c[y] = 1;
					Q.push(y);
				}
			}
		}
		c[pq] = 0;
	}
}

bool check(int x)
{
	for (int i = 1; i <= t; ++i)
		if (w[i].val > x) w[i].q = 1;
		else w[i].q = 0;
	spfa();
	if (dis[n] == 1e9) flag = 1;
	if (dis[n] <= k) return 1;
	else return 0; 
}

int main()
{
	scanf("%d%d%d", &n, &p, &k);
	for (int i = 1; i <= p; ++i)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}	
	int l = 0, r = 1000000;
	while (l <= r)
	{
		int mid = (l + r) / 2;
		if (check(mid)) r = mid - 1, ans = mid;
		else l = mid + 1;
		if (flag) break;
	}
	if (flag) printf("-1");
	else printf("%d", ans);
}

Tags: Graph Theory Binary Search SPFA

Posted by duclet on Mon, 23 May 2022 10:52:56 +0300