舒适的路线 (code[vs] 1001)

舒适的路线 (code[vs] 1001)

舒适的路线 (code[vs] 1001)

舒适的路线 (code[vs] 1001)

舒适的路线 (code[vs] 1001)

舒适的路线 (code[vs] 1001)

舒适的路线 (code[vs] 1001)

传送门 :code[vs]  1001

思路:拿到这题的首先的思路 , 就是跑一遍最短路。

可是在尝试了一会后发现不会写,于是果断弃

尝试另外的算法。。

于是就有的以下的算法。并查集 + 乱搞(有点像最小生成树) + 贪心

总的来说, 就是先对边排一遍序, 从最小边开始找

若找到一条边未访问过(即在不同的集合),则将他们合并, 如果他们的最大速度 除以 最小速度 比已有答案小,则更新答案

如此重复。。

最后找 最大速度和最小速度的最大公约数来化简。。

ok

#include <iostream>
#include <cstdio>
#include <algorithm>
#define Max 10005
#define INF 1e7
using namespace std;
char word;
int N, M;
int father [Max], Count;
int Answer_Max = INF, Answer_Min, Maxn, Minn;
struct node
{
int from;
int to;
int dis;
}Edge [Max];
inline void AddEdge(int from, int to, int dis)
{
Count++;
Edge [Count].from = from;
Edge [Count].to = to;
Edge [Count].dis = dis;
}
bool comp (const node a, const node b)
{
return a.dis < b.dis;
}
int find (int x) // 找祖先
{
if (father [x] == x)
return x;
else return father [x] = find (father [x]);
}
inline void read (int &now)
{
now = ;
word = getchar ();
while (word < '' || word > '')
word = getchar ();
while (word >= '' && word <= '')
{
now = now * + (int)(word - '');
word = getchar ();
}
}
int Gcd (int x, int y) //找最大公约数
{
return y == ? x : Gcd (y, x % y);
}
int main()
{
read (N);
read (M);
int x, y, v;
for (int i = ; i <= M; i++)
{
read (x);
read (y);
read (v);
AddEdge (x, y, v);
}
sort (Edge + , Edge + + M, comp); // 把边排序,从最小的边开始找
int start, end;
read (start);
read (end);
for (int k = ; k <= M; k++)
{ for (int i = ; i <= N; i++) // 把每个点的 祖先初始化为本身
father [i] = i;
Minn = Edge [k].dis; // 初始化最大值 最小值为 当前扫描边的速度
Maxn = Edge [k].dis;
for (int i = k; i <= M; i++)
{
int x = find (Edge [i].from); // 找当前边的 两个点的祖先
int y = find (Edge [i].to);
if (x != y) //判断两点是否不在同一集合中 , 如果不在,将这两个点合并 , 证明此边都 已访问
{
father [x] = y;
Maxn = max (Maxn, Edge [i].dis ); // 最大值为 之前的最大值 与当前边的值取大
}
if (find (start) == find (end)) // 如果起点与终点都在同一集合 , 说明图已经扫描完
break;
}
if (find (start) == find (end)) // 如果图已经扫描完, 且 当前的要求的值比上一次的小, 则更新答案
if (double (Maxn) / double (Minn) < double (Answer_Max) / double (Answer_Min))
{
Answer_Max = Maxn;
Answer_Min = Minn;
}
}
if (Answer_Min == ) // 如果 答案未更新,则证明无解
cout << "IMPOSSIBLE";
else
{
int now = Gcd (Answer_Max, Answer_Min); // 因为结果要化为既约分数(即化到最简) 所以找出最大速度与最小速度的最大公约数
Answer_Max /= now; // 化简
Answer_Min /= now;
if (Answer_Min == ) //如果化简后最小的速度为0 ,则证明 最大与最小可以整除
cout << Answer_Max << endl;
else
cout << Answer_Max << "/" << Answer_Min << endl;
}
return ;
}
上一篇:Java对象克隆(Clone)及Cloneable接口、Serializable接口的深入探讨


下一篇:c++空类的大小