P2269 高质量的数据传输

licn · 2023-08-23 21:56:13 · 题解

题目分析：

本题是在最短路的基础上多维护了一个路径，我们正常去做最短路。

做法：

用 spfa 去跑最短路，由于需要维护最少丢失率，我们可以维护最大剩余率，最后用 1 减，可以保证精度。当丢失率相等时再去判断一下延时长短。

切记：丢失率可能是 0 存图的时候注意不要特判是 0 时不存。（本人栽了）

spfa：当一个点的最优值被更新时，那么需要更新与它相连的点。如果需要去更新的点已在队列里不必再入队。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=310;
const double eps=1e-6;
int n,l,r,t[N][N],head[N],tot;
double loss[N][N];
struct node
{
    int next,to,dis2;
    double dis1;//dis1[]剩余率，dis2[]延时
}edge[N*N];
void read(int from,int to,double dis1,int dis2)
{
    tot++;
    edge[tot].to=to;
    edge[tot].dis1=dis1;
    edge[tot].dis2=dis2;
    edge[tot].next=head[from];
    head[from]=tot;
}
void spfa()
{
    double ans1[N]={0};//剩余率
    int ans2[N]={0},v[N]={0};//ans2[]延时，v[]标记是否在队列里
    ans1[l]=1,v[l]=1;
    queue<int>q;
    q.push(l);
    while(q.size())
    {
        int x=q.front();
        q.pop();
        v[x]=0;
        for(int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to;
            if(ans1[x]*edge[i].dis1>ans1[y])
            {
                ans1[y]=ans1[x]*edge[i].dis1;
                ans2[y]=ans2[x]+edge[i].dis2;
                if(v[y]==0)q.push(y),v[y]=1; //如果已经在队列里不必再次入队
            }
        }
    }
    printf("%d %.4lf",ans2[r],1-ans1[r]);
}
int main(){
    scanf("%d%d%d",&n,&l,&r);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&t[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%lf",&loss[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(t[i][j]!=-1&&loss[i][j]!=-1)
                read(i,j,1-loss[i][j],t[i][j]),read(j,i,1-loss[i][j],t[i][j]);
    spfa();
    return 0;
}