洛谷 P1396

P1396

传送门

扯些题外话

讲真的我刚看到这个题的时候真的傻fufu的.....

大体题意

找出从s走到t的拥挤度最大值最小..

思路

说最大值最小可能就会有dalao开始二分了.

想我这种的蒟蒻只能打一些kruskal维持一下生活...

说正题:因为kruskal的时候先把每一个边的边权排了序，等到什么时候s区与t区在同一个集合里的时候。

那个路径的最大值就是当前连接的最后一条边的边权.

因为kruskal的边权一开始是按大小排序的，那就说明这个最大值一定是各个最大值中最小的那个.

然后就没有然后了..

code

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <cmath>

#include <vector>

#include <cstdio>

#include <string>

#include <cstring>

#include <iomanip>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define N 20010

#define M 10010

using namespace std;

int fath[N], n, m, s, t;

struct node {

	int x, y, dis;

}e[N];

int read() {

    int s = 0, f = 0; char ch = getchar();

    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();

    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();

    return f ? -s : s;

}

bool cmp(node a, node b) {

	return a.dis < b.dis;

}

int father(int x) {

	if (x != fath[x]) fath[x] = father(fath[x]);

	return fath[x];

}

int main() {

	n = read(), m = read(), s = read(), t = read();

	for (int i = 1, u, v, w; i <= m; i++) {

		u = read(), v = read(), w = read();

		e[i].x = u, e[i].y = v, e[i].dis = w;

	}

	for (int i = 1; i <= n; i++) fath[i] = i;

	sort(e + 1, e + m + 1, cmp);

	int ans;

	for (int i = 1; i <= m; i++) {

		int fx = father(e[i].x), fy = father(e[i].y);

		if (fx != fy) {

			fath[fx] = fy;

			ans = e[i].dis;

		}

		if (father(s) == father(t)) break;

	}

	cout << ans;

}