`

POJ 3621 Sightseeing Cows ((二分+spfa求回路 | 最优比率环)

阅读更多
Sightseeing Cows
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 6758   Accepted: 2234

Description

Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows must decide how best to spend their free time.

Fortunately, they have a detailed city map showing the L (2 ≤ L ≤ 1000) major landmarks (conveniently numbered 1.. L) and the P (2 ≤ P ≤ 5000) unidirectional cow paths that join them. Farmer John will drive the cows to a starting landmark of their choice, from which they will walk along the cow paths to a series of other landmarks, ending back at their starting landmark where Farmer John will pick them up and take them back to the farm. Because space in the city is at a premium, the cow paths are very narrow and so travel along each cow path is only allowed in one fixed direction.

While the cows may spend as much time as they like in the city, they do tend to get bored easily. Visiting each new landmark is fun, but walking between them takes time. The cows know the exact fun values Fi(1 ≤ Fi ≤ 1000) for each landmark i.

The cows also know about the cowpaths. Cowpath i connects landmark L1i to L2i (in the direction L1i -> L2i ) and requires time Ti (1 ≤ Ti ≤ 1000) to traverse.

In order to have the best possible day off, the cows want to maximize the average fun value per unit time of their trip. Of course, the landmarks are only fun the first time they are visited; the cows may pass through the landmark more than once, but they do not perceive its fun value again. Furthermore, Farmer John is making the cows visit at least two landmarks, so that they get some exercise during their day off.

Help the cows find the maximum fun value per unit time that they can achieve.

Input

* Line 1: Two space-separated integers: L and P
* Lines 2..L+1: Line i+1 contains a single one integer: Fi
* Lines L+2..L+P+1: Line L+i+1 describes cow path i with three space-separated integers: L1i , L2i , and Ti

Output

* Line 1: A single number given to two decimal places (do not perform explicit rounding), the maximum possible average fun per unit time, or 0 if the cows cannot plan any trip at all in accordance with the above rules.

Sample Input

5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2

Sample Output

6.00

Source

【题目大意】
给出一个有向图,问求一个回路,使得回路上的点权之和/边权之和 最大。
【解题思路】
此题是对01分数规划的应用,那么首先明白01分数规划的思想.
01整数规划问题就是求解方程(a1*x1+a2*x2+..+an*xn)/(b1*x1+b2*x2+..+bn*xn)的最小值/最大值问题。其中xi = 0或1(i=1,2...n)
对于此类问题我们可以通过二分来求解很接近答案的近似值。我们可以先令:
(a1*x1+a2*x2+..+an*xn)/(b1*x1+b2*x2+..+bn*xn)=L,则我们可以将此式转换为:x1*(a1-b1*L)+x2*(a2-b2*L)+...xn*(an-bn*L)=0,我们先定义一个估计值val,如果这个值使得上面的式子小于0我们就可以知道val>L,如果上式等于0,则val = L;如果大于0,则val<L,显然我们可以采用二分的思想求解次问题。
对于此题,设happy[u]为点u的欢乐值,w[u][v]为u-->v的边权值。要求的是happy[1]+happy[2]+...+happy[n] / w[1][2]+...+w[n-1][n] = ans,设ans就是所求的最大值。则移项,ans*w[u][v] - happy[v]  = 0 .我们重新构造一幅图,使得边权为happy[v] - ans*w[u][v]。用SPFA算法,二分枚举ans,判断是否存在负权回路,若存在,说明ans偏小了,则增大ans,若不存在,则减小ans。
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int VM=1010;
const int EM=5010;
const int INF=0x3f3f3f3f;

struct Edge{
    int to,nxt;
    int cap;
}edge[EM<<1];

int n,m,cnt,head[VM];
int happy[VM],vis[VM],count[VM];
double dis[VM];

void addedge(int cu,int cv,int cw){
    edge[cnt].to=cv;    edge[cnt].cap=cw;   edge[cnt].nxt=head[cu];
    head[cu]=cnt++;
}

int SPFA(double mid){
    queue<int> q;
    while(!q.empty())
        q.pop();
    for(int i=1;i<=n;i++){
        dis[i]=INF;
        vis[i]=0;
        count[i]=0;
    }
    dis[1]=0;
    q.push(1);
    vis[1]=1;
    count[1]++;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].nxt){
            int v=edge[i].to;
            double newdis=mid*edge[i].cap-happy[v];      //新的边权值
            if(dis[v]>dis[u]+newdis){
                dis[v]=dis[u]+newdis;
                if(!vis[v]){
                    vis[v]=1;
                    count[v]++;
                    q.push(v);
                    if(count[v]>=n)     //有负权环路
                        return 0;
                }
            }
        }
    }
    return 1;   //无负权环路
}

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d%d",&n,&m)){
        cnt=0;
        memset(head,-1,sizeof(head));
        for(int i=1;i<=n;i++)
            scanf("%d",&happy[i]);
        int u,v,w;
        while(m--){
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
        }
        double l=0,r=10000,ans=0,mid;
        while(r-l>=1e-8){
            mid=(l+r)/2;
            if(SPFA(mid))
                r=mid;
            else{     //有负权环路
                ans=mid;
                l=mid;
            }
        }
        printf("%.2f\n",ans);
    }
    return 0;
}
 
分享到:
评论

相关推荐

    POJ2186-Popular Cows【Tarjan+极大强连通分量+缩点】

    POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573

    poj 2430 Lazy Cows.md

    poj 2430 Lazy Cows.md

    poj模拟题(二分查找)

    通过不断调整二分查找的范围,最终能够找到最优的分配方案。 综上所述,这三道题都强调了二分查找算法的运用,尤其是二分查找在解决优化问题上的应用,如最大化最小值和最小化最大值问题。在实际编程竞赛或者算法...

    POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】

    《POJ3009-Curling 2.0:深度优先搜索、向量、回溯与剪枝的综合应用》 北京大学在线编程平台上的POJ3009题目名为"Curling 2.0",它是一道涉及到算法与数据结构的复杂问题,主要考察了参赛者对深度优先搜索(DFS)、...

    ACM常用算法及其相应的练习题.docx

    * 最优二分检索树问题 六、数学 * 组合数学: + 加法原理和乘法原理 + 排列组合 + 递推关系 - poj3252, poj1850, poj1019, poj1942 * 数论: + 素数与整除问题 + 进制位 + 同余模运算 - poj2635, poj...

    西北工业大学POJ试题C++答案代码+课程设计

    "西北工业大学POJ试题C++答案代码+课程设计"这一标题表明了资源的主要内容,涉及两个核心部分:一是西北工业大学的编程竞赛(POJ,Problem Oriented Judge System)的C++解题代码,二是与这些题目相关的课程设计。...

    poj题目分类

    * 哈希表和二分查找等高效查找法:例如 poj3349、poj3274、poj2151、poj1840、poj2002、poj2503。 * 哈夫曼树:例如 poj3253。 * 堆:例如 poj2513。 * trie 树:例如 poj2513。 4. 简单搜索: * 深度优先搜索...

    POJ算法题目分类

    * 哈希表和二分查找等高效查找法:哈希表和二分查找等高效查找法是指解决问题的高效查找算法,如 poj3349、poj3274、POJ2151、poj1840、poj2002、poj2503。 * 哈夫曼树:哈夫曼树是指解决问题的哈夫曼树算法,如 poj...

    POJ1207-The 3n + 1 problem

    此外,对于大型数据,还可以考虑使用更高效的数据结构和算法优化,例如二分查找、位运算等。然而,对于POJ1207的规模,上述的简单动态规划方法已经足够高效。 总的来说,解答《POJ1207-The 3n + 1 problem》不仅...

    POJ3733-Changing Digits【DFS+强剪枝】

    【标题】"POJ3733-Changing Digits【DFS+强剪枝】"是一个来自北京大学在线评测系统POJ的编程题目,该题目主要涉及深度优先搜索(DFS)算法和强剪枝策略。在算法竞赛和编程挑战中,这类问题通常要求参赛者通过编写...

    北大POJ初级-所有题目AC代码+解题报告

    【标题】"北大POJ初级-所有题目AC代码+解题报告" 涉及的知识点主要集中在编程、算法和在线判题系统方面。北京大学(Peking University, 简称PKU)的POJ(Peking University Online Judge)是一个为计算机科学爱好者...

    POJ3026-Borg Maze【BFS+Prim】

    《POJ3026-Borg Maze:BFS与Prim算法的应用解析》 在计算机科学领域,图论是解决问题的重要工具之一,而BFS(广度优先搜索)和Prim算法则是其中的两种经典算法。本篇文章将围绕北大POJ3026题目“Borg Maze”来探讨...

    acm 题目汇总(好东西)

    POJ 3621 "Sightseeing Cows" 考虑的是寻找环路,需要用到参数搜索和最短路算法的组合。连通性问题,如POJ 1236 "Network of Schools" 和 POJ 1659 "Frogs' Neighborhood",则通常需要DFS(深度优先搜索)和缩点技巧...

    poj各种分类

    包括最长公共子序列、最优二分检索树等问题,关键在于状态转移方程的设计。 ### 六、数学 #### 组合数学 涵盖加法原理、乘法原理、排列组合等,用于解决计数问题,如poj3252。 #### 数论 涉及素数检测、整除性、...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...

    POJ3373-Changing Digits【DFS+强剪枝】

    标题“POJ3373-Changing Digits【DFS+强剪枝】”涉及的是一个编程竞赛中的问题,这个问题在北大POJ(北京大学在线评测系统)平台上被提出。"Changing Digits"是一个算法挑战,而解决方案是通过深度优先搜索(DFS)...

    强大的poj分类

    **简介**:基础算法是算法学习的基础,主要包括排序算法(如冒泡排序、选择排序、插入排序、归并排序、快速排序)、查找算法(如顺序查找、二分查找)、数学算法(如质数判断、最大公约数计算)等。 **重要性**:...

    Poj中的一些题目源代码

    7. **P2728(最优比率生成树).cpp** - 最优比率生成树问题涉及找到一棵树,使得树中所有边的权值之比的几何平均值最大。这可能涉及到图论和动态规划。 8. **P2486.cpp** - 又一个未提供具体描述的题目,可能需要...

    poj图论题目汇总

    - **知识点**:二分匹配是解决一类特定问题的有效算法,特别是当问题可以被建模为一个二分图时尤为有效。 - **二分图**:一种特殊的图,其中顶点可以被分为两个不相交的集合,每条边都连接两个不同集合中的顶点。 ...

Global site tag (gtag.js) - Google Analytics