题目描述
在一个 n 个节点（编号为1-n），n 条边的连通图中，每个点的权值都是正整数，每条边的权值为两个端点的权值的和。
已知各边权值，求各点权值。
输入格式
第一行一个整数 n 。
接下来 n 行，每行 3 个整数 x,y,z(1≤x,y≤n)，表示连接点 x 和 y 的边的权值为 z 。
数据保证合法，且没有自环或重边。给出的图中有且只有一个包括奇数个节点的环。
输出格式
$_math_inline$n$math_inline_$ 行。每行一个正整数 $_math_inline$w_i$math_inline_$ ，表示点 $_math_inline$i$math_inline_$ 的权值。
样例输入
13
21 2 3
32 3 5
41 3 4
样例输出
11
22
33
首先我们设第一个点的权值是ans
然后我们以第一个点为起点进行dfs
在dfs的过程中我们可以从中推出一点关于ans的表达式
由于保证有一个环
肯定有一个点出现两个表达式
那么这两个表达式一联立就解得了ans
Code
1/**
2 * author: Akvicor
3 * created: 2019-07-20 23-14-46
4**/
5
6#include <bits/stdc++.h>
7
8using namespace std;
9
10#ifdef DEBUG
11#define FAST_IO 17
12#else
13#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
14#define endl '\n'
15#endif
16
17#define rep(i, n) for(int i = 0; i < (n); ++i)
18#define reep(i, n) for(int i = 0; i <= (n); ++i)
19#define lop(i, a, n) for(int i = a; i < (n); ++i)
20#define loop(i, a, n) for(int i = a; i <= (n); ++i)
21#define prec(x) fixed << setprecision(x)
22#define ms(s, n) memset(s, n, sizeof(s))
23#define all(v) (v).begin(), (v).end()
24#define sz(x) ((int)(x).size())
25#define pb push_back
26#define mp make_pair
27#define fi first
28#define se second
29#define MOD(x) const int MOD = (int)x + 7
30#define MAXN(x) const int MAXN = (int)x + 7
31
32typedef long long LL;
33typedef unsigned long long ULL;
34typedef pair<int, int> PII;
35typedef vector<int> VI;
36typedef vector<PII> VII;
37
38const double EPS = 1e-6;
39const double PI = acos(-1.0);
40const int INF = 0x3f3f3f3f;
41const LL LINF = 0x7f7f7f7f7f7f7f7f;
42
43/** >------- Akvicor's Solution -------< **/
44
45MOD(1e9);
46MAXN(1e6);
47
48int ans;
49int vis[MAXN];
50PII p[MAXN];
51VII ve[MAXN];
52
53void dfs(int x, int fa){
54 rep(i, sz(ve[x])){
55 int tmp1 = ve[x][i].fi;
56 int tmp2 = ve[x][i].se;
57 if(vis[tmp1] == 1 && tmp1!=fa){
58 if(p[x].se==1){
59 ans = (tmp2-p[x].fi - p[tmp1].fi)/2;
60 }else{
61 ans = (p[tmp1].fi - tmp2 + p[x].fi)/2;
62 }
63 }
64 if(vis[tmp1] == 0){
65 vis[tmp1] = 1;
66 p[tmp1].fi = tmp2 - p[x].fi;
67 p[tmp1].se = p[x].se^1;
68 dfs(tmp1, x);
69 }
70 }
71}
72
73void solve(){
74 FAST_IO;
75
76 ms(vis, 0);
77 int n, u, v, w;
78 cin >> n;
79 loop(i, 1, n){
80 cin >> u >> v >> w;
81 ve[u].pb(mp(v, w));
82 ve[v].pb(mp(u, w));
83 }
84 vis[1] = 1;
85 p[1] = mp(0, 1);
86 dfs(1, 0);
87 loop(i, 1, n){
88 cout << (p[i].second==0 ? p[i].fi-ans : p[i].fi+ans) << endl;
89 }
90
91}
92
93/** >----------------------------------< **/
94
95int main(){
96
97#ifdef DEBUG
98 int DEBUGCNT = 0;
99 clock_t DEBUGstart, DEBUGfinish;
100 double DEBUGduration;
101 cout << ">------- Akvicor's Solution -------<" << endl;
102DEBUGLOOP:
103 DEBUGstart = clock();
104#endif
105
106 solve();
107
108#ifdef DEBUG
109 DEBUGfinish = clock();
110 DEBUGduration = (double)(DEBUGfinish - DEBUGstart)*1000 / CLOCKS_PER_SEC;
111 cout << " --> Test: #" << DEBUGCNT << " time: " << fixed << setprecision(4) << DEBUGduration << " ms <--" << endl;
112 ++DEBUGCNT;
113 if(DEBUGCNT < 100) goto DEBUGLOOP;
114 cout << ">----------------------------------<" << endl;
115#endif
116
117 return 0;
118}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。