POJ 3662 Telephone Lines 二分答案+djk


		[cpp] 
/* 
POJ 3662 Telephone Lines 
题意：从1到N修一条电缆，有p对电线杆之间是可以连接的，电信公司可以提供k条电缆，其他的由John提供，求john提供的电缆的最长的那根的长度（ret） 
这应该有很多方案，但是还有一个条件，求所有方案中ret最小的那个 
所以应该让电信公司提供那k跟比较长的，剩下的那些有john提供，然后挑出最长的（长度L），也就是说只要是长度比L长的且在这条路上用到的电缆，那么就应该由电信公司提供。 
 
现在假设john提供的最长的电缆的长度是L，从1到N找出一条路来，使这条路上的长度比L大的电缆的个数不超过k 
（怎么算这个个数？长度大于L的电缆的边权1，john提供的电缆的边权0，然后求最短路就是）， 
那个这就是一个方案，只需尽量的使L小就可以了（二分长度即可求 一个最佳值） 
 
*/  
#include<stdio.h>   
#include<string.h>   
#include<algorithm>   
using namespace std;  
struct edge  
{  
    int a,b,l;  
}bian[10100];  
int map[1010][1010];  
int vis[1010];  
int dist[1010];  
int inf=0x7ffffff;  
bool cmp(struct edge a,struct edge b)  
{  
    return a.l<b.l;  
}  
void build(int l,int n,int p)  
{  
    int i,j;  
    for(i=0;i<=n;++i)  
    {  
        for(j=0;j<=n;++j)  
        {  
            map[i][j]=inf;  
        }  
    }  
      
    for(i=0;i<p;++i)  
    {  
        int a,b;  
        a=bian[i].a;  
        b=bian[i].b;  
        if(bian[i].l<=l)  
        {  
              
            map[a][b]=map[b][a]=0;  
        }else map[a][b]=map[b][a]=1;  
    }  
}  
int xun(int n)//在剩余的节点中寻找到1最近的     
{    
    int xia=-1,i;    
    for(i=1;i<=n;i++)    
        if(vis[i]==0&&(xia==-1||dist[i]<dist[xia]))    
            xia=i;    
        return xia;    
}    
int djk(int n)    
{    
    int i,j,just;    
    for(i=1;i<=n;i++)//初始化     
        dist[i]=map[1][i];    
    memset(vis,0,sizeof(vis));    
    vis[1]=1;    
    for(i=2;i<=n;i++)    
    {    
        just=xun(n);    
        vis[just]=1;//just最近，将他标为已找到最短路径     
        for(j=1;j<=n;j++)//更新剩余的     
            if(vis[j]==0&&dist[j]>dist[just]+map[just][j])    
                dist[j]=dist[just]+map[just][j];    
    }    
    return dist[n];  
}    
int bin(int n,int p,int k)  
{  
    int head,tail;  
    head=0;  
    tail=p-1;  
    int mid;  
    while(head<=tail)  
    {  
        int mid=(head+tail)>>1;  
        build(bian[mid].l,n,p);  
        if(djk(n)<=k)//求出最小的   
        {  
            tail=mid-1;  
        }  
        else head=mid+1;  
    }  
    return head;  
}  
int main()  
{  
    int i,n,p,k;  
    while(scanf("%d%d%d",&n,&p,&k)!=EOF)  
    {  
        for(i=0;i<p;i++)  
        {  
            scanf("%d%d%d",&bian[i].a,&bian[i].b,&bian[i].l);  
        }  
        sort(bian,bian+p,cmp);  
        build(0,n,p);  
        int duan=djk(n);  
        if(duan==inf)  
        {  
            printf("-1\n");  
        }else  
        {  
            if(duan<=k)  
                printf("0\n");  
            else printf("%d\n",bian[bin(n,p,k)].l);  
        }  
    }  
    return 0;  
}

补充：软件开发 , C++ ,