1>暴力出奇迹
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int n,lim; const int N=303; int head[N],tot; int ev[N<<1],ew[N<<1],enx[N<<1]; void add(int u,int v,int w) { ev[++tot]=v,ew[tot]=w,enx[tot]=head[u],head[u]=tot; ev[++tot]=u,ew[tot]=w,enx[tot]=head[v],head[v]=tot; } int dis[N],fa[N];//从源点来的最短路 int pt,distant;//最远的那个点 void dfs(int rt)//两次dfs寻找任意一条直径 { bool conti=false; for(int i=head[rt];i;i=enx[i]) { if(ev[i]==fa[rt]) continue; conti=true; fa[ev[i]]=rt; dis[ev[i]]=dis[rt]+ew[i]; dfs(ev[i]); } if(!conti && distant<dis[rt] ) distant=dis[rt],pt=rt; } bool us[N]; void find_ecc(int rt,int f,int dist) { bool conti=false; for(int i=head[rt];i;i=enx[i]) { if(ev[i]==f || us[ev[i]] ) continue; conti=true; find_ecc(ev[i],rt,dist+ew[i]); } if(!conti && distant<dist ) distant=dist; } int main() { scanf("%d%d",&n,&lim); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); } //先找直径，迅速定下选得链的范围 int st,ed,lenth; dfs(1); st=pt; dis[st]=0,fa[st]=0,distant=0; dfs(st); ed=pt,lenth=distant; //开始暴力寻找偏心距，确定答案 int ans=1<<30; for(int i=ed;i;i=fa[i]) { //枚举寻找这个链的起始b，终止a int a=i,b=i; us[a]=true; while(fa[b] && dis[a]-dis[fa[b]]<=lim ) us[fa[b]]=true,b=fa[b]; int ans2=0; for(int t=a;t!=fa[b];t=fa[t]) { distant=0; find_ecc(t,0,0); ans2=max(ans2,distant); } ans=min(ans2,ans); for(int t=a;t!=b;t=fa[t]) us[t]=false; us[b]=false; } printf("%d ",ans); return 0; }
2>按照题目背景写大模拟
长度感人，调试过程感人......
以后一定要静态调试......
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; inline int read() { int x=0; char c=getchar(); while(c<'0' || c>'9' ) c=getchar(); while(c>='0'&&c<='9' ) x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x; } int n,lim; const int N=303; int head[N],tot; int ev[N<<1],ew[N<<1],enx[N<<1]; void add(int u,int v,int w) { ev[++tot]=v,ew[tot]=w,enx[tot]=head[u],head[u]=tot; ev[++tot]=u,ew[tot]=w,enx[tot]=head[v],head[v]=tot; } int dis[N],fa[N];//从源点来的最短路 int pt,distant;//最远的那个点 void dfs(int rt)//两次dfs寻找任意一条直径 { for(int i=head[rt];i;i=enx[i]) { if(ev[i]==fa[rt]) continue; fa[ev[i]]=rt; dis[ev[i]]=dis[rt]+ew[i]; dfs(ev[i]); } if(distant < dis[rt] ) distant=dis[rt],pt=rt; } int ecc[2][N];//0是从st出发，1是从ed出发 int nx[2][N];//0是从st出发，1是从ed出发 bool cross[2][N]; int st,ed,length; bool get_ecc(int rt,int f,int k,int goal) { if(rt==goal) return true; for(int i=head[rt];i;i=enx[i]) { if(ev[i]==f) continue; if(get_ecc(ev[i],rt,k,goal) ) nx[k][rt]=ev[i]; int val=ecc[k][ev[i]]+ew[i]; if(val==ecc[k][rt] ) cross[k][rt]=true; else if(val > ecc[k][rt]) ecc[k][rt]=val,cross[k][rt]=false; } if(nx[k][rt]) return true; else return false; } int c,l,r; void find_c(int rt) { if(dis[rt]*2==length) l=r=c=rt; else { int t=dis[nx[0][rt]]<<1; if(t<=length ) find_c(nx[0][rt]); else { l=rt,r=nx[0][rt]; if(length-dis[rt]*2 < t-length ) c=rt; else c=nx[0][rt]; } } } void bfs(int res) { while(1 && res>0 ) { int pre=nx[1][l],nxt=nx[0][r]; bool f1=false,f2=false; if(pre && res>=dis[l]-dis[pre] && !cross[1][l] ) f1=true; if(nxt && res>=dis[nxt]-dis[r] && !cross[0][r] ) f2=true; if(!f1 && !f2 ) break; if(f1 && !f2 ) { if(ecc[0][r]>=ecc[1][l] ) break; else res-=dis[l]-dis[pre],l=pre; } else if(!f1 && f2 ) { if(ecc[1][l]>=ecc[0][r] ) break; else res-=dis[nxt]-dis[r],r=nxt; } else //都可以选，我再比较 { if(ecc[1][l] > ecc[0][r] ) res-=dis[l]-dis[pre],l=pre; else if(ecc[1][l]< ecc[0][r] ) res-=dis[nxt]-dis[r],r=nxt; else if(res >= dis[l]-dis[pre] +dis[nxt]-dis[r] ) res-=dis[l]-dis[pre] +dis[nxt]-dis[r],l=pre,r=nxt; else break; } } } int ans; bool us[N]; int find_s(int rt,int f) { int as=0; for(int i=head[rt];i;i=enx[i]) if(ev[i]!=f && !us[ev[i]] ) as=max(as,find_s(ev[i],rt) +ew[i]); return as; } void get_max_ecc(int l,int r) { ans=max(dis[l],length-dis[r]); if(l==r || nx[0][l]==r ) return ; //ans=max(ans,max(ecc[1][l],ecc[0][r]) ); for(int t=r;t!=l;t=nx[1][t]) us[t]=true; for(int t=nx[0][l],pre=l;t!=r;pre=t,t=nx[0][t]) if(max(ecc[0][t],ecc[1][t]) >ans ) ans=max(ans,find_s(t,pre) ); } int main() { n=read(),lim=read(); for(int i=1;i<n;i++) { int u=read(),v=read(),w=read(); add(u,v,w); } //先找直径，迅速定下选得链的范围 dfs(1); st=pt; dis[st]=0,fa[st]=0,distant=0; dfs(st); ed=pt,length=distant; //写一份正解思路 get_ecc(st,0,0,ed); get_ecc(ed,0,1,st); find_c(st); if(dis[r]-dis[l]>lim) l=r=c,ans=max(ecc[1][l],ecc[0][r]); else { bfs(lim-(dis[r]-dis[l])); get_max_ecc(l,r);//这里强制不选择l,r链上的点，所以有点复杂 } printf("%d ",ans); return 0; }