ecnu鉄道修復計画
4193 ワード
http://acm.ecnu.edu.cn/problem/3247/
簡単麻、二分k、毎回得られる二分結果kは、外国人が作ったレールの価値に乗って、走りながら最小の木を作ればいいです.その後、最小費用と計画費の大きさを判断すればいいです.
簡単麻、二分k、毎回得られる二分結果kは、外国人が作ったレールの価値に乗って、走りながら最小の木を作ればいいです.その後、最小費用と計画費の大きさを判断すればいいです.
#include
#define mme(i,j) memset(i,j,sizeof(i))
using namespace std;
struct node
{
int u,v,f;
double t;
bool operator return t1000005],tp[1000005];
long long n,m,money;
int pre[1000005];
int find_x(int x)
{
if(x==pre[x])
return x;
else
return pre[x]=find_x(pre[x]);
}
bool check(double mid)
{
for(long long i=1;i<=m;i++)
{
tp[i]=rout[i];
if(tp[i].f==1)
tp[i].t*=mid;
}
for(long long int i=1;i<=n;i++)
pre[i]=i;
sort(tp+1,tp+1+m);
double ans=0;
int u,v;
for(long long i=1;i<=m;i++)
{
u=find_x(tp[i].u);
v=find_x(tp[i].v);
if(u!=v)
{
ans+=tp[i].t;
pre[u]=v;
}
}
if(ans<=money)
return true;
return false;
}
int main()
{
while(~scanf("%lld%lld%lld",&n,&m,&money))
{
for(long long i=1;i<=m;i++)
{
scanf("%d%d%lf%d",&rout[i].u,&rout[i].v,&rout[i].t,&rout[i].f);
tp[i]=rout[i];
}
double mid,l=0,r=1000000,ans=-1;
while( (r-l) >=1e-8)
{
mid = (l+r)/2;
if(check(mid))
{
l=mid;
ans = mid;
}
else
r=mid;
}
if(ans==-1.0)
ans=1.0;
printf("%.6f
",ans);
}
return 0;
}