本文共 1194 字，大约阅读时间需要 3 分钟。

题意：

给定一个无向有权图，权值代表修建电线需要的花费，公司给报销K条线，这个人需要付款剩下的线路中花费最大的那个线路。

题解：

最短路问题，只不过这时候的最短路不是让求最短的距离了，而是给定一个花费X，是否有一条通路能够满足，恰好有K+1条路满足>=X，这个X就是可行解。二分去求最小的可行解就可以了！

所以这个时候d[]数组放最短距离已经没有任何意义了，而是放到达终点>=X的边数最少有多少条。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int maxl=1000000;int d[1000+5];//“最短距离”，记录大于等于mid的有多少条边！struct edge{int to,cost;};vector
           
            G[1000+5];//边typedef pair
            
             P;//最短路径，顶点编号int V,E,K;//Dijkstra算法。收进来不属于集合的点的时候，不是更新最短路径了，而是更新到达此点共需要>=mid//的边多少条！bool C(int mid){ priority_queue
             
              
,greater
              
 >que; fill(d,d+V+2,0x3f3f3f3f); d[1]=0;//起点 que.push(P(0,1)); while(que.size()) { P p=que.top();que.pop(); int v=p.second; if(d[v]
               
                =mid?1:0);//记录大于等于mid的。 if(d[e.to]>new_d) { d[e.to]=new_d; que.push(P(d[e.to],e.to)); } } } return d[V]>=K+1;//k+1这个边界是最后的可行解！ // 因为>=mid有K+1个说明mid右边刚好有K个免费的，此时的mid就是最优解。 //所以满足这个条件的mid即为答案。}int main(){ cin>>V>>E>>K; for(int i=1;i<=E;i++) { int from,to,cost; cin>>from>>to>>cost; G[from].push_back(edge{to,cost}); G[to].push_back(edge{from,cost}); } int lb=0,ub=maxl+2; while(ub-lb>1) { int mid=(ub+lb)>>1; if(C(mid)) lb=mid; else ub=mid; }cout<<(lb>maxl?-1:lb)<
               
             
            
           
          
         
        
       
      
     
    
   

转载地址：http://iyyci.baihongyu.com/