网络的核(2014)

题目描述

给定一个无向网络G，共有N个节点(1到N)，M条边，求网络的核。

网络的核：到网络中其他节点距离之和最小的节点，且对于不连通的两点，他们之间的距离为N，若有多组解，输出编号最小的节点

输入

第一行是一个整数T表示测试数据的组数(<26)

对于每组测试数据：

第一行有两个整数N,M，表示N个点M条边

接下来M行，每行两个整数u,v(<=N)，表示点u和v之间有一条距离为一的边，任意两点之间不会有重复边

输出

输出网络的核

样例输入

2
3 3
1 2
1 3
2 3
4 2
1 2
2 3

样例输出

1
2

#include<bits/stdc++.h>
using namespace std;
int main() {
	int T,N,M,u,v;
	cin>>T;
	int w[55][55];
	while(T--) {
		cin>>N>>M;//N个点，M条边
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				w[i][j]=N;
			}
		}
		for(int i=1; i<=M; i++) { //初始化邻接矩阵
			cin>>u>>v;
			w[u][v]=1;
			w[v][u]=1;
		}
		for(int k=1; k<=N; k++) {//Floyd
			for(int i=1; i<=N; i++) {
				for(int j=0; j<=N; j++) {
					if(w[i][k]==N||w[k][j]==N)continue;
					if(w[i][k]+w[k][j]<w[i][j]) {
						w[i][j]=w[i][k]+w[k][j];
					}
				}
			}
		}
		int min=99999;
		int tmp,sum;
		for(int i=1; i<=N; i++) {
			sum=0;
			for(int j=1; j<=N; j++) {
				sum+=w[i][j];
			}
			if(sum<min) {
				min=sum;
				tmp=i;
			}
		}
		cout<<tmp<<endl;
	}
}