HDU 4514并查集判环+最长路
HDU 最长
2023-09-14 09:06:20 时间
题意:中文题......
思路:先推断是否能成环,之前以为是有向图,就用了spfa推断,果断过不了自己出的例子,发现是无向图。并查集把,两个点有公共的父节点,那就是成环了,之后便是求最长路了。之前用spfa将权值取反后求最短路,然后结果取正就完事了,仅仅是加个源点0而已,跑一边居然能超时,难道是姿势不正确吗.....,然后用了更暴力的bfs,由于是一个无环的图,所以从一个点出发后。它能走到的点之后便不用再走了,而这个点在bfs中更新距离时每一个点仅仅能入队一次.....这样就快多了。可是我们还须要找到最远的距离的位置在进行一次bfs,由于有这样的情况,1-->2 10,1-->3 5,2-->4 10,从1出发最长距离是20。到4那个点时。然而最长路应该是25,3->1->2->4;所以在进行一次bfs避免这样的情况
#include <queue> #include <vector> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> #include <functional> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=1100010; int f[100010],n,m,num,head[100010],dis[100010]; int used[100010],vis[100010]; struct EDGE{ int to,w,next; }edge[maxn*2]; void addedge(int u,int v,int w){ edge[num].to=v; edge[num].w=w; edge[num].next=head[u]; head[u]=num++; } void bfs(int s){ memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); vis[s]=1;dis[s]=0; queue<int>que; que.push(s); while(!que.empty()){ int u=que.front();que.pop(); used[u]=1; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(vis[v]==0){ vis[v]=1; dis[v]=dis[u]+edge[i].w; que.push(v); } } } } int slove(int s){ int max1=0,pos=s; bfs(s); for(int i=1;i<=n;i++){ if(dis[i]>max1){ pos=i;max1=dis[i]; } } bfs(pos); int ans=0; for(int i=1;i<=n;i++){ if(dis[i]>ans) ans=dis[i]; } return ans; } void init(){ for(int i=0;i<=n;i++) f[i]=i; num=0; memset(head,-1,sizeof(head)); memset(used,0,sizeof(used)); } int find1(int x){ int k,r=x,j; while(r!=f[r]) r=f[r]; k=x; while(k!=r){ j=f[k]; f[k]=r;k=j; } return r; } void unite(int a,int b,int c){ int aa=find1(a); int bb=find1(b); f[aa]=bb; } int main(){ int a,b,c; while(scanf("%d%d",&n,&m)!=-1){ init(); int flag=0; for(int i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c); if(find1(a)==find1(b)) flag=1; unite(a,b,c); addedge(a,b,c);addedge(b,a,c); } if(flag) printf("YES\n"); else{ int ans=-1; for(int i=1;i<=n;i++){ if(used[i]==0){ ans=max(ans,slove(i)); } } printf("%d\n",ans); } } return 0; }
相关文章
- HDU 1556-差分数组和线段树的对比分析-Color the ball
- hdu 3980 Paint Chain(SG函数)
- HDU 3336 KMP算法中对next数组的理解「建议收藏」
- HDU P3341 Lost’s revenge 题解+数据生成器
- hdu 3336 Count the string(kmp应用)
- hdu 3336 Count the string 用心写的题解
- hdu 1142_hdu1001
- HDU 3336 Count the string 解题报告
- [ACM] HDU 1006 解题报告
- H - Partial Tree HDU - 5534 【 完全背包 】
- HDU-2084 数塔
- 敌兵布阵(HDU 1166)
- I Hate It (HDU 1754)
- 校庆神秘建筑(HDU 1411)
- 还是畅通工程(HDU 1233)
- Friend-Graph (HDU 6152)2017中国大学生程序设计竞赛 - 网络选拔赛
- CaoHaha's staff (HDU 6154)(2017中国大学生程序设计竞赛 - 网络选拔赛)
- Oil Deposits (HDU - 1241 )(DFS思路 或者 BFS思路)
- 畅通工程续(HDU 1874)(简单最短路)
- Drainage Ditches (HDU - 1532)(最大流)
- Ancient Go ( HDU - 5546 ) ( BFS 搜索是否相连)
- 统计难题 【 HDU - 1251 】【 字典树 】
- Phone List 【 HDU - 1671 】 【 字典树判断是否存在前缀 】
- A * B Problem Plus【HDU 1402】 【FFT求高精度乘法】
- Bone Collector HDU - 2602【 01 背包 】