[UVALIVE 5713] 진시황 도로 보수 (최소 병목 로 + Kruskal)

전송 문
진시황
I think
    제목: n 개 도시 와 m 개의 길 을 제시 하고 n - 1 개의 길 을 건설 하 는 방안 을 구하 여 A / B 를 최대 로 한다.A 는 당신 이 선택 할 수 있 는 돈 을 지불 하지 않 아 도 되 는 길 i 를 말 합 니 다. 그것 이 연 결 된 두 도시 의 총 인 구 를 말 합 니 다.B. 길 을 가리 키 는 i 의 길이 입 니 다.    알고리즘: 최소 병목 길    사고: 최소 생 성 트 리 를 구하 세 요.임의의 두 점 을 도로 (u, v) 의 양 끝 으로 매 거 합 니 다. 만약 에 답 변 (u, v) 이 최소 생 성 트 리 에 있 지 않 으 면 이 변 까지 고리 가 됩 니 다. 그래서 u 를 삭제 합 니 다. v 는 MST 의 경로 중 가장 긴 변 (최소 병목 길: 두 결점 사이 의 가장 긴 변 의 가장 짧 은 경로) 을 삭제 합 니 다. 그렇지 않 으 면 가장 작은 생 성 트 리 에서 사 이 드 를 삭제 합 니 다.    데이터 범위 가 더 넓 으 면 두 점 사이 의 최소 병목 로 를 배로 늘 리 는 방법 으로 처리 할 수 있다.
Code

#include
#include
#include
#include
#include

const int sm = 1e3+10;
const int sn = 1e6+10;

int T,N,S,Ct,l;
int hd[sm],to[sm<<1],nxt[sm<<1];
int Fa[sm],X[sm],Y[sm],C[sm];
double mxc[sm][sm];
double Ans,tot,w[sm<<1];
struct Edge {
    int Fm,To;double L;
    bool ex;
}Ed[sn];
std::vector<int>g; 

bool cmp(Edge x,Edge y) { return x.Ltemplate <typename T> T Max(T x,T y) { return x>y?x:y; }
void Ins(int u,int v,double len) { Ed[++S]=(Edge) {u,v,len};}
double Len(int x,int y,int a,int b) { return (double)sqrt((x-a)*(x-a)+(y-b)*(y-b)); }

void read(int &x) {
    x=0;char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}

void init() {
    S=Ct=0,Ans=tot=0;
    l=Max(N,N*(N-1)/2);
    for(int i=1;i<=l;++i) {
        if(i<=N)hd[i]=0;
        Ed[i].ex=0;
    }
    if(!g.empty()) g.clear();
    memset(mxc,0,sizeof(mxc)); 
}
void Add(int u,int v,double len) {
    to[++Ct]=v,nxt[Ct]=hd[u],hd[u]=Ct,w[Ct]=len;
    to[++Ct]=u,nxt[Ct]=hd[v],hd[v]=Ct,w[Ct]=len;
}
int Find(int x) {
    if(x!=Fa[x]) Fa[x]=Find(Fa[x]);
    return Fa[x];
}
void Kruskal() {
    int x,y;
    for(int i=1;i<=N;++i) Fa[i]=i;
    std::sort(Ed+1,Ed+S+1,cmp);
    for(int i=1;i<=S;++i) {
        x=Find(Ed[i].Fm);
        y=Find(Ed[i].To);
        if(x!=y) {
            Add(Ed[i].Fm,Ed[i].To,Ed[i].L);
            Ed[i].ex=1;
            Fa[x]=y,tot+=Ed[i].L;
            if((Ct>>1)==N-1) break;
        }
    }
}
void Dfs(int x,int fa,double LEN) {
    for(int i=0;ifor(int i=hd[x];i;i=nxt[i])
        if(to[i]!=fa) Dfs(to[i],x,w[i]);
}
void Calc() {
    for(int i=1,x,y,z;i<=S;++i) {
        x=Ed[i].Fm,y=Ed[i].To,z=C[x]+C[y];
        if(Ed[i].ex) Ans=Max(Ans,z*1.0/(tot-Ed[i].L));
        else Ans=Max(Ans,z*1.0/(tot-mxc[x][y]));
    }
}
int main() {
    read(T);
    while(T--) {
        init(),read(N);
        for(int i=1;i<=N;++i)
            read(X[i]),read(Y[i]),read(C[i]);
        for(int i=1;ifor(int j=i+1;j<=N;++j)
                Ins(i,j,Len(X[i],Y[i],X[j],Y[j]));
        Kruskal(),Dfs(1,0,0),Calc();
        printf("%.2lf
",Ans);
    }
    return 0;
}