Beiyou OJ-272. Jadro siete

Beiyou Oj 272 Network Core

Opis témy

Vzhľadom na neusmernenú sieť G existuje N uzlov (1 až N), M okrajov a jadro siete.

Jadro siete: uzol s najmenším súčtom vzdialeností od ostatných uzlov v sieti a vzdialenosť medzi nimi je N pre dva body, ktoré nie sú spojené, a uzol s najmenším výstupným číslom, ak existuje viac sád riešenia

Vstup

Prvý riadok je celé číslo T predstavujúce počet skupín testovacích údajov (<26)

Pre každú sadu údajov o teste:

Prvý riadok má dve celé čísla N, M, ktoré predstavujú N bodov M strán

Nasledujúce M riadky, dve celé čísla u, v (<=N) per line, indicate that there is a side with a distance between points u and v, and there will be no repeated edges between any two points.

Výkon

Výstupné sieťové jadro

Ukážka vstupu

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

Ukážkový výstup

1 2

Zákonníka

#include using namespace std / / Floyd algorithm, the node of the graph below 100 can be considered int main() { int T,a[55][55],M,N,x,y cin>>T while(T--) { cin>>N>>M / / Adjacency matrix storage For(int i=1 i<=N i++) { // The initial initialization of the graph is unreachable for(int j=1 j<=N j++) { a[i][j]=N } } //Undirected graph For(int i=1 i>x>>y a[x][y]=1 a[y][x]=1 } //Floyd algorithm body For(int k=1 k<=N k++) { //Update the adjacency matrix with k node as the intermediate node for(int i=1 i<=N i++) { for(int j=1 j<=N j++) { If(a[i][k]==N||a[k][j]==N){ //If the loop is unreachable, continue the loop and do not continue executing the loop body statement continue } if(a[i][k]+a[k][j]