风景

风景

关注
发信
关注(28)粉丝(399)

HDU 4514 湫湫系列故事——设计风景线 树的直径

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4514

湫湫系列故事——设计风景线

Time Limit: 5000/2000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
#### 问题描述
> 随着杭州西湖的知名度的进一步提升，园林规划专家湫湫希望设计出一条新的经典观光线路，根据老板马小腾的指示，新的风景线最好能建成环形，如果没有条件建成环形，那就建的越长越好。
> 　　现在已经勘探确定了n个位置可以用来建设，在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线？如果不能，风景线最长能够达到多少？
> 　　其中，可以兴建的路线均是双向的，他们之间的长度均大于0。
#### 输入
> 测试数据有多组，每组测试数据的第一行有两个数字n, m，其含义参见题目描述；
> 　　接下去m行，每行3个数字u v w，分别代表这条线路的起点，终点和长度。
>
> 　　[Technical Specification]
> 　　1. n 　　2. m 　　3. 1 　　4. w 对于每组测试数据，如果能够建成环形（并不需要连接上去全部的风景点），那么输出YES，否则输出最长的长度，每组数据输出一行。
####样例输入
> 3 3
> 1 2 1
> 2 3 1
> 3 1 1
>
####样例输出
> YES
>
## 题意
> o(n)求树的直径

题解

代码

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define scf scanf

#define prf printf

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=1e5+10;

int fa[maxn];

int find(int x){ return fa[x]=fa[x]==x?x:find(fa[x]); }

VPII G[maxn];

int n,m;

int dep[maxn],vis[maxn];

int Ma;

//树直径，两次dfs。

int _v,_Ma;

void dfs(int u,int fa,int d){

    vis[u]=1;

    dep[u]=d;

    if(_Ma<dep[u]){ _Ma=dep[u],_v=u; }

    rep(i,0,G[u].sz()){

        int v=G[u][i].X,w=G[u][i].Y;

        if(v==fa) continue;

        dfs(v,u,d+w);

    }

}

void init(){

    for(int i=1;i<=n;i++) fa[i]=i;

    for(int i=1;i<=n;i++) G[i].clear();

    for(int i=1;i<=n;i++) vis[i]=false;

    Ma=0;

}

int main() {

    while(scf("%d%d",&n,&m)==2){

        init();

        int flag=0;

        rep(i,0,m){

            int u,v,w;

            scf("%d%d%d",&u,&v,&w);

            int pu=find(u);

            int pv=find(v);

            if(pu!=pv){

                fa[pv]=pu;

            }else{

                flag=1;

            }

            G[u].pb(mkp(v,w));

            G[v].pb(mkp(u,w));

        }

        if(flag){

            prf("YES\n"); continue;

        }

        for(int i=1;i<=n;i++){

            if(!vis[i]){

                _v=i,_Ma=0;

                dfs(i,-1,0);

                int u=_v;

                _v=u,_Ma=0;

                dfs(u,-1,0);

                Ma=max(Ma,_Ma);

            }

        }

        prf("%d\n",Ma);

    }

    return 0;

}

/*

5 0

*/


#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define scf scanf

#define prf printf

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=1e5+10;

int fa[maxn];

int find(int x){ return fa[x]=fa[x]==x?x:find(fa[x]); }

VPII G[maxn];

int n,m;

int vis[maxn];

int Ma;

///dp[u][0]存最大深度

///dp[u][1]存次大深度

///ans[u]存有经过u点的最远点对

///id[u]存最大值是从哪个儿子转移上来的。

///第一遍求以u为根的最大深度和次大深度，以及最远顶点对。

///第二遍则求在整个树上的。

int ans[maxn],dp[maxn][2],id[maxn];

void dfs(int u,int fa){

    vis[u]=1;

    dp[u][0]=dp[u][1]=0;

    rep(i,0,G[u].sz()){

        int v=G[u][i].X,w=G[u][i].Y;

        if(v==fa) continue;

        dfs(v,u);

        if(dp[u][0]<dp[v][0]+w){

            dp[u][1]=dp[u][0];

            dp[u][0]=dp[v][0]+w;

            id[u]=v;

        }else if(dp[u][1]<dp[v][0]+w){

            dp[u][1]=dp[v][0]+w;

        }

    }

    ans[u]=dp[u][0]+dp[u][1];

    Ma=max(Ma,ans[u]);

}

void dfs2(int u,int fa,int w){

    if(fa!=-1){

        int tmp=(id[fa]==u)?dp[fa][1]:dp[fa][0];

        ans[u]=max(ans[u],dp[u][0]+tmp+w);

        if(dp[u][0]<=tmp+w){

            dp[u][0]=tmp+w;

            dp[u][1]=dp[u][0];

            id[u]=-1;

        }else if(dp[u][1]<tmp+w){

            dp[u][1]=tmp+w;

        }

    }

    Ma=max(Ma,ans[u]);

    rep(i,0,G[u].sz()){

        int v=G[u][i].X;

        if(v==fa) continue;

        dfs2(v,u,G[u][i].Y);

    }

}

void init(){

    for(int i=1;i<=n;i++) fa[i]=i;

    for(int i=1;i<=n;i++) G[i].clear();

    for(int i=1;i<=n;i++) vis[i]=false;

    clr(dp,0); clr(id,-1);

    Ma=0;

}

int main() {

    while(scf("%d%d",&n,&m)==2){

        init();

        int flag=0;

        rep(i,0,m){

            int u,v,w;

            scf("%d%d%d",&u,&v,&w);

            int pu=find(u);

            int pv=find(v);

            if(pu!=pv){

                fa[pv]=pu;

            }else{

                flag=1;

            }

            G[u].pb(mkp(v,w));

            G[v].pb(mkp(u,w));

        }

        if(flag){

            prf("YES\n"); continue;

        }

        for(int i=1;i<=n;i++){

            if(!vis[i]){

                dfs(i,-1);

                dfs2(i,-1,0);

            }

        }

        prf("%d\n",Ma);

    }

    return 0;

}

/*

5 3

1 2 9

3 4 5

3 5 3

*/


#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define scf scanf

#define prf printf

typedef int LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=10000000000000000LL;

const double eps=1e-9;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=100010;

VPII G[maxn];

int fa[maxn];

int find(int x){ return fa[x]=fa[x]==x?x:find(fa[x]); }

int n,m;

int dp[maxn],ans;

int vis[maxn];

void dfs(int u,int fa){

    dp[u]=0;

    vis[u]=1;

    rep(i,0,G[u].sz()){

        int v=G[u][i].X,w=G[u][i].Y;

        if(v==fa) continue;

        dfs(v,u);

        ///枚举经过(u,v)边的在以u为根的子树中的最长链

        ans=max(ans,dp[v]+w+dp[u]);

        dp[u]=max(dp[u],dp[v]+w);

    }

}

int main() {

    while(scf("%d%d",&n,&m)==2){

        for(int i=0;i<=n;i++) vis[i]=0;

        for(int i=0;i<=n;i++) G[i].clear();

        for(int i=0;i<=n;i++) fa[i]=i;

        bool flag=false;

        rep(i,0,m){

            int u,v,w;

            scf("%d%d%d",&u,&v,&w);

            int pu=find(u),pv=find(v);

            if(pu!=pv){

                fa[pv]=pu;

            }else flag=true;

            G[u].pb(mkp(v,w));

            G[v].pb(mkp(u,w));

        }

        if(flag){

            prf("YES\n");

            continue;

        }

        ans=0;

        for(int i=1;i<=n;i++){

            if(vis[i]) continue;

            dfs(i,-1);

        }

        prf("%d\n",ans);

    }

    return 0;

}

//end-----------------------------------------------------------------------

/*

6 5

1 2 1

1 3 1

2 6 1

3 4 1

3 5 2

*/
04-28 15:14
Powered by LMLPHP ©2024 风景 0.082020