给一张图,要将1与n连起来.可以有k条边免费,其他边付费,付费的值为所有自费边中最大的值.求最小付费.
可以假定一个付费值m,所有<=m的都自己付费,>m的免费,然后使>m的边数a尽可能小,看是否可以使得a<=k.这里用二分即可.
统计a的最小值时,我们考虑:边分为免费边和自费边,要让免费边数量尽可能小,就把免费边赋值为1,自费边赋值为0,跑最短路,最后d[n]就是最少经过的免费边数量a.
另外,二分的标准如果是0~maxl的话就太大了,我们可以把每一条边的值存在f数组中,然后二分f[0]~f[p],这样会小很多.
注意:
1.如果自费最大费用(不用免费的了),还是不能成功,就输出-1.
1 #include<cstdio> 2 #include<vector> 3 #include<queue> 4 #include<algorithm> 5 using namespace std; 6 7 const int maxn=1005,maxp=10005,INF=1<<27; 8 struct node 9 { 10 int to,w; 11 node(){} 12 node(int a,int b) : to(a),w(b){} 13 bool operator < (const node &a) const { return a.w>w; } 14 }; 15 vector <node> g[maxn]; 16 int n,p,k; 17 int d[maxn],f[maxp]; 18 19 bool Dijkstra(int m) 20 { 21 for(int i=1;i<=n;i++) d[i]=INF; 22 d[1]=0; 23 priority_queue <node> q; 24 q.push(node(1,0)); 25 while(!q.empty()) 26 { 27 int x=q.top().to;q.pop(); 28 for(int i=0;i<g[x].size();i++) 29 { 30 int y=g[x][i].to,dxy=g[x][i].w; 31 dxy=dxy>m ? 1 : 0; 32 if(d[y]>d[x]+dxy) 33 { 34 d[y]=d[x]+dxy; 35 q.push(node(y,d[y])); 36 } 37 } 38 } 39 return (d[n]<=k); 40 } 41 42 void solve() 43 { 44 if(!Dijkstra(f[p])) { printf("-1\n"); return; } 45 int l=0,r=p; 46 while(l<r) 47 { 48 int m=l+(r-l)/2; 49 if(Dijkstra(f[m])) r=m; 50 else l=m+1; 51 } 52 printf("%d\n",f[l]); 53 } 54 55 void init() 56 { 57 scanf("%d%d%d",&n,&p,&k); 58 for(int i=1;i<=p;i++) 59 { 60 int a,b,c; 61 scanf("%d%d%d",&a,&b,&c); 62 g[a].push_back(node(b,c)); 63 g[b].push_back(node(a,c)); 64 f[i]=c; 65 } 66 sort(f+1,f+1+p); 67 } 68 69 int main() 70 { 71 #ifndef ONLINE_JUDGE 72 freopen("phone.in","r",stdin); 73 freopen("phone.out","w",stdout); 74 #endif 75 init(); 76 solve(); 77 #ifndef ONLINE_JUDGE 78 fclose(stdin); 79 fclose(stdout); 80 #endif 81 return 0; 82 } 83
1 #include<cstdio> 2 #include<vector> 3 #include<queue> 4 #include<algorithm> 5 using namespace std; 6 7 const int maxn=1005,maxp=10005,INF=1<<27; 8 struct node 9 { 10 int to,w; 11 node(){} 12 node(int a,int b) : to(a),w(b){} 13 }; 14 vector <node> g[maxn]; 15 int n,p,k; 16 int d[maxn],f[maxp]; 17 bool vis[maxn]; 18 19 bool Spfa(int m) 20 { 21 for(int i=1;i<=n;i++) { d[i]=INF; vis[i]=false; } 22 d[1]=0; vis[1]=true; 23 queue <int> q; 24 q.push(1); 25 while(!q.empty()) 26 { 27 int x=q.front(); 28 q.pop(); 29 vis[x]=false; 30 for(int i=0;i<g[x].size();i++) 31 { 32 int y=g[x][i].to,dxy=g[x][i].w; 33 dxy=dxy>m ? 1 : 0; 34 if(d[y]>d[x]+dxy) 35 { 36 d[y]=d[x]+dxy; 37 if(!vis[y]) 38 { 39 vis[y]=true; 40 q.push(y); 41 } 42 } 43 } 44 } 45 return (d[n]<=k); 46 } 47 48 void solve() 49 { 50 if(!Spfa(f[p])) { printf("-1\n"); return; } 51 int l=0,r=p; 52 while(l<r) 53 { 54 int m=l+(r-l)/2; 55 if(Spfa(f[m])) r=m; 56 else l=m+1; 57 } 58 printf("%d\n",f[l]); 59 } 60 61 void init() 62 { 63 scanf("%d%d%d",&n,&p,&k); 64 for(int i=1;i<=p;i++) 65 { 66 int a,b,c; 67 scanf("%d%d%d",&a,&b,&c); 68 g[a].push_back(node(b,c)); 69 g[b].push_back(node(a,c)); 70 f[i]=c; 71 } 72 sort(f+1,f+1+p); 73 } 74 75 int main() 76 { 77 #ifndef ONLINE_JUDGE 78 freopen("phone.in","r",stdin); 79 freopen("phone.out","w",stdout); 80 #endif 81 init(); 82 solve(); 83 #ifndef ONLINE_JUDGE 84 fclose(stdin); 85 fclose(stdout); 86 #endif 87 return 0; 88 } 89
原文：http://www.cnblogs.com/Sunnie69/p/5424340.html
