网站建设原理与实践,网站快速开发平台,企业网站新模式,长沙棋牌软件制作开发正题 题目大意
有若干个省#xff0c;每个省有些城市#xff0c;每个省有优惠Xi%X_i\%Xi%#xff0c;若在i省内的道路就优惠Xi%X_i\%Xi%#xff0c;若在i到j省的道路就优惠(Xi%Yi%)2\frac {(X_i\%Y_i\%)}22(Xi%Yi%)#xff0c;求一个区间[L,R][L,R][L,R]边权在…正题 题目大意
有若干个省每个省有些城市每个省有优惠Xi%X_i\%Xi%若在i省内的道路就优惠Xi%X_i\%Xi%若在i到j省的道路就优惠(Xi%Yi%)2\frac {(X_i\%Y_i\%)}22(Xi%Yi%)求一个区间[L,R][L,R][L,R]边权在这个区间内就可以移动。 要求在可以到达终点的情况下
LLL最大。LLL最大的情况下RRR最小。 解题思路
先处理所有边权然后二分LLL之后求是否可以到达找到最大的LLL之后计算最小的RRR。 code
#includecstdio
#includealgorithm
#includequeue
#includecstring
#define M 100010
#define N 50010
using namespace std;
struct line{int from,to;double w;int next;
}a[M*2];
queueint q;
int n,m,x,y,w,tot,ans;
int ls[N],mark[N],h[N],s,t,L,R;
double f[N];
bool v[N];
void addl(int x,int y,double w)
{a[tot](line){x,y,w,ls[x]};ls[x]tot;a[tot](line){y,x,w,ls[y]};ls[y]tot;
}
bool spfa(int up)//SPFA
{q.push(s);v[s]true;for(int i1;ians;i) f[i]2147483647/3;f[s]0;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(a[i].wupmax(a[i].w,f[x])f[y]){f[y]max(a[i].w,f[x]);if(!v[y]){v[y]true;q.push(y);}}}v[x]false;}return !(f[t]2147483647/4);
}
void answer()//二分答案
{while(LR){int mid(LR1)/2;if(spfa(mid)) Lmid;else Rmid-1;}spfa(L);if(f[t]!(int)f[t]) f[t];R(int)f[t];
}
int main()
{//freopen(trip.in,r,stdin);//freopen(trip.out,w,stdout);scanf(%d%d,n,m);for(int i1;im;i){scanf(%d%d%d,x,y,w);addl(x,y,w);Rmax(R,w);}for(int i1;in;i){scanf(%d,t);anst;for(int j1;jt;j){scanf(%d,x);mark[x]i;}}for(int i1;in;i)scanf(%d,h[i]);for(int i1;itot;i)//计算边权{xmark[a[i].from];ymark[a[i].to];a[i].w*(h[x]h[y])/2.0/100.0;}scanf(%d%d,s,t);answer();printf(%d %d\n,L,R);
}
