HAOI2006 旅行

wjh15101051's space

卧薪尝胆，厚积薄发。

HAOI2006 旅行

Date: Mon Jul 16 23:31:55 CST 2018

In Category: NoCategory

Description：

给你一个无向图， $N$ 个顶点， $M$ 条边，每条边有一个权值 $V_i$ 。给你两个顶点 $S$ 和 $T$ ，求一条路径，使得路径上最大边和最小边的比值最小。

$1\le N \le 500$ $1\le M \le 5000$

Solution：

$M$ 只有 $5000$ ， $O(M^2)$ 也可过，于是可以将边排序后枚举一个最小边，不断加边直到 $S$ 和 $T$ 联通，即可得到路径上最大边，更新答案即可。

如果 $M$ 更大，可以用 $LCT$ 维护生成树，每次把环中最小边 $cut$ 掉并加入新边。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXM 5010

struct edge

{

	int u,v,w;

}e[MAXM];

bool cmp(edge x,edge y){return x.w < y.w;}

#define MAXN 510

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int ans1,ans2;

int gcd(int a,int b){return (b == 0 ? a : gcd(b,a % b));}

int s,t;

int main()

{

	ans1 = 0x3f3f3f3f,ans2 = 1;

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

	scanf("%d%d",&s,&t);

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

	bool found = false;

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

	{

		for(int k = 1;k <= n;++k)f[k] = k;

		for(int j = i;j <= m;++j)

		{

			int p = find(e[j].u),q = find(e[j].v);

			if(p == q)continue;

			f[p] = q;

			if(find(s) == find(t))

			{

				found = true;

				if(((double)ans1 / (double)ans2) > ((double)e[j].w / (double)e[i].w))

				{

					ans1 = e[j].w;ans2 = e[i].w;

				}

				break;

			}

		}

	}

	int t = gcd(ans1,ans2);

	ans1 /= t;ans2 /= t;

	if(!found)puts("IMPOSSIBLE");

	else if(ans2 != 1)cout << ans1 << "/" << ans2 << endl;

	else cout << ans1 << endl;

	return 0;

}

In tag: 图论-kruskal

wjh15101051