hdu1839 二分最短路

题意:

给你n个城市,m条双向边,每条边有自己的长度和最大运输量,让你找到一条时间小于等于T的运输能力最大的那条路...

思路:

刚开始以为是费用流呢,后来发现根本不是,因为根本不是在求最优和最优下的其他最优,其实这个题目可以二分最大运输量,每次都根据二分结果建图,比如对于当前的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;

         }

         else

         up = mid - 1;

      }

      printf("%d\n" ,ans);

   }

   return 0;

}

巴特西

hdu1839 二分最短路

最新文章

热门文章