[HNOI2009]最小圈 分数规划 spfa判负环

时间:2021-02-11 20:08:36

[HNOI2009]最小圈 分数规划 spfa判负环

题面

思路难,代码简单。

题目求圈上最小平均值,问题可看为一个0/1规划问题,每个边有\(a[i],b[i]\)两个属性,\(a[i]=w(u,v),b[i]=1\),问题转化为\(min(\frac{\sum^{k}_{i=1}a[i]}{\sum^{k}_{j=1}b[j]})\)

分数规划考虑二分答案,当前\(mid\)可能为答案当且仅当:

\[\frac{\sum^{k}_{i=1}a[i]}{\sum^{k}_{j=1}b[j]} < mid
\]

化简即为判定:

\[\sum{}^{k}_{i=1} (a[i]-mid)<0
\]

每次二分答案时,将图中所有边权\(a[i]​\)视为\(a[i]-mid​\),此时问题转换为一个\(spfa​\)判负环问题,考虑使用\(dfs​\)优化的\(spfa​\)

AC Code:

#include <cstdio>
#include <cstring>
#define MAXN 3003
#define MAXM 10010
using namespace std;
int head[MAXN],nxt[MAXM],vv[MAXM],tot;
double ww[MAXM];
inline void add_edge(int u, int v, double w){
vv[++tot]=v;
ww[tot]=w;
nxt[tot]=head[u];
head[u]=tot;
}
double dis[MAXN];
bool vis[MAXN];
bool spfa(int u, double mid){
vis[u]=1;
for(register int i=head[u];i;i=nxt[i]){
int v=vv[i];double w=ww[i]-mid;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(vis[v]) return 1;
if(spfa(v,mid)) return 1;
}
}
vis[u]=0;
return 0;
}
inline int read()
{
int s=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*f;
}
int n,m;
int main()
{
n=read(),m=read();
while(m--){
int a,b;double w;a=read(),b=read();scanf("%lf", &w);
add_edge(a,b,w);
}
double l=-1e7,r=1e7,mid;
while(r-l>1e-10){
mid=(l+r)/2;
memset(dis, 0, sizeof(dis));
memset(vis, 0, sizeof(vis));
bool isOK=0;
for(register int i=1;i<=n;++i)
if(spfa(i,mid)){
isOK=1;break;
}
if(isOK) r=mid;
else l=mid;
}
printf("%.8lf", mid);
return 0;
}