题意为给定一张图和 s,t 两个点, 问 s 到 t 的路径中最大边权 / 最小边权的最小值
其实就是让最大边权尽量小, 最小边权尽量大
把边按边权排序, 枚举最大边, 依次从大到小加入比他小的边, 直到 s 和 t 联通, 此时最小边权最大, 更新答案
未过 bzoj(shabi)
- #include<bits/stdc++.h>
- #define ll long long
- using namespace std;
- const int maxn=509;
- const int maxm=5009;
- int n,m,s,t;
- struct node{
- int u,v,w;
- bool operator <(const node&t)const{
- return w<t.w;
- }
- }e[maxm];
- int fa[maxn];
- int find(int x){
- while(x!=fa[x])x=fa[x]=fa[fa[x]];
- return x;
- }
- ll gcd(ll a,ll b){
- return b==0?a:gcd(b,a%b);
- }
- struct frac{
- long long up,dn;
- frac(){}
- frac(ll uu,ll dd){
- up=uu;dn=dd;
- }
- void set(){
- int g=gcd(up,dn);
- up/=g,dn/=g;
- }
- void out(){
- // set();
- if(dn==1)printf("%d\n",up);
- else printf("%d/%d\n",up,dn);
- }
- bool operator <(const frac&t)const{
- if(up*t.dn<dn*t.up)return 1;
- else return 0;
- }
- }ans;
- int vis[maxn];
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)fa[i]=i;
- for(int i=1,u,v;i<=m;i++){
- scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
- u=find(e[i].u),v=find(e[i].v);
- if(u!=v)fa[u]=v;
- }
- scanf("%d%d",&s,&t);
- if(find(s)!=find(t)){
- printf("IMPOSSIBLE");
- return 0;
- }
- int ff=find(s);
- for(int i=1;i<=n;i++)if(find(i)!=ff)vis[i]=1;
- for(int i=1;i<=n;i++)fa[i]=i;
- sort(e+1,e+1+m);
- ans=frac(1e8,1);
- for(int i=1;i<=m;i++){
- int u=e[i].u,v=e[i].v;
- if(vis[u] || vis[v])continue;
- for(int j=1;j<=n;j++)fa[j]=j;
- for(int j=i;j>=1;j--){
- int u=e[j].u,v=e[j].v;
- if(vis[u] || vis[v])continue;
- int uu=find(u),vv=find(v);
- if(uu!=vv){
- fa[uu]=vv;
- if(find(s)==find(t)){
- frac a=frac(e[i].w,e[j].w);
- a.set();
- if(a<ans)ans=a;
- break;
- }
- }
- }
- }
- ans.set();
- ans.out();
- }
[题解]luogu_P2502[HAOI2006] 旅行 (最小生成树 / 并查集乱搞
来源: http://www.bubuko.com/infodetail-3209460.html