【刷题】【树】【模拟】树网的核

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\n",ans);
    return 0;
}

View Code

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\n",ans);
    return 0;
}