codevs1183 泥泞的道路

时间限制: 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
3
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

spfa+二分。对于每一个ans,代入原式spfa检查是否满足。跑最长路。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define maxn 105
#define ljt(i,a,b) for(int i=(a);i<=(b);i++)

int P[maxn][maxn],T[maxn][maxn],n;
double W[maxn][maxn],dis[maxn];
bool inq[maxn];
int inv[maxn];
queue <int> que;

int read()
{
    int sum=0;
    char ch=getchar();
    while(!(ch>='0' && ch<='9')) ch=getchar();
    while(ch>='0' && ch<='9') sum=sum*10+ch-'0',ch=getchar();
    return sum;
}

bool spfa()
{
    memset(inv,0,sizeof(inv));
    memset(dis,-0x3f,sizeof(dis));
    memset(inq,0,sizeof(inq));
    que.push(1),dis[1]=0,inq[1]=1,inv[1]=1;
    while(!que.empty())
    {
    int now=que.front();
    que.pop();
    inq[now]=0;
    ljt(i,1,n)
    {
        if(P[now][i] && dis[i]<W[now][i]+dis[now])
        {
        dis[i]=W[now][i]+dis[now];
        if(!inq[i])
        {
            que.push(i);
            inq[i]=1;
            inv[i]++;
            if(inv[i]>n) return 1;
        }
        }
    }
    }
    if(dis[n]>0) return 1;
    return 0;
}

bool slove(double x)
{
    memset(W,0,sizeof(W));
    ljt(i,1,n) ljt(j,1,n) W[i][j]=P[i][j]-x*T[i][j];
    return spfa();
}

double binary()
{
    double mid,l=0,r=100000,ans;
    while(r-l>0.0001)
    {
    mid=(r+l)/2;
    if(slove(mid)) l=mid,ans=mid;
    else r=mid;
    }
    return ans;
}

int main()
{
    n=read();
    ljt(i,1,n) ljt(j,1,n) P[i][j]=read();
    ljt(i,1,n) ljt(j,1,n) T[i][j]=read();
    printf("%.3lf",binary());
    return 0;
}

Codevs 1183 泥泞的路经

codevs1183 泥泞的道路

相关推荐