POJ - 3662 Telephone Lines-白红宇

POJ - 3662 Telephone Lines

阅读量：5816 次

发布时间：2019-06-18

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

有K根线是免费的。如果最大花费已知为mx，那么长度大于mx的线都是应该是免费的。

线数量表示为d，那么d ≤ K。mx越小，d越大，随着mx增大，可行性：00000111111。这就满足了决策单调性。

把免费的线的权值设置为1，其他为0，判断mx的可行就是1到N是否有一条权值不超过K的路径。

看样例猜题意系列。。。

/**********************************************************            ------------------                          **   author AbyssalFish                                   ***********************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;int N, P, K;const int MAX_P = 2e4, MAX_N = 1e3+1;int hd[MAX_N], nx[MAX_P], le[MAX_P], to[MAX_P], ec;#define eachedge int i = hd[u]; ~i; i = nx[i]void add(int u,int v,int l){ le[ec] = l; to[ec] = v; nx[ec] = hd[u]; hd[u] = ec++;}int d[MAX_N];typedef pair
                  
                    pii;#define dst first#define nd secondpriority_queue
                   
                    
                     ,greater
                     
                       > q;const int INF = 0x3f3f3f3f;bool dijkstra(int mx){ memset(d+1,0x3f,sizeof(int)*N); q.push(pii(d[N] = 0,N)); while(q.size()){ pii x = q.top(); q.pop(); if(x.dst != d[x.nd]) continue; int u = x.nd; for(eachedge){ int v = to[i], l = (le[i]<=mx?0:1); if(d[v] > d[u]+l){ q.push(pii(d[v] = d[u]+l,v)); } } } return d[1]<=K;}int solve(){ if(dijkstra(0)) return 0; if(d[1] >= INF) return -1; int lb = 1e6, ub = 0, md; for(int i = 0; i < ec; i += 2) { lb = min(lb,le[i]); ub = max(ub,le[i]); } while(lb < ub){ md = (lb+ub)>>1; dijkstra(md) ? ub = md: lb = md+1; } return lb;}//#define LOCALint main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif scanf("%d%d%d",&N,&P,&K); memset(hd,-1,sizeof(hd)); for(int i = 0; i < P; i++){ int a,b,l; scanf("%d%d%d",&a,&b,&l); add(a,b,l); add(b,a,l); } printf("%d\n",solve()); return 0;}