Bond UVA - 11354(并查集按秩合并)

题意:

  给你一张无向图,然后有若干组询问,让你输出a->b的最小瓶颈路。

解析:

  应该都想过用prime的次小生成树做。。但二维数组开不了那么大。。所以只能用kruskal了。。。。

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff, maxm = 1e5+;
int n, m;
int f[maxn], ra[maxn], vis[maxn], edge[maxn]; struct node
{
int u, v, w;
}Node[maxm]; bool cmp(node a, node b)
{
return a.w < b.w;
}
int find(int x)
{
return f[x] == x ? x : find(f[x]);
} int query(int x, int y)
{
int ans1 = , ans2 = -;
int cur = x;
while() //从x回溯到祖先
{
vis[cur] = ans1; //标记 从x到当前cur的最大权值的路段
if(cur == f[cur]) break;
ans1 = max(ans1, edge[cur]);
cur = f[cur];
}
cur = y;
while() //从y回溯到祖先
{
if(vis[cur] >= ) //直到遇到y和x的最近公共祖先
{
ans2 = max(ans2, vis[cur]);
break;
}
ans2 = max(ans2, edge[cur]);
cur = f[cur];
}
cur = x;
while() //还原vis。。其实用一个memset就好了。。但时间复杂度竟然比用这个大10倍。。emm。。。
{
vis[cur] = -;
if(cur == f[cur]) break;
cur = f[cur];
}
return ans2;
} void init()
{
rap(i, , n)
{
f[i] = i;
ra[i] =;
}
mem(vis, -);
} int main()
{
bool flag = true;
while(~scanf("%d%d", &n, &m))
{
init();
rap(i, , m)
{
scanf("%d%d%d", &Node[i].u, &Node[i].v, &Node[i].w);
}
sort(Node+, Node+m+, cmp);
rap(i, , m) //按秩合并
{
int l = find(Node[i].u);
int r = find(Node[i].v);
if(l == r) continue;
if(ra[l] <= ra[r]) f[l] = r, ra[r] = max(ra[r], ra[l] + ), edge[l] = Node[i].w; //儿子标记权值
else f[r] = l, ra[l] = max(ra[l], ra[r] + ), edge[r] = Node[i].w;
}
if(flag) flag = false;
else printf("\n");
int q;
scanf("%d", &q);
rap(i, , q)
{
int u, v;
scanf("%d%d", &u, &v);
printf("%d\n", query(u, v));
} } return ;
}
上一篇:【C语言】为什么指明数组的列数?


下一篇:程序员教程-9章-C程序设计