题面
标题比题面好懂系列. 题目就是要求所有环中边权之和与环长之比的最小值.
令点权为1(方便统计长度. 更一般的0/1分数规划题中点权是可以任意取的, 后续推导一致), 则
$ ans=\sum{e.w}/\sum{v.w}$
$ \sum{e.w}-ans*\sum{v.w}=0$
$ \sum(e.w-ans*v.w)=0$
$ \sum_{i=1}^{k}(e_i.w-ans*v_i.w)=0 (e_k,v_k\text{在环上})$
$ \sum_{i=1}^{k}(e_i.w-ans)=0$
然后就可以二分ans(实数域上)
chk(mid): 图以$ e_i-mid$为边权, 若存在一个负环, 即存在一组位于一个环上的k个数使 $ \sum_{i=1}^{k}(e_{i}.w-mid)<0$(对于更一般的0/1分数规划, i可以取任意值, 也可以选任意多个值, 这时选所有使$ e_{i}.w-mid*v_{i}$为正的数即可判断”负环”存不存在/答案可不可行), 则有
$ \sum e.w<mid*\sum v.w$
$ mid>\sum e.w/\sum v.w$
即 mid>ans , 则mid要变小, r=mid
注意找负环要用dfs的SPFA, 存在负环时它会绕圈.
展开远古代码
#include<cstdio>
#include<cstring>
#define int long long
#define db double
#define in inline
#define re register
in int read()
{
int s=0,b=0;
char ch;
do{
ch=getchar();
if(ch=='-') b=1;
}while(ch<'0' || ch>'9');
while(ch>='0' && ch<='9')
{
s=(s<<3)+(s<<1)+(ch^48);
ch=getchar();
}
return b?-s:s;
}
int n,m;
struct edge{
int t,nxt;
db w,ww;//ww是原边权
}e[20020];
int head[3001],cnt=0;
in void add(int f,int t,db ww)
{
e[++cnt].t=t;
e[cnt].ww=ww;
e[cnt].nxt=head[f];
head[f]=cnt;
}
int b[3001];
db dis[3001];
int flag;
in void spfa(int u)
{
b[u]=1;
for(re int i=head[u];i;i=e[i].nxt)
{
if(dis[u]+e[i].w<dis[e[i].t] && !flag)
{
dis[e[i].t]=dis[u]+e[i].w;
if(!b[e[i].t]) spfa(e[i].t);
else {flag=1;break;}
}
}
b[u]=0;
}//bfs的spfa会tle, dfs版找负环会快得多, 因为它会沿着负环一直走完, 不是一层层的走完
in bool chk(db ans)
{
for(re int i=1;i<=m;++i) e[i].w=e[i].ww-ans;
flag=0;
for(re int i=1;i<=n;++i)
{
memset(b,0,sizeof(b));
for(re int i=1;i<=n;++i) dis[i]=0;
spfa(i);
if(flag) return false;//只要有一个负环, 就说明mid大了
}
return true;
}
in db fabs(db x)
{
return x>0?x:-x;
}
signed main()
{
n=read();
m=read();
for(re int i=1;i<=m;++i)
{
int f,t;
db ww;
f=read();
t=read();
scanf("%lf",&ww);
add(f,t,ww);
}
db l=-1e6,r=1e6,eps=1e-10;
while(fabs(l-r)>eps)
{
db mid=(l+r)/2;
if(chk(mid)) l=mid;
else r=mid;
}
printf("%0.8lf\n",l);
return 0;
}