首页 > 其他 > 详细

BZOJ [HAOI2006]旅行comf

时间:2018-02-21 19:17:04      阅读:75      评论:0      收藏:0      [点我收藏+]

标签:cmp   iostream   bzoj   can   light   oid   names   pos   zoj   

题解:枚举最大边,然后对<=最大边的边做最大生成树,使最小边最大

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100009;
const int oo=1000000000;

int Gcd(int a,int b){
	if(b==0)return a;
	return Gcd(b,a%b);
}

double ans=oo;
int ansa,ansb;

int n,m;
int s,t;

int father[maxn];
int Getf(int x){
	if(father[x]==x)return x;
	return father[x]=Getf(father[x]);
}
void Unionn(int x,int y){
	int fx=Getf(x);
	int fy=Getf(y);
	if(fx!=fy)father[fx]=fy;
}


struct Edge{
	int u,v,d;
}edges[maxn];
bool cmp(const Edge &rhs1,const Edge &rhs2){
	return rhs1.d<rhs2.d;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].d);
	sort(edges+1,edges+1+m,cmp);
	scanf("%d%d",&s,&t);
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j)father[j]=j;
		Unionn(edges[i].u,edges[i].v);
		if(Getf(s)==Getf(t)){
			printf("1\n");
			return 0;
		}
		for(int j=i-1;j;--j){
			int u=edges[j].u;
			int v=edges[j].v;
			if(Getf(u)!=Getf(v)){
				Unionn(u,v);
			}
			if(Getf(s)==Getf(t)){
				if(1.0*edges[i].d/edges[j].d<ans){
					ansa=edges[i].d;
					ansb=edges[j].d;
					ans=1.0*edges[i].d/edges[j].d;
				}
				break;
			}
		}
	}
	
	if(ans>oo-1){
		printf("IMPOSSIBLE\n");
	}else{
		int d=Gcd(ansa,ansb);
		ansa/=d;
		ansb/=d;
		if(ansb==1)printf("%d\n",ansa);
		else printf("%d/%d\n",ansa,ansb);
	}
	return 0;
}

  

BZOJ [HAOI2006]旅行comf

标签:cmp   iostream   bzoj   can   light   oid   names   pos   zoj   

原文:https://www.cnblogs.com/zzyer/p/8457061.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号