cf Inverse the Problem （最小生成树+DFS）

题意：

N个点。N行N列d[i][j]。

d[i][j]：结点i到结点j的距离。

问这N个点是否可能是一棵树。是输出YES，否则输出NO。

思路：

假设这个完全图是由一棵树得来的，则我们对这个完全图求最小生成树，得到原树。（画个图就明白）

故我们对完全图求最小生成树，然后用DFS从这棵树上的每个点出发，判断距离是否和矩阵d相同。

注意：

用vector存与每个点相连树枝的另一端，否则超时。用了vector也耗了1400多秒，限时2s。

代码：

#include <cstdio>

#include <iostream>

#include <string.h>

#include <cstdlib>

#include <algorithm>

#include <queue>

#include <vector>

#include <cmath>

#include <map>

#include <stack>

using namespace std;

int const uu[4] = {1,-1,0,0};

int const vv[4] = {0,0,1,-1};

typedef long long ll;

int const maxn = 50005;

int const inf = 0x3f3f3f3f;

ll const INF = 0x7fffffffffffffffll;

double eps = 1e-10;

double pi = acos(-1.0);

#define rep(i,s,n) for(int i=(s);i<=(n);++i)

#define rep2(i,s,n) for(int i=(s);i>=(n);--i)

#define mem(v,n) memset(v,(n),sizeof(v))

#define lson l, m, rt<<1

#define rson m+1, r, rt<<1|1

struct node{

    int x,y,len;

};

int n;

int d[2005][2005], a[2005][2005];

int fa[2005];

node edge[4000005];

vector<int> graph[2005];

bool cmp(node a,node b){

    return a.len<b.len;

}

int findFa(int x){

    if(fa[x]!=x) fa[x]=findFa(fa[x]);

    return fa[x];

}

bool dfs(int start,int x,int fa,int weight){

    if(d[start][x]!=weight){

        return false;

    }

    int L=graph[x].size();

    rep(i,0,L-1){

        int v=graph[x][i];

        if(v==fa) continue;

        bool t=dfs(start,v,x,weight+a[x][v]);

        if(!t) return false;

    }

    return true;

}

int main(){

    scanf("%d",&n);

    rep(i,1,n) rep(j,1,n) scanf("%d",&d[i][j]);

    rep(i,1,n) if(d[i][i]!=0){

        printf("NO\n");

        return 0;

    }

    rep(i,1,n-1) rep(j,i+1,n){

        if(d[i][j]==0 || (d[i][j]!=d[j][i])){

            printf("NO\n");

            return 0;

        }

    }

    int eNum=0;

    mem(a,0);

    rep(i,1,n-1) rep(j,i+1,n){

        edge[++eNum].x=i, edge[eNum].y=j;

        edge[eNum].len=d[i][j];

    }

    sort(edge+1,edge+1+eNum,cmp);

    rep(i,1,n) fa[i]=i;

    rep(i,1,n) graph[i].clear();

    rep(i,1,eNum){

        int xx=edge[i].x, yy=edge[i].y;

        int fx=findFa(xx), fy=findFa(yy);

        if(fx!=fy){

            fa[fx]=fy;

            a[xx][yy]=a[yy][xx]=edge[i].len;

            graph[xx].push_back(yy);

            graph[yy].push_back(xx);

        }

    }

    int t=findFa(1);

    rep(i,2,n) if(findFa(i)!=t){

        printf("NO\n");

        return 0;

    }

    rep(i,1,n){

        bool k=dfs(i,i,-1,0); //从顶点i出发

        if(!k){

            printf("NO\n");

            return 0;

        }

    }

    printf("YES\n");

}

巴特西

cf Inverse the Problem （最小生成树+DFS）

最新文章

热门文章