luoguP2502旅行

2006河南省选

思路：（参考题解）

枚举最大的边（第\(i\)条），从这条边开始由大到小枚举、添边，当\(s\)和\(t\)联通时，此时即为以第\(i\)条边为最大边的答案，比较每个答案，判断输出。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 50005;

int n,m,fa[N],tot,s,t;

int ansm,ansz,anspm,anspz;

struct edge{

	int from,node,data;

}e[N];

void add(int x,int y,int z)

{

	e[++tot].from=x; e[tot].node=y;

	e[tot].data=z;

}

bool cmp(edge a,edge b)

{ return a.data<b.data; }

int find(int x)

{

	if(x!=fa[x]) fa[x]=find(fa[x]);

	return fa[x];

}

void uni(int x,int y)

{

	int f1=find(x),f2=find(y);

	fa[f1]=f2;

}

bool judge()

{ return find(s)==find(t); }

int gcd(int x,int y)

{

	if(x%y==0) return y;

	return gcd(y,x%y);

}

int main()

{

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

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

	int x,y,z;

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

	{

		scanf("%d%d%d",&x,&y,&z);

		add(x,y,z); uni(x,y);

	}

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

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

	{ printf("IMPOSSIBLE\n"); return 0; }

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

	for(int i=tot;i>=1;i--)

	{

		anspz=e[i].data;

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

	    for(int j=i;j>=1;j--)

	    {

	    	uni(e[j].from,e[j].node);

	    	if(judge())

	    	{	anspm=e[j].data;

	    	    if(ansm==0) ansm=anspm,ansz=anspz;

	    		else if((ansz*anspm)>(anspz*ansm))

	    		 ansm=anspm,ansz=anspz;

	    	}

	    //	if(ansm!=0&&(ansz*anspm)<(anspz*ansm)) break;

	    }

	}

	int t=gcd(ansm,ansz);

	ansm=ansm/t;

	ansz=ansz/t;

	if(ansm==1) printf("%d\n",ansz);

	else printf("%d/%d\n",ansz,ansm);

	return 0;

}