?? zju2281 -- way to freedom(b).cpp
字號:
// PROB Zju Online Judge 2281 -- Way to Freedom
// Algorithm Greedy + Disjoint
// Complexity O (MlogM + Mlog*N)
// Author LoveShsean
// Comment I'm lazy. You can improve this code
// by using heap or sort-divide. :)
#include <stdio.h>
#include <algorithm>
#define maxn 100010
#define maxm 1001000
using namespace std;
int eu [maxm], ev [maxm], ew [maxm], id [maxm], M;
int pnt [maxn], rank [maxn], N;
int src, dst;
bool cmp (const int &x, const int &y)
{
return ew [x] > ew [y];
}
int find (int x)
{
if (pnt [x] != x) pnt [x] = find (pnt [x]);
return pnt [x];
}
int main ()
{
int i, j, x, y;
while (scanf ("%d%d", &N, &M) == 2)
{
for (i = 0; i < M; i ++)
id [i] = i, scanf ("%d%d%d", eu + i, ev + i, ew + i);
scanf ("%d%d", &src, &dst);
sort (id, id + M, cmp);
for (i = 1; i <= N; i ++) rank [pnt [i] = i] = 0;
for (i = 0; i < M; i ++)
{
j = id [i]; x = find (eu [j]); y = find (ev [j]);
if (rank [x] > rank [y]) pnt [y] = x;
else pnt [x] = y, rank [y] += (rank [x] == rank [y]);
if (find (src) == find (dst)) break;
}
if (i == M) printf ("0\n");
else printf ("%d\n", ew [j]);
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -