JZOJ5771遨游 题解

本文主要是介绍JZOJ5771遨游 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

MWH寒假外出旅游，来到了S国。S国划分为N个省，第i个省有Ti座城市，编号分别为Ci1，Ci2，……CiTi（各省城市编号不会重复）。 所有城市间有M条双向的道路连接，从任意一个城市出发，可到达一切城市，每条道路均须收费。同时，每个省也有优惠措施，第i个省内的每条道路路费收其Xi%，连接第i个省和第j个省的每条道路路费收其(Xi%+Xj%)/2。MWH想从城市s走到城市t，请求出一对L，R，确保：
MWH能免费到达目的地；
L≤R；
L、R均为整数；
L尽可能地大，R在满足L最大的前提下最小。
注意：因每条道路由各省的交通运输局直接管辖，所以每条道路的路费必须先得到省级优惠，再得到国家级优惠。
Input
第一行两个整数N，M。
接下来M行，每行三个整数，u、v、w，表示连接u、v的道路需收费w。
接下来N行，第i+M+1行有一个整数Ti，后面Ti个整数，分别是Ci1..CiTi（所有城市编号保证按正整数顺序给出1.. Ti）。
下一行N个整数X1..Xi。
最后一行，两个整数，s、t。
Output
一行两个整数，如题，L和R。
Sample Input
3 7
1 2 3
5 2 8
1 3 7
5 4 5
2 4 9
3 5 10
3 4 2
2 1 2
1 3
2 4 5
30 50 60
1 5

分析

对于这道题，我们可以现将路况进行处理，然后问题变为从s到t最大最小路程是什么，几乎和[HAOI2006]旅行一样了，我们可以通过枚举最小边，求出最大边，但分析复杂度发现是O(m^2)，会t掉，所以我们换一种思路，对道路进行二分，即通过二分枚举最小道路，从而求出最长道路，这样复杂度就是O(mlog（m）)，这样就可以做了，时间：127ms，空间：2.21mb。
上代码

#include<bits/stdc++.h>
using namespace std;
int n,m,city[50010],sb[5010],cn=0,f[50010],ans1=0,ans2=1<<30,s,t,l=1,r;
struct node{int x,y;double we;
}al[100010];
int find(int x){if(f[x]==x)return x;return f[x]=find(f[x]);
}
bool cmp(node x,node y){return x.we<y.we;
}
int main(){freopen("trip.in","r",stdin);freopen("trip.out","w",stdout);memset(city,0,sizeof(city));memset(sb,0,sizeof(sb));scanf("%d%d",&n,&m);for(int i=1,x,y,z;i<=m;i++)scanf("%d%d%lf",&al[i].x,&al[i].y,&al[i].we);for(int i=1,x;i<=n;i++){scanf("%d",&x);cn+=x;for(int j=1,y;j<=x;j++){scanf("%d",&y);city[y]=i;}}for(int i=1;i<=n;i++)scanf("%d",&sb[i]);scanf("%d%d",&s,&t);for(int i=1;i<=m;i++){if(city[al[i].x]==city[al[i].y])al[i].we=al[i].we*1.0*sb[city[al[i].x]]/100.0;elseal[i].we=al[i].we*1.0*(sb[city[al[i].x]]*1.0+sb[city[al[i].y]]*1.0)/200.0;}sort(al+1,al+1+m,cmp);r=m;while(l<r){int mid=(l+r)/2;for(int i=1;i<=cn;i++)f[i]=i;int i=mid;for(i=mid;i<=m;i++){int fx=find(al[i].x),fy=find(al[i].y);if(fx==fy)continue;f[fx]=fy;if(find(s)==find(t))break;}if(find(s)!=find(t)){r=mid;continue;}else{l=mid+1;int fx=floor(al[mid].we),fy=ceil(al[i].we);if(fx>ans1)ans1=fx,ans2=fy;if(fx==ans1)ans2=min(ans2,fy);}}printf("%d %d",ans1,ans2);return 0;
}

这篇关于JZOJ5771遨游 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---