举报网站赚钱,沈阳成创网站建设公司,基木鱼建站,忻州市城乡建设局网站问题 D: [Sdoi2011]消防 时间限制: 1 Sec 内存限制: 512 MB 提交: 12 解决: 6 [提交][状态][讨论版] 题目描述 某个国家有n个城市#xff0c;这n个城市中任意两个都连通且有唯一一条路径#xff0c;每条连通两个城市的道路的长度为zi(zi1000)。 这个国家的人对火焰… 问题 D: [Sdoi2011]消防 时间限制: 1 Sec 内存限制: 512 MB 提交: 12 解决: 6 [提交][状态][讨论版] 题目描述 某个国家有n个城市这n个城市中任意两个都连通且有唯一一条路径每条连通两个城市的道路的长度为zi(zi1000)。 这个国家的人对火焰有超越宇宙的热情所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍大量的消防经费开销可是却又无可奈何总统竞选的国民支持率所以只能想尽方法提高消防能力。 现在这个国家的经费足以在一条边长度和不超过s的路径两端都是城市上建立消防枢纽为了尽量提高枢纽的利用率要求其他所有城市到这条路径的距离的最大值最小。 你受命监管这个项目你当然需要知道应该把枢纽建立在什么位置上。 输入 输入包含n行 第1行两个正整数n和s中间用一个空格隔开。其中n为城市的个数s为路径长度的上界。设结点编号以此为12……n。 从第2行到第n行每行给出3个用空格隔开的正整数依次表示每一条边的两个端点编号和长度。例如“2 4 7”表示连接结点2与4的边的长度为7。 输出 输出包含一个非负整数即所有城市到选择的路径的最大值当然这个最大值必须是所有方案中最小的。 样例输入 【样例输入1】 5 2 1 2 5 2 3 2 2 4 4 2 5 3 【样例输入2】 8 6 1 3 2 2 3 2 3 4 6 4 5 3 4 6 4 4 7 2 7 8 3 样例输出 【样例输出1】 5 【样例输出2】 5 提示 对于100%的数据n300000边长小等于1000。 很容易证得路径一定在树的直径上。如果路径拐到了另一条链上明显不最优。所以求出树的直径两遍广搜再一遍广搜就可以搞出其它点到直径的最大距离只要把直径上的边权标为0把它作为二分的下界上届就是树的直径了。二分时只不过要舍弃掉直径左右两部分长度mid即可最后判断剩下的长度s即可。 现在只要证一下只要保证直径上舍弃的长度其它点到直径的距离即可。其实这个没啥好证的。。想想就明白了。 #pragma GCC optimize(O3)
#includecstdio
#includecstdlib
#includecstring
#includeiostream
#includealgorithm
#includequeue
#define N 300005
#define ll long long
using namespace std;
int read()
{int sum0,f1;char xgetchar();while(x0||x9){if(x-)f-1;xgetchar();}while(x0x9){sum(sum1)(sum3)x-0;xgetchar();}return sum*f;
}
queueint q;
struct road{int v,next,l;}lu[N*2];
int n,s,e,rt1,rt2,top,adj[N],dis[N],vis[N],mark[N],from[N],zhan[N];
void add(int u,int v,int l){lu[e](road){v,adj[u],l};adj[u]e;}
void bfs(int S)
{memset(dis,-1,sizeof(dis));q.push(S);dis[S]0;while(!q.empty()){int xq.front();q.pop();vis[x]0;for(int iadj[x];i;ilu[i].next){int tolu[i].v;if(dis[to]-1){from[to]x;if(mark[to])dis[to]dis[x];else dis[to]dis[x]lu[i].l;q.push(to);}}}
}
bool check(int x)
{int l1,rtop;while(zhan[1]-zhan[l1]xltop)l;while(zhan[r-1]xr1)r--;return zhan[l]-zhan[r]s;
}
int main()
{ nread();sread();int x,y,z;for(int i1;in;i){xread();yread();zread();add(x,y,z);add(y,x,z);}bfs(1);for(int i1;in;i)if(dis[i]dis[rt1])rt1i;bfs(rt1);for(int i1;in;i)if(dis[i]dis[rt2])rt2i;int Ddis[rt2];zhan[top]dis[rt2];mark[rt2]1;while(rt2!rt1){zhan[top]dis[from[rt2]];rt2from[rt2];mark[rt2]1;}bfs(rt2);int l0,rD;for(int i1;in;i)lmax(l,dis[i]);if(sD){while(lr){int midlr1;if(check(mid))rmid-1;else lmid1;}}printf(%d\n,l);
} 转载于:https://www.cnblogs.com/QTY2001/p/7632632.html
