AtCoder Beginner Contest 320 Problem D - Relative Position 题解
题目保证不矛盾,就可以直接 vector 建图,然后 dfs 一遍,边权为 \((w_x,w_y)\) 表示坐标的差,从 \(u=1\) 开始搜索,设点 \(u,v\) 有一条无向边,\(v_x = u_x + w_x,v_y = u_y + w_y\),最后如果没有被标记过的话(也就是没有遍历过),那么无解。
AC Code
#include<iostream>
#include<vector>
using namespace std;
const int MAXN = 2e5 + 10;
struct node{
int t, x, y;
};
struct ANS{
long long a, b;
}ans[MAXN];
vector<node> G[MAXN];
int n, m, a, b, x, y;
bool vis[MAXN];
void dfs(int u, long long x, long long y){
if (vis[u]){
return;
}
vis[u] = 1,ans[u] = {x, y};
for (int i = 0; i < G[u].size(); i++){
dfs(G[u][i].t, x + G[u][i].x, y + G[u][i].y);
}
}
int main(){
cin >> n >> m;
for (int i = 1; i <= m; i++){
cin >> a >> b >> x >> y;
G[a].push_back({b, x, y}), G[b].push_back({a, -x, -y});
}
dfs(1, 0, 0);
for (int i = 1; i <= n; i++){
if (!vis[i]){
cout << "undecidable\n";
}
else {
cout << ans[i].a << ' ' << ans[i].b << '\n';
}
}
return 0;
}
标签:int,题解,dfs,ABC320D,vis,MAXN,long
From: https://www.cnblogs.com/codehyx-blog/p/solution-abc320_d.html