Hdu 4514 湫湫系列故事——设计风景线 (非连通图并查集判环+树的直径)

今天药忘吃喽~ 2022-08-27 04:57 125阅读 0赞

去年比赛时做这题完全无思路……据说现在这题的数据加强过了。

根据题目要求图需要判环，需要注意图有可能是不连通的，不过并查集不论是否连通都可以判环。当要合并u,v时，若u和v的根节点相同，则说明构成环。

当图中没有环时就是求图中最长链的长度，可以用树的直径解决。注意可能有多个连通块，所以对每个连通块都要求最长链，然后更新最大值。

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int N=100005;
    
    class Disjoint_Set
    {
    public:
    	int father[N];            /*father[x]表示x的父节点*/
    	int rank[N];              //以该节点为根节点的点数,同时起到按秩合并的作用
    
    	void Init (int n)
    	{
    		for (int i=0;i<=n;i++)
    			Make_Set (i);
    	}
    
    	void Make_Set (int x)
    	{
    		father[x]=x;
    		rank[x]=1;
    	}
    
    	int Find_Set (int x)
    	{
    		if (x != father[x])
    			father[x] = Find_Set(father[x]);//回溯
    		return father[x];
    	}
    
    	bool Union (int x,int y)
    	{//返回false表示要合并的两点已在同一个集合中
    		int a=Find_Set (x);
    		int b=Find_Set (y);
    		if (a == b)
    			return false;
    		if (rank[a] >= rank[b])
    		{
    			father[b]=a;
    			rank[a]+=rank[b];
    		}
    		else
    		{
    			father[a]=b;
    			rank[b]+=rank[a];
    		}
    		return true;
    	}
    }ob;
    
    struct Node
    {
    	int v,w;
    	int next;
    }edges[205*N];
    
    int n,m,e;
    int head[N],dis[N];
    bool vis[N],used[N];
    int point_u;
    
    void Add (int u,int v,int w)
    {
    	edges[e].v=v;
    	edges[e].w=w;
    	edges[e].next=head[u];
    	head[u]=e++;
    }
    
    int BFS (int u)
    {
        int maxlenth=0;
    	memset(vis,false,sizeof(vis));
    	memset(dis,0,sizeof(dis));
    	queue<int> Q;
    	Q.push(u);
    	vis[u] = true;
    
    	while (!Q.empty())
    	{
    		int s=Q.front();
    		Q.pop();
    		used[s]=true;   
    		for (int i=head[s];i!=-1;i=edges[i].next)
    		{
    			int v=edges[i].v;
    			if (vis[v]==false)
    			{
    				dis[v]=dis[s]+edges[i].w;
    				Q.push(v);
    				vis[v]=true;
    				if (dis[v]>maxlenth)
    				{
    					maxlenth=dis[v];
    					point_u=v;
    				}
    			}
    		}
    	}
    	return maxlenth;
    }
    
    int main ()
    {
        while (~scanf("%d%d",&n,&m))
    	{
    		memset(head,-1,sizeof(head));
    		ob.Init(n);
    		int u,v,w,i;
    		e=0;
    		bool flag=false;
    		for (i=1;i<=m;i++)
    		{
    			scanf("%d%d%d",&u,&v,&w);
    			Add(u,v,w);
    			Add(v,u,w);
    			if (ob.Union(u,v)==false)
                    flag=true;  //若u和v的根节点相同，并且他们又彼此连通，则说明构成环
    		}
    		if (flag) printf("YES\n");
    		else
    		{
    		    memset(used,false,sizeof(used));
    		    int ans=-1;
                for (i=1;i<=n;i++)
                    if (used[i]==false)
                    {
                        BFS(i);
                        ans=max(ans,BFS(point_u));
                    }
                printf("%d\n",ans);
    		}
    	}
    	return 0;
    }