本文共 2330 字，大约阅读时间需要 7 分钟。
这道题 有点意思 让我迷了很久 包括我在写题解的时候 我都觉得不是很会写。（因为此时我还没有A掉这道题）
给同学讲了下题 然后把自己的代码覆盖了（那可是150+的代码啊都没了需重写o(╥﹏╥)o）
经过长达3h的思考 我终于想完了所有的细节问题和 一些check的问题及初始化 我觉得比较困难吧这道题。
当我写完 的时候发现调试比较恶心 头此时也比较晕 状态不太好了 巅峰时刻让打代码了。。。完了
终于打完了代码 一遍50 不我头脑不清醒 让我静静
好我知道了 貌似这个地方应该清零 但是我好像没有清零 这好像是可以导致错误的原因 改了 好像A了。。
这道题我觉得算是比较难的题目了，贪心 不好想 看了下书觉得不太会写 。
首先求 最短时间 好像根本不知道什么时候会最短 那就 二分吧 反正答案具有单调性
那我们可以有所有军队能行驶的距离了 ，此时 对于那些 到不了的根节点以下的节点肯定是能到多远到多远 越远越好
至于到了根节点的儿子节点的军队就有初步的资格去跨过根节点 来救援 至于救援不了的点那么自己管自己的就行了。
大体上的贪心细节请参考算法进阶竞赛指南。
//#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long#define INF 2147483646using namespace std;char buf[1<<15],*fs,*ft;inline char getc(){ return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}inline int read(){ int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f;}inline void put(int x){ x<0?putchar('-'),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar('\n');return;}const int MAXN=50002;int n,m,T;ll l,r,g[MAXN][20];int a[MAXN],q[MAXN],f[MAXN][20],b[MAXN],vis[MAXN],son[MAXN],t,h,top;ll dis[MAXN],d[MAXN],c[MAXN],z[MAXN],s,en;int lin[MAXN<<1],nex[MAXN<<1],ver[MAXN<<1],e[MAXN<<1],len;vector p[MAXN];inline void swap(ll &x,ll &y){ll t;t=x;x=y;y=t;}inline ll cmp(ll x,ll y){ return x>y;}inline void add(int x,int y,int z){ ver[++len]=y; nex[len]=lin[x]; lin[x]=len; e[len]=z;}inline void bfs(){ t=h=0; for(int i=lin[1];i;i=nex[i]) { int tn=ver[i]; vis[tn]=1;q[++t]=tn; b[++top]=i;son[tn]=top; } while(++h =0;j--) { if(!f[d[i]][j])continue; if(dis[i]+g[d[i]][j]<=x) { dis[i]+=g[d[i]][j]; d[i]=f[d[i]][j]; } } int army=son[d[i]]; vis[d[i]]=1; if(army) { p[army].push_back(x-dis[i]); if(p[army].size()>1&&p[army][p[army].size()-2] =e[b[i]])c[++s]=p[i][j]-e[b[i]]; } sort(z+1,z+1+en,cmp); sort(c+1,c+1+s,cmp); for(int i=1,j=1;i<=en;++i,++j)if(c[j] >1; if(check(mid))r=mid; else l=mid; } if(check(l))put(l); else put(r); return 0;}
转载于:https://www.cnblogs.com/chdy/p/10594356.html
