LOJ #10084. 「一本通 3.3 练习 1」最小圈(二分+SPFA判负环)

时间:2021-09-28 00:03:23

题意描述:

   见原LOJ:https://loj.ac/problem/10084

题解:

  假设所求的平均最小值为X,环上各个边的权值分别为A1,A2...Ak,可以得到:

    X=(A1+A2+A3+...+Ak)/K,

    A1+A2+A3+...+Ak=X*K,

    移项可得:(A1-X)+(A2-X)+(A3-X)+...+(Ak-X)=0,

    另外注意到式子中的等于号可以改为大于等于,那么我们可以二分结果ans,然后判断是否存在一组解满足(A1+A2+A3+...+Ak)/k<=ans,

    即判断:(A1-ans)+(A2-ans)+(A3-ans)+...+(Ak-ans)<=0;

    最后问题就变成了二分一个ans后在图中判断是否存在一个负环。

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 30009
#define maxm 10009
#define eps 1e-9
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+(ll)(ch-'');ch=getchar();}
return x*f;
}
bool flag;
bool vis[maxn];
double dis[maxn];
int head[maxn];
struct edge
{
int to,nxt;
double val;
}p[maxm];
int n,m,k,tot,cnt;
double ans,sum,l,r; void add(int x,int y,double z)
{
++cnt,p[cnt].to=y,p[cnt].nxt=head[x],p[cnt].val=z,head[x]=cnt;
} void Spfa(int u,double ave)
{
if(flag)
return ;
vis[u]=;
for(int i=head[u];i;i=p[i].nxt)
{
int v=p[i].to;
if(dis[u]+p[i].val-ave<dis[v])
{
dis[v]=dis[u]+p[i].val-ave;
if(!vis[v])
Spfa(v,ave);
if(flag)
return ;
else if(vis[v])
{
flag=true;
return ;
}
}
}
vis[u]=;
}
bool Check(double ave)
{
flag=false;
memset(vis,,sizeof(vis));
for(int j=;j<maxn;j++)
dis[j]=;
for(int i=;i<=n;i++)
{
Spfa(i,ave);
if(flag)
break;
}
return flag;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read(),m=read();
for(int i=;i<=m;i++)
{
int x=read(),y=read();
double z;scanf("%lf",&z);
add(x,y,z);
}
l=-1e7,r=1e7;
while((r-l)>eps)
{
double mid=(l+r)/;
if(Check(mid))
{
ans=mid;
r=mid;
}
else
l=mid;
}
printf("%0.8lf",ans);
fclose(stdin);
fclose(stdout);
return ;
}