思路:最短路+SPFA+二分查找
分析:
1 题目要求的是在限制时间t之内,最大的容量。而题目说了最大的容量就是路径上的最小的边值。
2 这里加了一个容量,而且是要求一条边的最短。所以这里用到了二分,因为我们知道随着边长的增大能够满足的路径越来越少,所以我们只要去枚举容量即可。
代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> using namespace std; #define MAXN 110010 #define INF 0x7FFFFFFF int cnt , n , m , t; int first[MAXN] , next[MAXN]; int star[MAXN] , end[MAXN]; int value[MAXN] , Time[MAXN]; int dis_Time[MAXN]; int vis[MAXN]; queue<int>q; void init(){ memset(first , -1 , sizeof(first)); memset(next , -1 , sizeof(next)); } void SPFA(int s){ memset(vis , 0 , sizeof(vis)); for(int i = 2 ; i <= n ; i++) dis_Time[i] = INF; dis_Time[1] = 0; q.push(1); vis[1] = 1; while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 0; for(int i = first[x] ; i != -1 ; i = next[i]){ if(dis_Time[end[i]] > dis_Time[x] + Time[i] && s <= value[i]){/*这里加了一个边长都要大于s*/ dis_Time[end[i]] = dis_Time[x] + Time[i]; if(!vis[end[i]]){ vis[end[i]] = 1; q.push(end[i]); } } } } } int main(){ scanf("%d" , &cnt); while(cnt--){ scanf("%d%d%d" , &n , &m , &t); init(); for(int i = 0 ; i < m ; i++){ scanf("%d%d%d%d" , &star[i] , &end[i] , &value[i] , &Time[i]); star[i+m] = end[i] , end[i+m] = star[i]; value[i+m] = value[i] , Time[i+m] = Time[i]; next[i] = first[star[i]]; first[star[i]] = i; next[i+m] = first[star[i+m]]; first[star[i+m]] = i+m; } /*二分最短路*/ int tmp_value[MAXN]; memcpy(tmp_value , value , sizeof(tmp_value)); sort(tmp_value , tmp_value+m); int left , right , mid , ans; left = 0 , right = m-1; /*二分查找的形式*/ while(left <= right){ mid = (right+left)/2; SPFA(tmp_value[mid]); if(dis_Time[n] <= t)/*满足条件还要继续二分,因为不是最大*/ ans = tmp_value[mid] , left = mid + 1; else right = mid - 1; } printf("%d\n" , ans); } return 0; }