首页 > 代码库 > （最优比例环）POJ 3621 - Sightseeing Cows
（最优比例环）POJ 3621 - Sightseeing Cows
题意：
在一个有向加权图中找到一个环，使这个环点权和/边权和 最大
分析：
一开始还没做过最优比率生成树，但是看到过，两题都A不了。
后来看了题解，索性一起撸掉。
这题可以用类似最优比率生成树的方法做，二分答案。
具体： 这个题解讲的很详细了。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 #include <queue> 6 7 8 using namespace std; 9 10 const int inf=0x3f3f3f3f;11 const int maxn=1010;12 13 #define eps (1e-6)14 15 int sgn(double x) {16 return x<-eps?-1:x>eps?1:0;17 }18 19 int n,m;20 21 bool vis[maxn];22 int cnt[maxn];23 int val[maxn];24 double dist[maxn];25 26 struct Edge {27 int v;28 double cost;29 Edge(int _v=0,double _cost=0.0) {30 v=_v;31 cost=_cost;32 }33 };34 35 vector<Edge> edge[maxn];36 37 38 bool SPFA(double rate) {39 memset(vis,0,sizeof(vis));40 memset(cnt,0,sizeof(cnt));41 memset(dist,0,sizeof(dist));42 queue<int> q;43 while(!q.empty())q.pop();44 for(int i=1; i<=n; i++) {45 dist[i]=0;46 vis[i]=1;47 cnt[i]=1;48 q.push(i);49 }50 while(!q.empty()) {51 int u = q.front();52 q.pop();53 vis[u]=false;54 for(int i=0; i<edge[u].size(); i++) {55 int v= edge[u][i].v;56 double w=edge[u][i].cost*rate-val[v];57 if(dist[v]>dist[u]+w) {58 dist[v]=dist[u]+w;59 if(!vis[v]) {60 vis[v]=true;61 q.push(v);62 if(++cnt[v]>n)return false;63 }64 }65 }66 }67 return true;68 }69 70 71 int main() {72 while(~scanf("%d%d",&n,&m)) {73 for(int i=1; i<=n; i++) {74 scanf("%d",&val[i]);75 edge[i].clear();76 }77 for(int i=0; i<m; i++) {78 int u,v;79 double c;80 scanf("%d%d%lf",&u,&v,&c);81 edge[u].push_back(Edge(v,c));82 }83 double left=0;84 double right=1000;85 while(sgn(left-right)<0) {86 double mid=(left+right)/2;87 if(!SPFA(mid)) {88 left=mid;89 } else {90 right=mid;91 }92 }93 printf("%.2f\n",left);94 }95 return 0;96 97 }
（最优比例环）POJ 3621 - Sightseeing Cows
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。