Massive Algorithms: hdu 4514

hdu 4514 - 设计风景线

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

　　随着杭州西湖的知名度的进一步提升，园林规划专家湫湫希望设计出一条新的经典观光线路，根据老板马小腾的指示，新的风景线最好能建成环形，如果没有条件建成环形，那就建的越长越好。
　　现在已经勘探确定了n个位置可以用来建设，在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线？如果不能，风景线最长能够达到多少？
　　其中，可以兴建的路线均是双向的，他们之间的长度均大于0。

Input

　　测试数据有多组，每组测试数据的第一行有两个数字n, m，其含义参见题目描述；
　　接下去m行，每行3个数字u v w，分别代表这条线路的起点，终点和长度。

　　[Technical Specification]
　　1. n<=100000
　　2. m <= 1000000
　　3. 1<= u, v <= n
　　4. w <= 1000

Output

　　对于每组测试数据，如果能够建成环形（并不需要连接上去全部的风景点），那么输出YES，否则输出最长的长度，每组数据输出一行。

Sample Input

Sample Output

YES

https://blog.csdn.net/qianguch/article/details/78216860
一棵树的直径就是这棵树上存在的最长路径。
求法:
两次dfs或bfs。第一次任意选一个点进行dfs(bfs)找到离它最远的点，此点就是最长路的一个端点，再以此点进行dfs（bfs），找到离它最远的点，此点就是最长路的另一个端点，于是就找到了树的直径。
证明:
假设此树的最长路径是从s到t,我们选择的点为u。反证法：假设搜到的点是v。
1、v在这条最长路径上，那么dis[u,v]>dis[u,v]+dis[v,s],显然矛盾。
2、v不在这条最长路径上，我们在最长路径上选择一个点为po，则dis[u,v]>dis[u,po]+dis[po,t]，那么有dis[s,v]=dis[s,po]+dis[po,u]+dis[u,v]>dis[s,po]+dis[po,t]=dis[s,t],即dis[s,v]>dis[s,t],矛盾。
也许你想说u本身就在最长路径，或则其它的一些情况，但其实都能用类似于上面的反证法来证明的。
综上所述，你两次dfs(bfs)就可以求出最长路径的两个端点和路径长度。
附练习题:
1、POJ 1985 Cow Marathon 模板题；
2、POJ 3310 Caterpillar 需判断出其实是求树的直径，模板运用，不难。

用dfs判断是否有环，再用两次dfs求出树上的最长路了（树的直径）。

这里用到了一个树的性质，从树上的任意节点出发找到的最长路端点一定是该树直径的端点。

先看是否有环，有环的话输出YES，否则找最长的直径的长度。
判断有没有环用并查集就能判断。
直径的话，还是两遍dfs解决=-=

int tail[100010], pre[2000010], to[2000010], length[2000010], tot;
int p[100010];
int far_node, far_dis;
int used[100010];

inline void add(int _u, int _v, int _length) {
    pre[tot] = tail[_u];
    to[tot] = _v;
    length[tot] = _length;
    tail[_u] = tot++;
}

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

void dfs(int now, int fa, int dis) {
    used[now] = true;
    for(int i = tail[now]; i != -1; i = pre[i]) {
        int _to = to[i], _length = length[i];
        if(_to == fa) continue;
        if(far_dis < dis + _length)
            far_dis = dis + _length, far_node = _to;
        dfs(_to, now, dis + _length);
    }
}

int main() {
    int n, m;
    while(scanf("%d%d", &n, &m) > 0) {
        for(int i = 1; i <= n; i++)
            p[i] = i;
        memset(tail, -1, sizeof tail);
        tot = 0;
        bool circle = false;
        while(m--) {
            int u, v, cost;
            scanf("%d%d%d", &u, &v, &cost);
            add(u, v, cost);
            add(v, u, cost);
            int uf = find(u), vf = find(v);
            if(uf == vf)
                circle = true;
            else
                p[uf] = vf;
        }
        if(circle)
            puts("YES");
        else {
            int ans = 0;
            memset(used, 0, sizeof used);
            for(int i = 1; i <= n; i++) {
                if(!used[i]) {
                    far_dis = 0;
                    dfs(i, -1, 0);
                    far_dis = 0;
                    dfs(far_node, -1, 0);
                    ans = max(far_dis, ans);
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

http://www.acmsearch.com/article/show/22445

分析：首先我们得考虑这是一个无向图，而且有可能是非连通的，那么就不能直接像求树那样来求最长链。对于本题，首先得

判断环，在这里我们就用并查集判环，因为并查集本身就是树型结构，如果要连接的两点的祖先都相同，那么就已经有环了，

这样直接输出YES，如果没有环，就应该输出最长链长度，那么我们每次可以对每一个没有访问过的节点进行两次bfs，就可以

求出，然后每次更新最大值即可。

int pre[N],n,m,res;

int head[N],to[M],next[M],w[M],edge;
int tosum[N],dis[N],que[N];
bool vis[N],used[N];
queue <int>Q;

void init()
{
    edge=0;
    memset(head,-1,sizeof(head));
    memset(used,0,sizeof(used));
    for(int i=1;i<=n;i++)
        pre[i]=i;
}

int find(int x)
{
    int r=x;
    while(r!=pre[r])
        r=pre[r];
    //路径压缩
    int i=x,j;
    while(i!=r)
    {
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}

void Union(int x,int y)
{
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy) pre[fx]=fy;
}

void add(int u,int v,int c)
{
    to[edge]=v,w[edge]=c,next[edge]=head[u],head[u]=edge++;
    to[edge]=u,w[edge]=c,next[edge]=head[v],head[v]=edge++;
}

void bfs(int s)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    vis[s]=1; dis[s]=0;
    while(!Q.empty()) Q.pop();
    Q.push(s);
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        used[u]=1;
        for(int i=head[u]; ~i; i=next[i])
        {
            int v=to[i];
            if(!vis[v])
            {
                vis[v]=1;
                dis[v]=dis[u]+w[i];
                Q.push(v);
            }
        }
    }
}

int treediameter(int s)
{
    int u,maxl;
    bfs(s);
    maxl=0,u=s;
    for(int i=1; i<=n; i++)
        if(dis[i]>maxl)
            u=i,maxl=dis[i];
    bfs(u);
    maxl=0;
    for(int i=1; i<=n; i++)
        if(dis[i]>maxl)
            maxl=dis[i];
    return maxl;
}

int main()
{
    int u,v,d,i;
    while(~scanf("%d%d",&n,&m))
    {
        init();
        bool f=0;
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&d);
            if(find(u)==find(v)) f=1;
            Union(u,v);
            add(u,v,d);
        }
        if(f) puts("YES");
        else
        {
            res=-1;
            for(i=1;i<=n;i++)
            if(!used[i]) res=max(res,treediameter(i));
            printf("%d\n",res);
        }
    }
    return 0;
}

hdu 4514 - 设计风景线

Labels

Popular Posts