时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在上一回和上上回里我们知道Nettle在玩《艦これ》，Nettle在整理好舰队之后终于准备出海捞船和敌军交战了。
在这个游戏里面，海域是N个战略点(编号1..N)组成，如下图所示
其中红色的点表示有敌人驻扎，猫头像的的点表示该地图敌军主力舰队(boss)的驻扎点，虚线表示各个战略点之间的航线(无向边)。
在游戏中要从一个战略点到相邻战略点需要满足一定的条件，即需要舰队的索敌值大于等于这两点之间航线的索敌值需求。
由于提高索敌值需要将攻击机、轰炸机换成侦察机，舰队索敌值越高，也就意味着舰队的战力越低。
另外在每一个战略点会发生一次战斗，需要消耗1/K的燃料和子弹。必须在燃料和子弹未用完的情况下进入boss点才能与boss进行战斗，所以舰队最多只能走过K条航路。
现在Nettle想要以最高的战力来进攻boss点，所以他希望能够找出一条从起始点(编号为1的点)到boss点的航路，使得舰队需要达到的索敌值最低，并且有剩余的燃料和子弹。
特别说明：两个战略点之间可能不止一条航线，两个相邻战略点之间可能不止一条航线。保证至少存在一条路径能在燃料子弹用完前到达boss点。
输入
第1行：4个整数N,M,K,T。N表示战略点数量，M表示航线数量，K表示最多能经过的航路，T表示boss点编号, 1≤N,K≤10,000, N≤M≤100,000
第2..M+1行：3个整数u,v,w，表示战略点u,v之间存在航路，w表示该航路需求的索敌值，1≤w≤1,000,000。
输出
第1行：一个整数，表示舰队需要的最小索敌值。
- 样例输入
-
5 6 2 5 1 2 3 1 3 2 1 4 4 2 5 2 3 5 5 4 5 3
- 样例输出
-
3
思路：求所有路径中最短边的最大值。若将所有路径（注意：此时同一个路径和边可能访问多次）遍历一次TLE。
TLE代码：#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN=100005; const int INF=0x3f3f3f3f; struct Edge{ int to,w,net; }es[MAXN]; int n,m,k,ter; int head[MAXN],tot; int vis[MAXN]; int vec[MAXN],top; int res; void addedge(int u,int v,int w) { es[tot].to=v; es[tot].w=w; es[tot].net=head[u]; head[u]=tot++; } void dfs(int dep,int u,int mx) { if(dep>k) return; if(u==ter) { res=min(res,mx); return ; } for(int i=head[u];i!=-1;i=es[i].net) { int v=es[i].to; int w=es[i].w; int mmx=max(mx,w); if(!vis[v]) { vis[v]=1; dfs(dep+1,v,mmx); vis[v]=0; } } } int main() { memset(head,-1,sizeof(head)); scanf("%d%d%d%d",&n,&m,&k,&ter); for(int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } res=INF; dfs(0,1,0); printf("%d ",res); return 0; }
若只求一个最大值或者最小值可尝试采用二分方法求解。
#include <cstdio> #include <cstring> #include <queue> using namespace std; const int MAXN=100005; const int INF=0x3f3f3f3f; struct Edge{ int to,w,net; }es[MAXN+MAXN]; int head[MAXN],tot; int vis[MAXN]; int step[MAXN]; int n,m,k,ter; void addedge(int u,int v,int w) { es[tot].to=v; es[tot].w=w; es[tot].net=head[u];; head[u]=tot++; } bool bfs(int limit) { memset(step,0,sizeof(step)); memset(vis,0,sizeof(vis)); queue<int> que; que.push(1); vis[1]=1; while(!que.empty()) { int u=que.front();que.pop(); if(u==ter) { return true; } for(int i=head[u];i!=-1;i=es[i].net) { int v=es[i].to; if(!vis[v]&&es[i].w<=limit&&step[u]+1<=k) { step[v]=step[u]+1; vis[v]=1; que.push(v); } } } return false; } int main() { memset(head,-1,sizeof(head)); scanf("%d%d%d%d",&n,&m,&k,&ter); for(int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } int l=0,r=INF; while(r-l>1) { int mid=(l+r)>>1; if(bfs(mid)) { r=mid; } else { l=mid; } } printf("%d ",r); return 0; }