程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> CSU1659: Graph Center(最短路)

CSU1659: Graph Center(最短路)

編輯：關於C++

Description

The center of a graph is the set of all vertices of minimum eccentricity, that is, the set of all vertices A where the greatest distance d(A,B) to other vertices B is minimal. Equivalently, it is the set of vertices with eccentricity equal to the graph's radius. Thus vertices in the center (central points) minimize the maximal distance from other points in the graph.
------wikipedia
Now you are given a graph, tell me the vertices which are the graph center.

Input

There are multiple test cases.
The first line will contain a positive integer T (T ≤ 300) meaning the number of test cases.
For each test case, the first line contains the number of vertices N (3 ≤ N ≤ 100) and the number of edges M (N - 1 ≤ N * (N - 1) / 2). Each of the following N lines contains two vertices x (1 ≤ x ≤ N) and y (1 ≤ y ≤ N), meaning there is an edge between x and y.

Output

The first line show contain the number of vertices which are the graph center. Then the next line should list them by increasing order, and every two adjacent number should be separated by a single space.

Sample Input

Sample Output

HINT

Source

題意：給出n個點，m條邊，求每個點到其他點的距離，取最大的，然後在這所有最大的距離中選一個最小的值，最後輸出這個值下有哪些點符合條件

思路： n次最短路找出所有答案

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define lson 2*i
#define rson 2*i+1
#define LS l,mid,lson
#define RS mid+1,r,rson
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define N 200005
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define lowbit(x) (x&-x)
const int mod = 1e9+7;
const int L = 10005;
struct Edges
{
    int x,y,w,next;
} e[L<<2];

int head[L],n,m;
int dis[L];
int vis[L];
int cnt[L],hash[L],ss[L];
int s[L];
void init()
{
    memset(e,-1,sizeof(e));
    memset(head,-1,sizeof(head));
}
void AddEdge(int x,int y,int w,int k)
{
    e[k].x = x,e[k].y = y,e[k].w = w,e[k].next = head[x],head[x] = k;
}
int relax(int u,int v,int c)
{
    if(dis[v]>dis[u]+c)
    {
        dis[v] = dis[u]+c;
        return 1;
    }
    return 0;
}

int SPFA(int src)
{
    int i;
    memset(vis,0,sizeof(vis));
    for(int i = 0; i<=n; i++)
        dis[i] = INF;
    dis[src] = 0;
    queue Q;
    Q.push(src);
    vis[src] = 1;
    while(!Q.empty())
    {
        int u,v;
        u = Q.front();
        Q.pop();
        vis[u] = 0;
        for(i = head[u]; i!=-1; i=e[i].next)
        {
            v = e[i].y;
            if(relax(u,v,e[i].w)==1 && !vis[v])
            {
                Q.push(v);
                vis[v] = 1;
            }
        }
    }
    int maxn = -1;
    for(i = 1; i<=n; i++)
        maxn = max(maxn,dis[i]);
    return maxn;
}

int ans[L],tot,p[N];
int main()
{
    int t,u,v,i,j,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init();
        for(i = 0; i<2*m; i+=2)
        {
            scanf("%d%d",&u,&v);
            AddEdge(u,v,1,i);
            AddEdge(v,u,1,i+1);
        }
        int minn = INF;
        for(i = 1; i<=n; i++)
        {
            p[i] = SPFA(i);
            minn = min(p[i],minn);
        }
        tot = 0;
        for(i = 1; i<=n; i++)
        {
            if(p[i]==minn)
                ans[tot++] = i;
        }
        printf("%d\n",tot);
        for(i = 0; i