題意:
? ? ? 給你n個城市,m條雙向邊,每條邊有自己的長度和最大運輸量,讓你找到一條時間小于等于T的運輸能力最大的那條路...


思路:
? ? ? 剛開始以為是費用流呢,后來發(fā)現(xiàn)根本不是,因為根本不是在求最優(yōu)和最優(yōu)下的其他最優(yōu),其實這個題目可以二分最大運輸量,每次都根據(jù)二分結果建圖,比如對于當前的mid,枚舉每一條邊,如果當前邊的流量大于等于mid那么就把當前邊連接到圖里,枚舉玩之后跑最短路,看如果1到n的距離小于等于T則滿足,如果滿足 low = mod + 1,ans = mid,如果不滿足則

up = mid - 1.......二分枚舉,建圖,找到答案.

#include<stdio.h> #include<string.h> #include<queue>#define N_node 10000 + 500 #define N_edge 100000 + 10000 #define inf 2000000000 using namespace std;typedef struct {int to ,next ,cost; }STAR;typedef struct {int a ,b ,c ,d; }EDGE;STAR E[N_edge]; EDGE edge[N_edge]; int list[N_node] ,tot; int s_x[N_node];void add(int a ,int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }void SPFA(int s ,int n) {for(int i = 0 ;i <= n ;i ++)s_x[i] = inf;s_x[s] = 0;int mark[N_node] = {0};mark[s] = 1;queue<int>q;q.push(s);while(!q.empty()){int tou ,xin;tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){xin = E[k].to;if(s_x[xin] > s_x[tou] + E[k].cost){s_x[xin] = s_x[tou] + E[k].cost;if(!mark[xin]){mark[xin] = 1;q.push(xin);}}}} }void Buid(int m ,int mid) {memset(list ,0 ,sizeof(list));tot = 1;for(int i = 1 ;i <= m ;i ++)if(edge[i].c >= mid){add(edge[i].a ,edge[i].b ,edge[i].d);add(edge[i].b ,edge[i].a ,edge[i].d);} }bool OK(int T ,int n) {SPFA(1 ,n);return s_x[n] <= T; }int main () {int t ,n ,m ,T;int i ,a ,b ,c ,d;int max;scanf("%d" ,&t);while(t--){scanf("%d %d %d" ,&n ,&m ,&T);max = -1;for(i = 1 ;i <= m ;i ++){scanf("%d %d %d %d" ,&a ,&b ,&c ,&d);if(max < c) max = c;edge[i].a = a;edge[i].b = b;edge[i].c = c;edge[i].d = d;}int low ,mid ,up;low = 0;up = max;int ans = 0;while(low <= up){mid = (low + up) >> 1;Buid(m ,mid);if(OK(T ,n)){low = mid + 1;ans = mid;}elseup = mid - 1;}printf("%d\n" ,ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu1839 二分最短路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。