清北学堂2018冬提高精英班NOIP模拟1T2优秀的路径题解

qq设了设备锁没带密保手机orz，所以用这种方式发上来好了.. ------------ 题目： 优秀的路径 小Z渐渐意识到完美的图可遇不可求，于是小Z开始尝试在一般的图中寻找优秀的路径。 小Z拥有一个含有N个节点与M条边的无向图，点的编号从1到N，图上的每一条边都带有一个正的权值。小Z希望找到一条长度在ll到rr范围内（≥ll 且 ≤rr）的从1到N的路径（该路径允许走相同的边多次），使得该路径是所有满足要求的路径当中最优秀的，一条路径的长度指的是该路径上的边数（如果一条边走了多次，则多次计算）。一条路径的优秀值为该路径上的边的权值和与该路径上的边数的比值（同上），优秀值越大，该路径越优秀。 小Z想要知道最优秀的路径的优秀值。 输入格式： 第一行四个正整数表示N,M,ll,rr(若rr不为正整数,则为-1)。当rr为-1时，表示所要求的路径的长度没有上限要求。 接下来M行，每行三个正整数x y z,表示x与y之间有一条权值为z的边。 输出格式： 一行一个实数表示答案，保留两位小数。若不存在方案，输出-1. 输入样例： 3 2 3 -1 1 2 5 2 3 3 输出样例： 5.00 数据规模： 对于30%的数据，保证N<=5,M<=5. 对于另外10%的数据，保证rr=-1. 对于100%的数据，保证N<=100,M<=200,ll,rr<=1000,z<=1000. ------------ 解析： 没仔细看标程的二分..直接dp就可以AC，时间和标程几乎一样，只不过标程复杂度貌似低一些..1000以内的数据就不用管这么多了 f(i,j)表示从i到n经过j条边的所有路径中最大的总权值，-1表示无法到达 j==0时f(n,0)=0,f(i,0)=-1 j!=0时f(i,j)=对于所有在边集中的(i,k)且f(k,j-1)!=-1，最大的f(k,j-1)+w[i][k] 意思就是从i出发的边中能到达n的最大总权值 max(f(1,∀j∈[ll,rr]))就是答案 还有注意rr=-1的特判（标程写错了233） 对于任何与1和n都连通的边，因为经过边数不限，所以可以在这条边上反复摩擦（不要在意用词），所以问题转变成求一条最大边权最大的从1到n的路径 不能直接找最大边权（标程就这样写的，所以80），因为那条边可能不与1、n连通 我是用的Floyd，因为Dijkstra貌似不行..而且数据很小，n³完全可以接受，写起来还简单 其它部分就是那三个循环，只是把最短边权和改成最大最大边权（真的没有打重）：if (w[i][k]&&w[k][j]) w[i][j]=max(w[i][j],max(w[i][k],w[k][j]));} ------------ 我的代码： ``` #include <fstream> #include <cstring> #include <algorithm> using namespace std; ifstream fin("roadbig.in"); ofstream fout("road.out"); int n,m,ll,rr; int f[110][1010],w[110][110]; int main() { int i,j,k=0,x,y,z; fin>>n>>m>>ll>>rr; for (i=0;i<m;++i) { fin>>x>>y>>z; w[x][y]=w[y][x]=max(w[x][y],z); } if (rr==-1) { for (k=1;k<=n;++k) { for (i=1;i<=n;++i) { for (j=1;j<=n;++j) { if (w[i][k]&&w[k][j]) { w[i][j]=max(w[i][j],max(w[i][k],w[k][j])); } } } } if (w[1][n]==0) { fout<<-1; //提交的时候没写这个..幸好没有这么恶心的数据 } else { fout<<w[1][n]<<".00"; } } else { double ans=-1; memset(f,-1,sizeof(f)); f[n][0]=0; for (j=1;j<=rr;++j) { for (i=1;i<=n;++i) { for (k=1;k<=n;++k) { if (w[i][k]&&f[k][j-1]!=-1) { f[i][j]=max(f[i][j],f[k][j-1]+w[i][k]); } } } if (j>=ll) { ans=max(ans,double(f[1][j])/j); } } if (ans<0) { fout<<-1; } else { fout.setf(ios_base::fixed); fout.precision(2); fout<<ans; } } } ``` ------------ 80分的标程： ``` #include <bits/stdc++.h> using namespace std; const int maxn=200+15; int n,m,ll,rr; int xx[maxn],yy[maxn],zz[maxn]; double ww[maxn]; double f[1005][maxn]; bool check(double x) { for (int i=1;i<=m;i++) ww[i]=zz[i]-x; double oo=-x*rr-2*x; for (int i=0;i<=rr;i++) for (int j=1;j<=n;j++) f[i][j]=oo; f[0][1]=1e-8; for (int i=1;i<=rr;i++) { for (int j=1;j<=m;j++) { if (f[i-1][xx[j]]>-x*rr-x) f[i][yy[j]]=max(f[i][yy[j]],f[i-1][xx[j]]+ww[j]); if (f[i-1][yy[j]]>-x*rr-x) f[i][xx[j]]=max(f[i][xx[j]],f[i-1][yy[j]]+ww[j]); } if (i>=ll) if (f[i][n]>0) return true; } return false; } int main() { freopen("road.in","r",stdin); freopen("road.out","w",stdout); scanf("%d%d%d%d",&n,&m,&ll,&rr); int maxx=0; for (int i=1;i<=m;i++) { scanf("%d%d%d",&xx[i],&yy[i],&zz[i]); maxx=max(maxx,zz[i]); } if (rr==-1) { printf("%.2lf\n",maxx); return 0; } if (ll>rr) { printf("-1\n"); return 0; } double l=0,r=1001,midd; while (l+1e-5<r) { midd=(l+r)/2; if (check(midd)) l=midd; else r=midd; } printf("%.2lf\n",l); return 0; } ``` P.S.（最？）优解应该是dp+Bellman-Ford，不用二分