BZOJ1050 [HAOI2006]旅行comf[并查集判图连通性]

★

Description

给你一个无向图，N(N<=500)个顶点, M(M<=5000)条边，每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T，求

一条路径，使得路径上最大边和最小边的比值最小。如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出这个

比值，如果需要，表示成一个既约分数。备注：两个顶点之间可能有多条路径。

体现了并查集实际作用的一道题，也就是判图连通性。几句总结：

最小化或最大化一个分数时通常可以二分，但是也可以去设法最大or最小化分子分母。二分不好check的话就可以尝试后者。

据说二分带点优化其实是可以的，然而我不会。根据上面那则提示，因为最大边和最小边无法同时分别最小和最大化，所以可以先固定分母（最小边）。然后要求分子尽可能小。就是说找大于最小边的一些边让s到t连通，最小化那个最大边。那么对于最小的最大边，只要从最小边开始从小到大不停加边，直到s与t连通时立即停止即可，找到的一定是最小的最大边，正确性很容易证（最小的可行解之前的所有边都无法使其连通，而当前为第一个可行解，即最小）。于是枚举最小边并查集维护连通性就行，$O(N^{2}α(N))$稍有点卡，但是能过。可以把除法比较转换成乘法比较加一点速。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #define dbg(x) cerr<<#x<<" = "<<x<<endl

 #define ddbg(x,y) cerr<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}

 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=+;

 struct thx{

     int u,v,w;

     inline bool operator <(const thx&orz)const{

         return w<orz.w;

     }

 }e[N];

 int fa[N],n,m,s,t,p=,q=;

 inline int Get(int x){return fa[x]^x?fa[x]=Get(fa[x]):x;}

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

 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);

     read(n),read(m);

     for(register int i=;i<=m;++i)read(e[i].u),read(e[i].v),read(e[i].w);

     sort(e+,e+m+);read(s),read(t);

     for(register int i=;i<=m;++i){

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

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

             fa[Get(e[j].u)]=Get(e[j].v);

             if(Get(s)==Get(t))break;

         }

         if(Get(s)==Get(t))if(p*e[i].w>q*e[j].w)p=e[j].w,q=e[i].w;

     }

     if(p>)printf("IMPOSSIBLE\n");

     else p%q==?printf("%d",p/q):printf("%d/%d\n",p/gcd(p,q),q/gcd(p,q));

     return ;

 }

巴特西

BZOJ1050 [HAOI2006]旅行comf[并查集判图连通性]

★

Description

最小化或最大化一个分数时通常可以二分，但是也可以去设法最大or最小化分子分母。二分不好check的话就可以尝试后者。

最新文章

热门文章