1486: [HNOI2009]最小圈

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 3129  Solved: 1543
[Submit][Status][Discuss]

Description

Input

 

Output

 

Sample Input

4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3

Sample Output

3.66666667

 

二分法+spfa_dfs最小圈

可以经过计算在T=60次循环后，答案精度会在小数点后8位

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 using namespace std;

 const int MAXN=;

 struct Edge

 {

     int to,next;

     double w;

 }E[MAXN];

 int node,head[MAXN];

 double dist[MAXN];

 bool flag,vis[MAXN];

 int n,m;

 double mid;

 void insert(int u,int v,double w)

 {

     E[++node]=(Edge){v,head[u],w};head[u]=node;

 }

 void spfa_dfs(int s)

 {

     vis[s]=;

     for(int i=head[s];i;i=E[i].next)

     {

         if(dist[E[i].to]>dist[s]+E[i].w-mid)

         {

             if(vis[E[i].to]){flag=;return;}

             else

             {

                 dist[E[i].to]=dist[s]+E[i].w-mid;

                 spfa_dfs(E[i].to);

             }

         }

     }

     vis[s]=;

 }

 bool check()

 {

     flag=;

     memset(dist,,sizeof(dist));

     memset(vis,,sizeof(vis));

     for(int i=;i<=n;i++)

     {

         dist[i]=;

         spfa_dfs(i);

         if(flag) return ;

     }

     return ;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++)

     {

         int u,v,w;

         scanf("%d%d%d",&u,&v,&w);

         insert(u,v,w);

     }

     double l=-1e7,r=1e7;

     int T=;

     while(T--)

     {

         mid=(l+r)/;

         if(check()) r=mid;

         else l=mid;

     }

     printf("%.8lf",r);

     return ;

 }