NOIP 2007 提高第四题。
啊......我还是看了题解才做出来的。
这题乍一看毫无头绪，但是我们spy on一下，暗中观察发现:n才300！随便打暴力水过去啊！
然后，这破题怎么暴力？感觉我的spfa，dijkstra都WA2了...
最后还是跑去看了题解。
一步一步慢慢模拟就出来了。
首先，肯定要跑floyd的。
然后，我们居然还要个邻接表来存图......(用来dfs求直径)
无脑Floyd的同时，记录一条直径的起点，终点。
find_d求了一条直径上的所有点。
然后find_f求出了直径上每个点不超过s能去的最远点。
然后对于每段直径上小于s的路径，求出每个点的min的max作为偏心距，然后再求min。
然后输出，成功。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int chart[][],n,s,top,d;
struct Edge
{
int u,v,len,next;
}edge[];
int point_e[],d_f[][],topd;///0dian 1xiabiao
bool vis[];
void add(int x,int y,int z)
{
top++;
edge[top].u=x;
edge[top].v=y;
edge[top].len=z;
edge[top].next=point_e[x];
point_e[x]=top;
return;
}
///
bool find_d(int a,int b)
{
if(a==b)
{
d_f[++topd][]=b;
return ;
}
if(vis[a]) return ;
vis[a]=;
int i=point_e[a];
while(i)
{
if(find_d(edge[i].v,b))
{
d_f[++topd][]=a;
vis[a]=;
return ;
}
i=edge[i].next;
}
vis[a]=;
return ;
}
void find_f(int k)
{
int i=k;
for(;i<=topd;i++)
{
if(chart[d_f[k][]][d_f[i][]]>s) break;
}
i--;
d_f[k][]=i;
return;
}
int find_ans(int k)
{
int ans=,now=;
for(int i=;i<=n;i++)
{
now=;
for(int j=k;j<=d_f[k][];j++)
{
now=min(now,chart[i][d_f[j][]]);
}
ans=max(ans,now);
}
return ans;
}
int main()
{
memset(chart,0x3f,sizeof(chart));
scanf("%d%d",&n,&s);
for(int i=;i<=n;i++) chart[i][i]=;
int x,y,z;
for(int i=;i<n;i++)
{
scanf ("%d%d%d",&x,&y,&z);
chart[x][y]=chart[y][x]=z;
add(x,y,z);
add(y,x,z);
}
int da,db;
for(int k=;k<=n;k++)
{
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(chart[i][j]>chart[i][k]+chart[k][j])
{
chart[i][j]=chart[i][k]+chart[k][j];
if(chart[i][j]>d)
{
d=chart[i][j];
da=i;db=j;
}
}
}
}
}
///
/**
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",chart[i][j]);
}
printf("\n");
}
*/
///
find_d(da,db);
for(int i=;i<=topd;i++) find_f(i);
///
/**
for(int i=1;i<=topd;i++) printf("%d ",d_f[i][0]);
printf("\n");
for(int i=1;i<=topd;i++) printf("%d ",d_f[i][1]);
*/
///
int now,ans=;
for(int i=;i<=topd;i++)
{
now=find_ans(i);
//printf("find_ans(%d)=%d\n",i,now);
ans=min(ans,now);
}
printf("%d",ans);
return ;
}
AC代码在此
这个纯暴力模拟题居然是蓝题...说明了我的暴力功力还不够。以后还要练搜索剪枝的。先做点USACO吧。
(logeadd：133行代码怎么不能是蓝题了？好像有点道理啊...)