首页 > 代码库 > [USACO08JAN]电话线Telephone Lines
[USACO08JAN]电话线Telephone Lines
多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着N(1<=N<=1000)根据1……n顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有p(1<=p<=10000)对电话杆可以拉电话线。其他的由于地震使得无法连接。
第i对电线杆的两个端点分别是ai,bi，它们的距离为li(1<=li<=1000000)。数据中每对(ai,bi)只出现一次。编号为1的电话杆已经接入了全国的电话网络，整个市的电话线全都连到了编号N的电话线杆上。也就是说，笨笨的任务仅仅是找一条将1号和N号电线杆连起来的路径，其余的电话杆并不一定要连入电话网络。
电信公司决定支援灾区免费为此市连接k对由笨笨指定的电话线杆，对于此外的那些电话线，需要为它们付费，总费用决定于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过k对，那么支出为0.
请你计算一下，将电话线引导震中市最少需要在电话线上花多少钱？ ——by洛谷（洛谷少有的良心翻译）
https://www.luogu.org/problem/show?pid=1948
《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《
二分答案＋有条件的最短路；
- 二分可能的答案，即对读入的边长sort，然后二分
- 对于每个答案跑SPFA（因为手头有SPFA板子）
- SPFA的松弛为spf[x[i].to]=spf[que[h]]+(x[i].dis>ct?1:0)（ct为二分的答案，意味着如果本边长度大于答案，则让这条边占用公司的名额）
- 若spf[n]>k，则把n连入时不可能以当前答案为答案（因为以当前答案为答案，占用名额一定大于k）
代码如下：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 struct ss 6 { 7 int to,next,dis; 8 }x[20001]; 9 int first[1001];10 int d[10001];11 int que[10000],vis[1001],spf[1001];12 int n,pd,k,num,p;13 void build(int f,int t,int di)14 {15 x[++num].next=first[f];16 x[num].to=t;17 x[num].dis=di;18 first[f]=num;19 }20 void spfa(int ,int );21 int main()22 {23 int i,j,l,r,mid;24 scanf("%d%d%d",&n,&p,&k);25 for(i=1;i<=p;i++)26 {27 scanf("%d%d%d",&j,&l,&d[i]);28 build(j,l,d[i]);29 build(l,j,d[i]);30 }31 sort(d+1,d+p+1);32 l=0;r=p;mid=(l+r)/2;33 while(l<r)34 {35 memset(spf,(0x3f3f3f),sizeof(spf));36 pd=0;37 spfa(1,d[mid]);38 if(pd==1)39 {40 r=mid;41 mid=(l+r)/2;42 }43 else44 {45 l=mid+1;46 mid=(l+r)/2;47 }48 }49 if(r==p&&pd==0)d[r]=-1;50 printf("%d",d[r]);51 return 0;52 }53 void spfa(int s,int ct)54 {55 int h=0,t=1,i;56 spf[s]=0;57 que[t]=s;vis[s]=1;58 while(h<t)59 {60 h++;61 vis[que[h]]=0;62 i=first[que[h]];63 while(i!=0)64 {65 if(spf[x[i].to]>spf[que[h]]+(x[i].dis>ct?1:0))66 {67 spf[x[i].to]=spf[que[h]]+(x[i].dis>ct?1:0);68 if(vis[x[i].to]==0)69 {70 t++;71 que[t]=x[i].to;72 vis[que[t]]=1;73 }74 }75 i=x[i].next;76 }77 }78 if(spf[n]<=k)79 pd=1;80 return ;81 }
祝AC
[USACO08JAN]电话线Telephone Lines
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。