一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

269C - Flawed Flow

---

二、解题报告

1、思路分析

考虑源点相连的边的方向是确定的，因为流量是从源点往外流的

我们设cap[u] 为 和u相连边的容量和，显然入边容量要和出边容量相等，我们不妨将cap 都 除以2

我们从源点开始往外更新流量，对所有邻接点 容量和减去相连边的容量

源点更新后一定存在某个点剩余容量为0，即其剩下的边的方向都是从该点出发的

由于原图无环，我们不断dfs一定能够不断地找到这样地点，知道更新到汇点

2、复杂度

时间复杂度： O(N + M)空间复杂度：O(N + M)

3、代码详解

 ​

#include <bits/stdc++.h>
// #include <ranges>
// #define DEBUG
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr double eps = 1e-9;constexpr int N = 1005;void solve() {int n, m;std::cin >> n >> m;std::vector<std::vector<std::array<int, 3>>> adj(n);std::vector<int> cap(n);for (int i = 1, u, v, c; i <= m; ++ i) {std::cin >> u >> v >> c;-- u, -- v;adj[u].push_back({v, c, i});adj[v].push_back({u, c, -i});cap[u] += c, cap[v] += c;}for (auto& x : cap)x /= 2;std::vector<int> ans(m, -1);auto dfs = [&](auto&& self, int u) -> void {for (auto& [v, c, i] : adj[u]) {if (~ans[abs(i) - 1]) continue;ans[abs(i) - 1] = i > 0 ? 0 : 1;if (!(cap[v] -= c)) {if (v + 1 != n)self(self, v);}}};dfs(dfs, 0);for (int x : ans)std::cout << x << '\n';
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
} ();int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif     int t = 1;// std::cin >> t;while (t --)solve();return 0;
}