题意：中文题......
思路：先推断是否能成环，之前以为是有向图，就用了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#include #include #include #include #include #include #include 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 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