POJ3621 Sightseeing Cows


这道题是求最优比率环,使点权和除以边权和最大,二分判断即为存在负环,可以用dfs版的spfa进行判断,注意由于二分答案使用duoble,所以与之相关的变量数组一定要定义为duoble

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=5050;
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int n,m,head[maxn],num=0;
int vv[maxn],vis[maxn];
double d[maxn],mid;
struct node{
    int v,w,nex;
}e[maxn];
void add(int u,int v,int w)
{
    e[++num].v=v;
    e[num].w=w;
    e[num].nex=head[u];
    head[u]=num;
}
bool spfa(int u)
{
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nex)
    {
        int v=e[i].v;
        if(d[v]>d[u]+mid*e[i].w-vv[u])
        {
            if(vis[v]) return 1;
            d[v]=d[u]+mid*e[i].w-vv[u];
            if(spfa(v)) return 1;
        }
    }
    vis[u]=0;
    return 0;
}
bool pan(double mid)
{
    memset(d,0,sizeof(d));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    if(spfa(i)) return true;
    return false;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) vv[i]=read();
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        x=read(),y=read(),z=read();
        add(x,y,z);
    }
    double l=0,r=10000;
    while(r-l>1e-6)
    {
        mid=(l+r)/2;
        if(pan(mid)) l=mid;
        else r=mid;
    }
    printf("%.2lf\n",l);
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
POJ1201Intervals POJ1201Intervals
这是一道差分约束,可以考虑前缀和,对于一个区间$[a_i,b_i]$要使选取数字超过$c_i$,可以得出不等式$s[b_i]-s[a_i-1]\geq c_i$,当然这样的限制还不够,我们要保证它的结果有意义,对于每一个$k$,都存在这样两
2019-07-05
下一篇 
POJ2976 Dropping tests POJ2976 Dropping tests
01分数规划裸题,给出n个物品有a b两个属性,选定n-k个元素,使$\sum{a_i}/\sum{b_i}$最大 #include<iostream> #include<cstdio> #include<cstring
2019-07-05
  目录