BZOJ 1050 [HAOI2006]旅行comf Kruskal

Description

給你一個無向圖，N(N<=500)個頂點, M(M<=5000)條邊，每條邊有一個權值Vi(Vi<30000)。給你兩個頂點S和T，求

一條路徑，使得路徑上最大邊和最小邊的比值最小。如果S和T之間沒有路徑，輸出”IMPOSSIBLE”，否則輸出這個

比值，如果需要，表示成一個既約分數。 備注： 兩個頂點之間可能有多條路徑。

Input

第一行包含兩個正整數，N和M。下來的M行每行包含三個正整數：x，y和v。表示景點x到景點y之間有一條雙向公路

，車輛必須以速度v在該公路上行駛。最後一行包含兩個正整數s，t，表示想知道從景點s到景點t最大最小速度比

最小的路徑。s和t不可能相同。

1<N<=500,1<=x,y<=N，0<v<30000，0<M<=5000

Output

如果景點s到景點t沒有路徑，輸出“IMPOSSIBLE”。否則輸出一個數，表示最小的速度比。

如果需要，輸出一個既約分數。

Sample Input

【樣例輸入1】

4 2

1 2 1

3 4 2

1 4

【樣例輸入2】

3 3

1 2 10

1 2 5

2 3 8

1 3

【樣例輸入3】

3 2

1 2 2

2 3 4

1 3

Sample Output

【樣例輸出1】

IMPOSSIBLE

【樣例輸出2】

5/4

【樣例輸出3】

2

HINT

Source

​​傳送門​​

利用貪心的思想。

首先我們把邊按照邊權升序排序。

然後我們看到假設我們枚舉一條邊x，

将它作為S~T的最小邊，

那麼接下來不停地加入比x邊權更大的邊，并且一條條加入，

直到S和T聯通為止（也就是Kruskal）

我們可以看到中間的邊權都是最大和最小之間的，是沒有用的。

這樣子O（M^2）的時間去枚舉就可以得到解。

注意一下v是會到30000的……

一開始MAX設了個30000結果90分???

後來MAX改大就過了。

提一下，如果這題N，M都提升到100000呢，怎麼做？

其實這題是可以用LCT優化的…

每次删除最小邊，然後加入新的最小邊，接着求解S~T的連通性。

因為删邊最多成為不聯通，是以最大值肯定是往後擴充的。

時間複雜度優化到了O（M*LogN）

（沒有仔細算過的……）

當然這題寫什麼LCT啊……

其實閑的話

也可以練練的。。

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int 
    N=505,
    M=5005,
    MAX=50000;
int n,m,fa[N];
struct Edge{
    int L,R,val;
}E[M];
bool cmp(Edge x,Edge y){
    return x.val<y.val;
}
int gcd(int a,int b){
    if (!b) return a;
        else return gcd(b,a%b);
}
int getfa(int x){
    if (fa[x]!=x) fa[x]=getfa(fa[x]);
    return fa[x];
}
void unn(int x,int y){
    int t1=getfa(x),
        t2=getfa(y);
    if (t1!=t2) fa[t2]=t1;
}
int main(){
    n=read(),m=read();
    for (int i=1;i<=m;i++)
        E[i].L=read(),E[i].R=read(),E[i].val=read();
    int S=read(),T=read();
    sort(E+1,E+1+m,cmp);
    int ansx=MAX,ansy=1,tx,ty;
    for (int i=1;i<=m;i++){
        for (int j=1;j<=n;j++) fa[j]=j;
        ty=E[i].val; tx=MAX;
        for (int j=i;j<=m;j++){
            unn(E[j].L,E[j].R);
            if (getfa(S)==getfa(T)){
                tx=E[j].val;
                break;
            }
        }
        if ((double)tx/(double)ty<
            (double)ansx/(double)ansy)
            ansx=tx,ansy=ty;
    }
    if (ansx==MAX) puts("IMPOSSIBLE");
        else{
            int t=gcd(ansx,ansy);
            ansx/=t,ansy/=t;
            if (ansx%ansy)
                printf("%d/%d\n",ansx,ansy);
                    else
                printf("%d\n",ansx/ansy);
        }
    return 0;
}