设为首页 加入收藏

TOP

poj 3621 Sightseeing Cows(最优比例生成环，01分数规划)
2015-07-24 07:08:27 来源: 作者: 【大 中 小】 浏览:77次
Tags：poj 3621 Sightseeing Cows 比例 生成 01分数 规划

http://poj.org/problem?id=3621


大致题意：给出一个有向图，每个点都有一个点权，每条有向边也都有一个边权，要求出一个环使得环中点权之和与边权之和的比值最大。


思路：和最优比率生成树异曲同工。设点权是v[i],边权是e[i]。不同的是这里一个是点，一个是边。怎么像生成树一样把这两个值放到一起呢？可以把他们都转化到边上。同样的二分λ，每次给边重新赋权为v[i] - λ*e[i](v[i]是该边终点的点权)。因为要求比值最大，那么在这前提下于图中的所有环都<=0, 所以我们只需每次spfa判断是否有正环，若有说明λ偏小，否则λ偏大。其实每条边的权值取上述(v[i] - λ*e[i])的负值，然后spfa判负环也可以，试了下，时间上差不多。下面的代码判的是负环。


#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
       #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #define LL long long #define _LL __int64 #define eps 1e-7 using namespace std; const _LL INF = 1e18; const int maxn = 1010; struct node { int v; double w; }; vector 
            
              edge[maxn]; int Map[maxn][maxn]; int fun[maxn]; int n,m; bool spfa(double mid) { queue 
             
               que; while(!que.empty()) que.pop(); int inque[maxn],in[maxn]; double dis[maxn]; memset(inque,0,sizeof(inque)); memset(in,0,sizeof(in)); for(int i = 1; i <= n; i++) { que.push(i); dis[i] = 0; in[i] = 1; inque[i] = 1; } while(!que.empty()) { int u = que.front(); que.pop(); inque[u] = 0; for(int i = 0; i < (int)edge[u].size(); i++) { int v = edge[u][i].v; double w = edge[u][i].w * mid - fun[v]; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if(!inque[v]) { inque[v] = 1; que.push(v); in[v]++; if(in[v] > n) return true; } } } } return false; } int main() { while(~scanf("%d %d",&n,&m)) { int u,v,w; for(int i = 1; i <= n; i++) edge[i].clear(); for(int i = 1; i <= n; i++) scanf("%d",&fun[i]); for(int i = 1; i <= m; i++) { scanf("%d %d %d",&u,&v,&w); Map[u][v] = w; edge[u].push_back((struct node){v,w}); } double l = 0.0, r = 1000.0; double mid; while(fabs(r-l) > eps) { mid = (l+r)/2; if(spfa(mid)) l = mid; else r = mid; } printf("%.2f\n",l); } return 0; }


【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：BNUOJ 34982 Beautiful Garden 下一篇：hdu 1016 Prime Ring Problem （d..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: