记录编号	187266	评测结果	AAAAAAAAAA
题目名称	[Ural 1569] Iset塔上的网络	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2015-09-18 08:22:17	内存使用	0.33 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
#include<deque>
using namespace std;
const int SIZEN=110,INF=0x7fffffff/2;
int N,M;
int P[SIZEN][SIZEN]={0};
int sw[SIZEN][SIZEN]={0};
int pre[SIZEN]={0};
int ma=INF;
int ct1,ct2;
void read()
{
	scanf("%d%d",&N,&M);
	int a,b;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			sw[i][j]=INF,P[i][j]=INF;
	for(int i=1;i<=N;i++) sw[i][i]=P[i][i]=0;
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d",&a,&b);
		P[a][b]=P[b][a]=1;
		sw[a][b]=sw[b][a]=1;
	}
}
void floyed()
{
	for(int k=1;k<=N;k++)
		for(int i=1;i<=N;i++)
			for(int j=1;j<=N;j++) sw[i][j]=min(sw[i][k]+sw[k][j],sw[i][j]);
}
void checkcentre(int x,int y)
{
	int dat,D=0;
	if(x==y) dat=0;
	else dat=1;
	for(int i=1;i<=N;i++) D=max(D,2*min(sw[x][i],sw[y][i])+dat);
	if(D<ma)
	{
		ma=D;ct1=x;ct2=y;
	}
}
void SPFA()
{
	deque<int> Q;
	int inq[SIZEN]={0};
	int dist[SIZEN];
	for(int i=1;i<=N;i++) dist[i]=INF;
	dist[ct1]=dist[ct2]=0;
	inq[ct1]=inq[ct2]=1;
	Q.push_back(ct1);Q.push_back(ct2);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();inq[x]=0;
		for(int i=1;i<=N;i++)
		{
			if(dist[x]+P[x][i]<dist[i])
			{
				dist[i]=dist[x]+P[x][i];
				pre[i]=x;
				if(inq[i]==0)
				{
					inq[i]=1;
					Q.push_back(i);
				}
			}
		}
	}
}
void work()
{
	floyed();
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
		{
			if(P[i][j]<INF) checkcentre(i,j);
		}
	SPFA();
	for(int i=1;i<=N;i++)
		if(pre[i]) printf("%d %d\n",i,pre[i]);
	if(ct1!=ct2)
	printf("%d %d\n",ct1,ct2);
}
int main()
{
	freopen("iset.in","r",stdin);
	freopen("iset.out","w",stdout);
	read();
	work();
	return 0;
}