题解 P1730 【最小密度路径】

· · 题解

题目描述

给出一张有N个点M条边的加权有向无环图，接下来有Q个询问，每个询问包括2个节点X和Y，要求算出从X到Y的一条路径，使得密度最小（密度的定义为，路径上边的权值和除以边的数量）。 1 ≤ N ≤ 50，1 ≤ M ≤ 1000，1 ≤ W ≤ 100000，1 ≤ Q ≤ 100000

题目分析

首先看数据范围，我们发现n的值很小，那我们就可以直接dfs爆搜，时间复杂度为O（n^2）;

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int q;
struct node
{
    int ver;
    int next;
    int val;
}e[100004];
int h[10005],cnt=0;
double dis[55][55];//dis[x][y]表示从x到y的最小密度; 
void add(int u,int v,int w)
{
    e[++cnt].ver=v;
    e[cnt].val=w;
    e[cnt].next=h[u]; 
    h[u]=cnt;
}
void dfs(int x,double c,double t,int k)//c为权值，t为走过的边数; 
{
    dis[k][x]=min(dis[k][x],c/t);
    for(int i=h[x];i;i=e[i].next)
    {
        int y=e[i].ver;
        dfs(y,c+e[i].val,t+1,k);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);}
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dis[i][j]=5000000.000;//赋初值; 
        }
        dis[i][i]=0;//自己到自己的距离为0; 
    }
    for(int i=1;i<=n;i++)
    {
        dfs(i,0,0,i);
    }
    scanf("%d",&q);
    while(q--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(dis[x][y]==5000000.000) printf("OMG!\n");//如果dis[x][y]仍等于初值，则表示x与y不连通; 
        else printf("%.3lf\n",dis[x][y]);
    }
}