1447. Portkey Network 夜

http://acm.timus.ru/problem.aspx?space=1&num=1447

最优比率生成树(最小生成树+二分）

黑书 p303

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<algorithm>
#include<cmath>
#define LL long long
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const double eps=1e-9;
const int INF=0x3f3f3f3f;
const double FINF=1e12;
const int N=1005;
const int M=500005;
/*
int f[N];
struct node
{
    int l,r,t,c;
    double tmp;
}edge[M];
int x[M];
int fx(int x)
{
    if(f[x]!=x)
    f[x]=fx(f[x]);
    return f[x];
}
bool cmp(node x,node y)
{
    return x.tmp<y.tmp;
}
double kruskal(int n,int m,double k)
{
    for(int i=1;i<=n;++i)
    f[i]=i;
    for(int i=0;i<m;++i)
    edge[i].tmp=edge[i].c-k*edge[i].t;
    sort(edge,edge+m,cmp);
    for(int i=0;i<m;++i)
    {
        if(fx(edge[i].l)==fx(edge[i].r))
        {x[i]=0;}
        else
        {x[i]=1;f[fx(edge[i].l)]=fx(edge[i].r);}
    }
    double sum=0.0;
    for(int i=0;i<m;++i)
    {
        sum+=(edge[i].c-k*edge[i].t)*x[i];
    }
    return sum;
}
*/
int c[N][N],t[N][N],f[N];
double tmp[N][N],dist[N];
bool had[N];
double prim(int n,double k)
{
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    if(c[i][j]!=-1)
    tmp[i][j]=c[i][j]-k*t[i][j];
    for(int i=1;i<=n;++i)
    dist[i]=FINF;
    dist[1]=0.0;
    memset(had,false,sizeof(had));
    for(int w=0;w<n;++w)
    {
        int l=-1;
        for(int i=1;i<=n;++i)
        if(!had[i]&&(l==-1||dist[i]<dist[l]))
        l=i;
        had[l]=true;
        for(int i=1;i<=n;++i)
        if(!had[i]&&c[l][i]!=-1&&dist[i]>tmp[l][i])
        {dist[i]=tmp[l][i];f[i]=l;}
    }
    double sum=0.0;
    for(int i=2;i<=n;++i)
    sum+=tmp[f[i]][i];
    return sum;
}
int main()
{
    //freopen("data.in","r",stdin);
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(c,-1,sizeof(c));
        while(m--)
        {
            int i,j,t1,c1;
            scanf("%d %d %d %d",&i,&j,&t1,&c1);
            t[i][j]=t[j][i]=t1;
            c[i][j]=c[j][i]=c1;
        }
        double l=0.0,r=1e6;
        double mid;
        while(r-l>=eps)
        {
            mid=(l+r)/2.0;
            if(prim(n,mid)<=0.0)
            r=mid;
            else
            l=mid;
        }
        printf("%.8lf\n",mid);
    }
    return 0;
}