[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;
}