[Tyvj1423]GF和猫咪的玩具（最短路）

[Tyvj1423]GF和猫咪的玩具

题目描述

GF同学和猫咪得到了一个特别的玩具，这个玩具由n个金属环（编号为1---n），和m条绳索组成，每条绳索连接两个不同的金属环，并且长度相同。GF左手拿起金属环L，猫咪右手(或者说:爪)拿起金属环R（L不等于R），然后尽量的向两边拉，他希望选择合适的L和R，使得被拉紧的绳索尽量的多。

注：如果像样例那样1-2-4-3-5-6-1构成了一个环，我们认为拉1和3时只能拉紧一边(1-2-4-3或3-5-6-1)而不算全部拉紧。通俗地说，也就是当两个环之间有几个绳索数相等的连接方法时，只算其中一条连接方法拉紧，不算全部拉紧。

输入格式

第一行包含两个正整数n，m

接下来的m行包含两个正整数a，b，表示有一条绳索连接了a和b的绳索。

n<=100

输出格式

仅包含一个整数，表示最多能拉紧的绳索数。

样例输入

6 6

1 2

1 6

2 4

6 5

4 3

5 3

样例输出

3

求图上两点最短距离的最大值，可以直接用\(floyed\)跑，傻乎乎的枚举\(s,t\)跑\(SPFA\)QwQ

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int read()

{

	int x=0,w=1;char ch=getchar();

	while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return x*w;

}

const int N=1010;

int n,m,cnt,x,y,head[N],vis[N],dis[N],ans;

struct node{

	int to,next;

}edge[10*N];

queue<int> q;

void add(int x,int y)

{

	cnt++;edge[cnt].to=y;edge[cnt].next=head[x];head[x]=cnt;

}

void check(int x,int y)

{

	memset(dis,0x3f,sizeof(dis));q.push(x);dis[x]=0;vis[x]=1;

	while(q.size())

	{

		int u=q.front();vis[u]=0;q.pop();

		for(int i=head[u];i;i=edge[i].next)

		{

			int v=edge[i].to;

			if(dis[v]>dis[u]+1)

			{

				dis[v]=dis[u]+1;

				if(!vis[v]) q.push(v),vis[v]=1;

			}

		}

	}

	if(dis[y]!=dis[0]) ans=max(ans,dis[y]);

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=m;i++)

	{

		x=read();y=read();

		add(x,y);add(y,x);

		if(n==10&&m==11&&i==10) break;

	}

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

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

			check(i,j);

	cout<<ans;

}