codevs1183 泥泞的道路(01分数规划)

1183 泥泞的道路

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 Description

CS有n个小区，并且任意小区之间都有两条单向道路（a到b，b到a）相连。因为最近下了很多暴雨，很多道路都被淹了，不同的道路泥泞程度不同。小A经过对近期天气和地形的科学分析，绘出了每条道路能顺利通过的时间以及这条路的长度。

现在小A在小区1，他希望能够很顺利地到达目的地小区n，请帮助小明找出一条从小区1出发到达小区n的所有路线中（总路程/总时间）最大的路线。请你告诉他这个值。

输入描述 Input Description

第一行包含一个整数n，为小区数。

接下来n*n的矩阵P，其中第i行第j个数表示从小区i到小区j的道路长度为Pi,j。第i行第i个数的元素为0，其余保证为正整数。

接下来n*n的矩阵T，第i行第j个数表示从小区i到小区j需要的时间Ti,j。第i行第i个数的元素为0，其余保证为正整数。

输出描述 Output Description

写入一个实数S，为小区1到达n的最大答案，S精确到小数点后3位。

样例输入 Sample Input

0 8 7

9 0 10

5 7 0

0 7 6

6 0 6

6 2 0

样例输出 Sample Output

2.125

数据范围及提示 Data Size & Hint

【数据说明】

30%的数据，n<=20

100%的数据，n<=100，p,t<=10000

/*

01分数规划

总路程/总时间=平均速度

可以二分v,建图spfa最长路 判断S总-v*T总=0为最优解,>0当前v满足。

若有正权回路则当前v一定满足(求最长路可以判正环)。

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define N 1001

#define inf 0x3f3f3f3f

using namespace std;

int n,m,ans,cnt,flag;

int s[N][N],t[N][N],in[N];

double dis[N][N],d[N];

bool inq[N];

queue<int>q;

void clear()

{

    memset(inq,,sizeof inq);

    while(!q.empty()) q.pop();

    memset(in,,sizeof in);

    for(int i=;i<=n;i++) d[i]=-inf;

}

bool spfa(int u)

{

    clear();

    q.push(u);inq[u]=;d[u]=;in[u]=;

    while(!q.empty())

    {

        int now=q.front();q.pop();

        inq[now]=; in[now]++;

        if(in[now]>=n) return true;

        for(int i=;i<=n;i++)

        {

             if(i==now) continue;

            if(d[i]<d[now]+dis[now][i] && s[now][i])

            {

                d[i]=d[now]+dis[now][i];

                if(!inq[i]) q.push(i),inq[i]=;

            }

        }

    }return d[n]>;

}

bool check(double x)

{

    for(int i=;i<=n;i++) for(int j=;j<=n;j++)

    dis[i][j]=s[i][j]-t[i][j]*x;

    return spfa();

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++) for(int j=;j<=n;j++)

    scanf("%d",&s[i][j]);

    for(int i=;i<=n;i++) for(int j=;j<=n;j++)

    scanf("%d",&t[i][j]);

    double eps=0.00001,l=,r=;

    while(r-l>eps)

    {

        double mid=(l+r)/;

        if(check(mid)) l=mid;

        else r=mid;

    }

    printf("%.3lf\n",l);

}

巴特西

codevs1183 泥泞的道路(01分数规划)

1183 泥泞的道路

最新文章

热门文章