codevs1183泥泞的道路

题意：给定一张有向稠密图和通过每条边的时间和路程，问从1到n的路程/时间最大为多少

正解：SPFA+二分答案

开始做的时候，想直接跑图论，后来发现好像不对（不然数据范围怎么这么小）

但是显然要用到图论，机智的我就想到了二分答案。

考虑，假如有一个ans,那么如果存在length i / time i >=ans(i属于路径上的边),那么显然更优 ,则可发现问题可转换为如果一个答案更优,那么对于以 length i - ans*time i 为权值,重新构的图中,如果到达n的最长路不小于n,显然答案可以更优,只需要二分答案就可以了.另外如果有正权环显然是可以的

唯独要注意的是，精度要求要满足题意，显然不能只分到第三位小数就停了，那样的话会gi

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

const int MAXN = ;

int n;

int tim[MAXN][MAXN],s[MAXN][MAXN];

long double ju[MAXN][MAXN];

double dis[MAXN];

bool vis[MAXN];

int num[MAXN];//记录经过次数，判环

long double ans;

//二分答案+SPFA

queue<int>q;

inline int getint()

{

       int w=,q=;

       char c=getchar();

       while((c<'' || c>'') && c!='-') c=getchar();

       if (c=='-')  q=, c=getchar();

       while (c>='' && c<='') w=w*+c-'', c=getchar();

       return q ? -w : w;

}

inline bool work(long double x){//跑最长路径

    for(int i=;i<=n;i++) dis[i]=-0x7ffffff;//置为更小的负值

    // memset(dis,0,sizeof(dis));

    ans=x;

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

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

        ju[i][j]=s[i][j]-x*tim[i][j];

    memset(vis,,sizeof(vis));

    memset(num,,sizeof(num));

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

    q.push(); vis[]=; dis[]=;

    while(!q.empty()) {

    int u=q.front();

    q.pop(); vis[u]=;

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

        if(i!=u){

        if(dis[i]<dis[u]+ju[u][i]) {

            dis[i]=dis[u]+ju[u][i];

            if(!vis[i]) {

            vis[i]=;

            q.push(i);

            num[i]++;

            if(num[i]>=n) return true;

            }

        }

        }

    }

    if(dis[n]>=) return true;//存在更优的答案

    return false;

}

int main()

{

    n=getint();

    for(int i=;i<=n;i++) for(int j=;j<=n;j++) s[i][j]=getint();

    for(int i=;i<=n;i++) for(int j=;j<=n;j++) tim[i][j]=getint();

    long double l=0.00,r=10000.00;

    //long double jingdu=0.00001;

    long double jingdu=0.0001;

    while(r-l-jingdu>=) {

    long double mid=l+(r-l)/2.0;

    if(work(mid)) l=mid;

    else r=mid;

    }

    printf("%.3lf",(double)l);

    return ;

}

巴特西

codevs1183泥泞的道路

最新文章

热门文章