POJ 3662 Telephone Lines(二分答案+SPFA)

【题目链接】 http://poj.org/problem?id=3662

【题目大意】

  给出点,给出两点之间连线的长度,有k次免费连线,

  要求从起点连到终点,所用的费用为免费连线外的最长的长度。

  求最小费用。

【题解】

  二分答案,对于大于二分答案的边权置为1,小于等于的置为0,
  则最短路就是超出二分答案的线数,如果小于等于k,则答案是合法的

【代码】

#include <cstdio>
#include <cstring>
using namespace std;
const int N=200010,inf=~0U>>2,M=200000;
int ans=-1,x,S,T,time[N],q[N],size,h,t,n,m,k,ed,dis[N],in[N],nxt[N],w[N],v[N],g[N],u,e,cost;
void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
bool spfa(int S,int limit){
    for(int i=1;i<=n;i++)dis[i]=inf,in[i]=0,time[i]=0;
    time[S]=1,dis[S]=0,in[S]=1;
    int i,x,size; q[h=t=size=1]=S;
    while(size){
        for(i=g[x=q[h]],h=(h+1)%M,size--;i;i=nxt[i])if(dis[x]+(w[i]>limit?1:0)<dis[v[i]]){
            dis[v[i]]=dis[x]+(w[i]>limit?1:0);
            if(!in[v[i]]){
                time[v[i]]++,t=(t+1)%M,size++,in[q[t]=v[i]]=1;
                if(time[v[i]]>n)return 0;
            }
        }in[x]=0;
    }return dis[T]<=k;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    memset(v,0,sizeof(v)); memset(nxt,0,sizeof(nxt));
    memset(w,0,sizeof(w)); memset(g,0,sizeof(g)); ed=0;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&e,&cost);
        add(u,e,cost);add(e,u,cost);
    }int l=0,r=1000000;T=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(spfa(1,mid)){ans=mid;r=mid-1;}
        else l=mid+1;
    }return printf("%d\n",ans),0;
}

  

时间: 12-27

POJ 3662 Telephone Lines(二分答案+SPFA)的相关文章

POJ 3662 Telephone Lines (二分+Dijkstra: 最小化第k大的值)

题意 Farmer John想从电话公司修一些电缆连接到他农场.已知N个电线杆编号为1,2,?N,其中1号已经连接电话公司,N号为农场,有P对电线杆可连接. 现给出P对电线杆距离Ai,Bi,Li表示Ai和Bi可连接,需要长度为Li的电缆. 电话公司赞助FJ K条免费电缆,额外的支出为剩下所需电缆的最大长度.求出最小费用. 思路 设mid为某条线的长度,长于mid的线放到免费额度里,否则自己掏钱.如果存在一个临界值x,使得长于x的电线数量恰好等于K,这个临界值对应的解就是最优解.如何计算长于mid

POJ 3662 Telephone Lines(二分+最短路)

查看题目 最小化第K大值. 让我怀疑人生的一题目,我有这么笨? 1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 4 #include <vector> 5 #include <functional> 6 using namespace std; 7 #define maxv 1010 8 #define maxl 1000000 9 struct edge 10 { 11 i

POJ 3662 Telephone Lines【Dijkstra最短路+二分求解】

Telephone Lines Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 7214   Accepted: 2638 Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of

poj 3662 Telephone Lines spfa算法的灵活运用

题意: 给一个有n个结点的无向图,要求一条从1到n的路径,你可以让其中的k条免费,这条路径的花费是这条路径上剩下的边中长度的最大值,现在要求花费的最小值. 思路: 这道题可以首先想到二分枚举路径上的最大值,我觉得用spfa更简洁一些.spfa的本质是一种搜索算法,既然是搜索,就涉及到状态的转移.在一般求最短路的spfa算法中,当到结点u时,对e(u,v)只需做如下转移:if(d[v]>d[u]+w(e)) d[v]=d[u]+w(e).在跟一般的情况下,到结点u,对e(u,v)需做多种转移,比如

poj 3662 Telephone Lines(最短路+二分)

Telephone Lines Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6973   Accepted: 2554 Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of

POJ 3662 Telephone Lines (分层图)

Telephone Lines Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6785   Accepted: 2498 Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of

poj 3662 Telephone Lines dijkstra+二分搜索

Telephone Lines Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 5696   Accepted: 2071 Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of

POJ 3662 Telephone Lines (分层图做法)

Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system. There are N (1 ≤ N ≤ 1,000) forlorn t

poj 3662 Telephone Lines(好题!!!二分搜索+dijkstra)

Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system. There are N (1 ≤ N ≤ 1,000) forlorn t