POJ 3621 Sightseeing Cows [最优比率环]

感觉去年9月的自己好$naive$ http://www.cnblogs.com/candy99/p/5868948.html

现在不也是嘛

裸题，具体看学习笔记

二分答案之后判负环就行了

$dfs$版超快

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

typedef long long ll;

const int N=,M=;

const double eps=1e-;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,u,v;

double f[N];

struct edge{

    int v,ne;

    double w;

}e[M<<];

int h[N],cnt=;

inline void ins(int u,int v,int w){

    cnt++;

    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;

}

double d[N];

int inq[N],num[N];

int q[N],head,tail;

inline void lop(int &x){if(x==N) x=;}

bool NegativeCircle(double mid){

    head=tail=;

    for(int i=;i<=n;i++) d[i]=,inq[i]=,q[tail++]=i,num[i]=;

    while(head!=tail){

        int u=q[head++];lop(head);inq[u]=;

        for(int i=h[u];i;i=e[i].ne){

            int v=e[i].v;double w=mid*e[i].w-f[u];

            if(d[v]>d[u]+w){

                d[v]=d[u]+w;

                if(!inq[v]){

                    inq[v]=;q[tail++]=v;lop(tail);

                    if(++num[v]>n) return true;

                }

            }

        }

    }

    return false;

}

inline bool check(double mid){return NegativeCircle(mid);}

void solve(){

    double l=,r=;

    while(r-l>eps){

        double mid=(l+r)/2.0;

        if(check(mid)) l=mid;

        else r=mid;

    }

    printf("%.2f",l);

}

int main(){

    freopen("in","r",stdin);

    n=read();m=read();

    for(int i=;i<=n;i++) f[i]=read();

    for(int i=;i<=m;i++) u=read(),v=read(),ins(u,v,read());

    solve();

}

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

typedef long long ll;

const int N=,M=;

const double eps=1e-;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,u,v;

double f[N];

struct edge{

    int v,ne;

    double w;

}e[M<<];

int h[N],cnt=;

inline void ins(int u,int v,int w){

    cnt++;

    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;

}

double d[N];

int vis[N],cl;

bool dfs(int u,double mid){

    vis[u]=cl;

    for(int i=h[u];i;i=e[i].ne){

        int v=e[i].v;double w=mid*e[i].w-f[u];

        if(d[v]>d[u]+w){

            d[v]=d[u]+w;

            if(vis[v]==vis[u]) return true;

            else if(dfs(v,mid)) return true;

        }

    }

    vis[u]=;

    return false;

}

bool NegativeCircle(double mid){

    memset(vis,,sizeof(vis));

    for(cl=;cl<=n;cl++) if(dfs(cl,mid)) return true;

    return false;

}

inline bool check(double mid){return NegativeCircle(mid);}

void solve(){

    double l=,r=;

    while(r-l>eps){

        double mid=(l+r)/2.0;

        if(check(mid)) l=mid;

        else r=mid;

    }

    printf("%.2f",l);

}

int main(){

    freopen("in","r",stdin);

    n=read();m=read();

    for(int i=;i<=n;i++) f[i]=read();

    for(int i=;i<=m;i++) u=read(),v=read(),ins(u,v,read());

    solve();

}

巴特西

POJ 3621 Sightseeing Cows [最优比率环]

最新文章

热门文章