首页 > 代码库 > POJ 3621 Sightseeing Cows [最优比率环]
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=1005,M=5005;const double eps=1e-4;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,u,v;double f[N];struct edge{ int v,ne; double w;}e[M<<1];int h[N],cnt=0;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=1;}bool NegativeCircle(double mid){ head=tail=0; for(int i=1;i<=n;i++) d[i]=0,inq[i]=1,q[tail++]=i,num[i]=1; while(head!=tail){ int u=q[head++];lop(head);inq[u]=0; 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]=1;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=0,r=2000; 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=1;i<=n;i++) f[i]=read(); for(int i=1;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=1005,M=5005;const double eps=1e-4;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,u,v;double f[N];struct edge{ int v,ne; double w;}e[M<<1];int h[N],cnt=0;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]=0; return false;}bool NegativeCircle(double mid){ memset(vis,0,sizeof(vis)); for(cl=1;cl<=n;cl++) if(dfs(cl,mid)) return true; return false;}inline bool check(double mid){return NegativeCircle(mid);}void solve(){ double l=0,r=2000; 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=1;i<=n;i++) f[i]=read(); for(int i=1;i<=m;i++) u=read(),v=read(),ins(u,v,read()); solve();}
POJ 3621 Sightseeing Cows [最优比率环]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。