记录编号	90183	评测结果	AAAAAAAAAA
题目名称	[Ural 1569] Iset塔上的网络	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2014-03-06 19:13:57	内存使用	0.41 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
const int SIZEN=110,INF=0x7fffffff/1000;
int c[SIZEN][SIZEN]={0};
int len[SIZEN][SIZEN]={0};
int pre[SIZEN]={0};
int N,M;
int ans=INF;
int ct1,ct2;
void SPFA(void){
	queue<int> Q;
	bool inq[SIZEN]={0};
	int dist[SIZEN]={0};
	for(int i=1;i<=N;i++) dist[i]=INF;
	dist[ct1]=dist[ct2]=0;
	inq[ct1]=inq[ct2]=true;
	Q.push(ct1),Q.push(ct2);
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		inq[u]=false;
		for(int i=1;i<=N;i++){
			if(dist[u]+c[u][i]<dist[i]){
				dist[i]=dist[u]+c[u][i];
				pre[i]=u;
				if(!inq[i]){
					Q.push(i);
					inq[i]=true;
				}
			}
		}
	}
}
void checkcenter(int u,int v){
	int dta=(u!=v),D=0;//D是直径
	//若u=v,则直径=2*(到u的最长距离),否则就是(到u的最长距离)+(到v的最长距离)+1,那个1是(u,v)
	for(int i=1;i<=N;i++){
		D=max(D,2*min(len[u][i],len[v][i])+dta);
	}
	if(D<ans) ans=D,ct1=u,ct2=v;
}
void floyd(void){
	for(int k=1;k<=N;k++){
		for(int i=1;i<=N;i++){
			for(int j=1;j<=N;j++) len[i][j]=min(len[i][j],len[i][k]+len[k][j]);
		}
	}
}
void read(void){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++) c[i][j]=INF;
	}
	for(int i=1;i<=N;i++) c[i][i]=0;
	for(int i=1;i<=M;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		c[a][b]=c[b][a]=1;
	}
	memcpy(len,c,sizeof(len));
}
int main(){
	freopen("iset.in","r",stdin);
	freopen("iset.out","w",stdout);
	read();
	floyd();
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			if(c[i][j]<INF) checkcenter(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);
	return 0;
}