AtCoder Regular Contest 090 D People on a Line

题目链接https://arc090.contest.atcoder.jp/tasks/arc090_b

题意:给你若干对人的位置关系,让你判断是否存在这样一组坐标满足这些对应的位置关系,一个点上可以站多个人。

思路:对于给定的关系(L,R,D),我们建立双向边LR连一条边长为D的边,RL连一条边长为-D的边,然后扫一遍所有的点,如果这个点没有被访问过,那么就以这个点为起点出发做一遍DFS,不断更新沿路访问的点的相对位置大小,如果出现冲突直接返回,如此即可。

int n,m,L,R,D,dis[maxn];
bool vis[maxn];
vector<pair<int,int> >G[maxn];
bool dfs(int u){
    vis[u]=true;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i].F;
        if (!vis[v]){
            dis[v]=dis[u]+G[u][i].S;
            if (!dfs(v)) return false;
        }
        else if (dis[u]+G[u][i].S!=dis[v]) return false;
    }
    return true;
}
int main(){
    read(n),read(m);
    for (int i=1;i<=m;i++){
        read(L),read(R),read(D);
        G[L].pb(make_pair(R,D));
        G[R].pb(make_pair(L,-D));
    }
    for (int i=1;i<=n;i++){
        if (!vis[i]){
            if (!dfs(i)) return puts("No"),0;
        }
    }
    puts("Yes");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注