首页 > 程序开发 > 软件开发 > 其他 >

hdu 5876 Sparse Graph【最短路+思维】好题

2016-09-12

hdu 5876 Sparse Graph【最短路+思维】好题

Sparse Graph

Time Limit: 4000/2000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others)

Total Submission(s): 300Accepted Submission(s): 100

Problem Description
In graph theory, the complement of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G.

Now you are given an undirected graph G of N nodes and M bidirectional edges of unit length. Consider the complement of G, i.e., H. For a given vertex S on H, you are required to compute the shortest distances from S to all N?1 other vertices.

Input
There are multiple test cases. The first line of input is an integer T(1&le;T<35) denoting the number of test cases. For each test case, the first line contains two integers N(2&le;N&le;200000) and M(0&le;M&le;20000). The following M lines each contains two distinct integers u,v(1&le;u,v&le;N) denoting an edge. And S(1&le;S&le;N) is given on the last line.
Output
For each of T test cases, print a single line consisting of N?1 space separated integers, denoting shortest distances of the remaining N?1 vertices from S (if a vertex cannot be reached from S, output ``-1" (without quotes) instead) in ascending order of vertex number.
Sample Input
1 2 0 1
Sample Output
1
题目大意:

给你n个点,m条无向边,让你求其无向完全图的补图的单源最短路。

思路:

网赛之后不知道为什么把数据范围m从5500改大了,但是我是按照5500做的,通过了....赛后也是通过的....

1、这算是出题事故了,一开始的时候说是M《=5500,那么问题其实就并不难了,如N大于了6000(大一点稍微稳妥一点),那么狠显然,无论这m条边如何建立的,其补图的从源点到其各个点的最短路要么是1,要么是2,因为很明显,如果m==0的时候,其源点到其他各个点都有一条值为1的最短路径直接相连,而且明显5500条边,当N大于5500的时候,是不可能将从源点到其各个点的最短路变成2以上的情况的(因为假设n==6000的时候,从源点到其他各个点的距离为2的走法一共有6000-2种,明显只去掉5500条边,是不能够使得某些最短距离变成3的)。。

2、那么当n<=6000的时候,直接按照其邻接矩阵跑其补图的最短路即可,否则如果n>6000那么按照输入的边,如果对应输入的无向边中有源点作为这条边的某个端点,那么规定其源点到这条边的另外一个端点的距离为2,即可。

Ac代码:

#include
#include
#include
using namespace std;
int dis[300005];
int vis[20005];
int map[6005][6005];
int bian[10000][3];
int n,m,ss,cont;
void Dij()
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)dis[i]=0x3f3f3f3f;
    dis[ss]=0;
    for(int i=0;idis[j])
            {
                u=j;
                tmp=dis[j];
            }
        }
        vis[u]=1;
        if(u==-1)continue;
        for(int j=1;j<=n;j++)
        {
            int v=j;
            int w=map[u][j];
            if(w==0x3f3f3f3f)continue;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==0x3f3f3f3f)dis[i]=-1;
    }
    int f=0;
    for(int i=1;i<=n;i++)
    {
        if(i==ss)continue;
        if(f==0)printf("%d",dis[i]);
        else printf(" %d",dis[i]);
        f++;
    }
    printf("\n");
}
void Slove()
{
    for(int i=0;i<6004;i++)
    {
        for(int j=0;j<6004;j++)
        {
            map[i][j]=1;
        }
    }
    for(int i=0;i
   
相关文章
最新文章
热点推荐