首页 > 代码库 > TopCoder SRM 642 Div.2 1000 --二分+BFS
TopCoder SRM 642 Div.2 1000 --二分+BFS
题意： 给你一张图，N个点(0~N-1),m条边，国王要从0到N-1，国王携带一个值，当走到一条边权大于此值的边时，要么不走，要么提升该边的边权，提升k个单位花费k^2块钱，国王就带了B块钱，问能携带的最大值是多少。
解法: 二分此值，然后BFS跑遍每个点，记录到达每个点的最小花费Mincost，如果Mincost[N-1] <= B,则此值可行，往上再二分，否则往下二分。
比赛时候本来我的二分方法应该返回high的，结果返回low，怎么都过不了样例，比赛完才发现此处的问题。 真是太弱。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <vector>#include <queue>#define ll long longusing namespace std;struct node{ int u; long long cost;};class TallShoes{public: long long mp[55][55],Mincost[55]; int N; bool bfs(int N,int S,int E,long long hei,long long B) { int i; Mincost[0] = 0; for(i=1;i<N;i++) Mincost[i] = 10000000000000000LL; queue<node> que; node now; now.u = S; now.cost = 0; que.push(now); while(!que.empty()) { node tmp = que.front(); que.pop(); int u = tmp.u; long long cost = tmp.cost; for(i=0;i<N;i++) { if(u == i) continue; if(mp[u][i] >= 10000000000000000LL) continue; if(mp[u][i] >= hei) { if(Mincost[i] > cost) { Mincost[i] = cost; now.u = i, now.cost = Mincost[i]; que.push(now); } } else { long long dif = hei-mp[u][i]; if(Mincost[i] > cost + dif*dif) { Mincost[i] = cost + dif*dif; now.u = i, now.cost = Mincost[i]; que.push(now); } } } } if(Mincost[E] <= B) return true; return false; } int maxHeight(int N, vector <int> X, vector <int> Y, vector <int> height, long long B) { for(int i=0;i<N;i++) { for(int j=0;j<N;j++) mp[i][j] = 10000000000000000LL; mp[i][i] = 0; } for(int i=0;i<X.size();i++) mp[X[i]][Y[i]] = mp[Y[i]][X[i]] = height[i]; long long low = 0, high = 1000000000LL; while(low <= high) { long long mid = (low+high)/2LL; if(bfs(N,0,N-1,mid,B)) low = mid+1; else high = mid-1; } return high; }};
TopCoder SRM 642 Div.2 1000 --二分+BFS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。