poj 3662 二分最短路（建模与转化）

二分给出的p条边，把大于的都当做电信赠送的线路，小于等于的都当做农夫自己买的线路。

前者权值设为1，后者权值设为0，则最短路跑出来的结果和k值比较就知道是否满足，继续二分。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   #define eps 1e-6 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define ll long long #define lson l,m,(rt<<1) using namespace std; #include
                  
                    #include
                   
                     #include
                    
                      using namespace std; int n; int v[1024],path[1024]; int map[1024][1024],dis[1024]; int p,k; int Dijkstra(int s) { int i,j; for(i=1;i<=n;i++) { v[i]=0; dis[i]=map[s][i]; } dis[s]=0; for(i=1;i<=n;i++) { int min=10000000; int pos=0; for(j=1;j<=n;j++) { if(!v[j] ) if(dis[j]
                     
                      1000000) { printf("-1\n"); continue; } int l=1,r=p,mid; int ans; while(l<=r) { mid=(l+r)>>1; build(ve[mid].d); if(Dijkstra(1)<=k) {ans=mid;r=mid-1;} else l=mid+1; } printf("%d\n",ve[ans].d); } return 0; }