题解 P1730 【最小密度路径】

最近$01$分数规划的题目做多了，看到这题下意识码了$SPFA+$二分，才看到$DAG$。 $SPFA+$二分也可以做这道题嘛。 这道题询问$10^5$然而本质不同的只有$n^2$个。 所以把询问打个表，最后查表输出。 从大佬那里听来，$DAG$上$SPFA$好像只能卡到$max(N^2,kM)$(~~错了别喷~~),所以直接大力$SPFA+01$分数规划做$N^2$次,复杂度也就$O(n^4log(?))$,还是可以过的。 $01$分数规划什么的还是老套路。 考虑对于询问$(from,to)$,显然可以二分答案(具有单调性)。 猜测答案为$limit$,则$limit$小于等于任何的可行解。 $\sum{W[i]}/\text{边数}>=limit$ $\sum{W[i]}/(\text{边数}*limit)>=1$ $\sum{W[i]}>=(\text{边数}*limit)$ $\sum{W[i]}-(\text{边数}*limit)>=0$ $\sum{(W[i]-limit)}>=0$ 也就是说$limit$为合发解可以通过在一个边权为$(W[i]-limit)$的新图上跑最短路，$(from,to)$的距离小于等于0来检验。 然后还有个小优化。 对于每次二分的$check$,我们都跑了一次单源最短路，但是只利用了其中的一个信息，未免浪费。 我们可以利用这些信息，在二分的边界上做手脚(不知道如何描述，还是看代码吧)。 不知道卡掉的是常数还是复杂度，反正跑的挺快。 ~~另外，我判断无解的方式有点令人无语~~ **Code:** ```cpp #include<algorithm> #include<cstdio> #include<vector> #include<queue> #define eps 1e-5 using namespace std; vector<int> g[55],l[55]; int n,m,from,to,len,q; double ans[55][55],ll[55][55],rr[55][55],s[55]; queue<int> t; bool in[55]; /* 假设ans>=limit 则sum(len)/sum(cnt) >= limit sum(len)/(sum(cnt)*limit) >= 1 sum(len) >= sum(cnt)*limit sum(len)-sum(cnt)*limit >= 0 sum(len-limit) > 0 */ bool check(int from,int to,double limit) { for (int i=1;i<=n;i++)s[i]=1e15; s[from]=0;t.push(from);in[from]=1; while(!t.empty()){ int u=t.front(); in[u]=0; t.pop(); for (int i=0,v;i<g[u].size();i++) if (s[v=g[u][i]]>s[u]+l[u][i]-limit+eps){ s[v]=s[u]+l[u][i]-limit; //注意这里边权 if (!in[v]){in[v]=1;t.push(v);} } }s[from]=1e15; //SPFA,没啥好看的 for (int i=1;i<=n;i++) if (s[i]<eps)rr[from][i]=min(rr[from][i],limit); else ll[from][i]=max(ll[from][i],limit); //在这里做了手脚 return s[to]<eps; } void getans(int from,int to) { if (!check(from,to,1e6))return ; //判断无解 double l=ll[from][to],r=rr[from][to],mid; while(r-l>eps){ mid=(l+r)/2; if (check(from,to,mid))r=mid; else l=mid; }ans[from][to]=l; //01分数规划 } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++){ scanf("%d%d%d",&from,&to,&len); g[from].push_back(to); l[from].push_back(len); } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){ ll[i][j]=0;rr[i][j]=100500; ans[i][j]=2.333333333; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i!=j)getans(i,j); scanf("%d",&q); for (int i=1;i<=q;i++){ scanf("%d%d",&from,&to); if (2.33333333<ans[from][to]&&ans[from][to]<2.33333334) puts("OMG!"); else printf("%.3lf\n",ans[from][to]); } return 0; } ``` ~~Orz比各位dp的巨佬慢多了~~