当前位置: 首页 > news >正文

题解:P6755 [BalticOI 2013] Pipes (Day1)

题目等价于:给定一个无向图和所有点的点权,给每条边确定一个边权,使得每个点的点权等于与其相连所有边的边权和除以二。特别地,如果无解或有无数解,只需输出 \(0\) 即可。

共有 \(m\) 个未知数(边权)和 \(n\) 个方程(点权)。由线性代数相关知识可知,若 \(m>n\),则要么方程组无解,要么存在自由未知数,使得方程组有无数解。我们不需要判断到底是无解还是无数解,因此当 \(m>n\) 时直接输出 \(0\) 即可。

因此我们只需考虑 \(m=n-1\)\(m=n\) 的情况。

假设存在一个度数为 \(1\) 的点 \(u\),则与它相连的边的边权可以唯一确定。我们使用拓扑排序不断地剥叶子,并同时确定相关边的边权。

\(m=n-1\),则拓扑排序后一定把这棵树剥得只剩一个节点,此时如果这个节点及相关边的权值符合题意,则我们已经构造出了解,否则一定无解。

\(m=n\),则这棵基环树被剥得只剩下一个环。

若剩下偶环,则要么方程组无解,要么存在至少一组解(废话)。假设存在一组解,我们对所有边依次编号,将奇数边的边权加一,偶数边的边权减一,则新的边权依然符合题意,故方程组存在无限解。因此,剩下偶环时要么方程组无解,要么方程组有无数解,直接输出 \(0\) 即可。

若剩下奇环,则由线性代数知识可知,这个方程组线性无关,此时必然存在唯一解。使用高斯消元法求解显然不现实。注意到每个方程只有两个未知数,并且形成一个环的形式,我们只需要设出一个未知数 \(x\),递推表示出其他所有未知数,最终进行求解即可。

时间复杂度 \(O(n+m)\)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {uniform_int_distribution<int> dist(L, R);return dist(rnd);
}template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}template<int mod>
inline unsigned int down(unsigned int x) {return x >= mod ? x - mod : x;
}template<int mod>
struct Modint {unsigned int x;Modint() = default;Modint(unsigned int x) : x(x) {}friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}friend Modint operator/(Modint a, Modint b) {return a * ~b;}friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}friend Modint operator~(Modint a) {return a ^ (mod - 2);}friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}friend Modint& operator++(Modint& a) {return a += 1;}friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}friend Modint& operator--(Modint& a) {return a -= 1;}friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}friend bool operator==(Modint a, Modint b) {return a.x == b.x;}friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};const int N = 1e5 + 5;int n, m, a[N], deg[N], vis[N], ans[N], k[N], b[N];
vector<tuple<int, int>> e[N];void toposort() {queue<int> q;rep(u, 1, n) if(deg[u] == 1) q.push(u);while(!q.empty()) {int u = q.front(); q.pop();for(auto [v, i]: e[u]) {if(!vis[i]) {vis[i] = 1;ans[i] = a[u] * 2;a[u] -= ans[i] / 2;a[v] -= ans[i] / 2;if(--deg[v] == 1) q.push(v);}}}
}int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;rep(i, 1, n) cin >> a[i];rep(i, 1, m) {int u, v;cin >> u >> v;e[u].emplace_back(v, i);e[v].emplace_back(u, i);++deg[u]; ++deg[v];}if(m > n) {cout << 0 << endl;return 0;}toposort();int cnt = 0;rep(u, 1, n) if(deg[u] == 2) ++cnt;if(cnt == 0) {bool ok = true;rep(u, 1, n) ok &= a[u] == 0;if(ok) rep(i, 1, m) cout << ans[i] << endl;else cout << 0 << endl;}else if(cnt % 2 == 0) cout << 0 << endl;else {vector<int> vec;rep(u, 1, n) {if(deg[u] == 2) {vec.push_back(u);break;}}rep(t, 0, cnt - 2) {int u = vec[t], w = t == 0 ? 0 : vec[t - 1];for(auto [v, i]: e[u]) {if(deg[v] == 2 && v != w) {vec.push_back(v);break;}}}rep(t, 0, cnt - 1) {int u = vec[t];if(t == 0) {k[t] = 1;b[t] = 0;}else {k[t] = -k[t - 1];b[t] = a[u] - b[t - 1];}}int K = k[0] + k[cnt - 1], B = b[0] + b[cnt - 1];int x = (a[vec[0]] - B) / K;rep(t, 0, cnt - 1) {int u = vec[t], w = vec[(t + 1) % cnt];for(auto [v, i]: e[u]) {if(v == w) {ans[i] = (k[t] * x + b[t]) * 2;break;}}}rep(i, 1, m) cout << ans[i] << endl;}return 0;
}
http://www.hskmm.com/?act=detail&tid=31765

相关文章:

  • Palantir 的“本体工程”的核心思路、技术架构与实践示例
  • P14164 [ICPC 2022 Nanjing R] 命题作文
  • C语言学习——整数变量
  • 语音合成技术从1秒样本学习表达风格
  • 我的高敏感和家人
  • 对称多项式
  • usb储存之BOT/UAS内核驱动
  • 简述flux思想?
  • 风控评分卡
  • 20232428 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • JAVA对象内存布局
  • 20232409 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • 10月15号
  • 记录一次客户现场环境,银河麒麟V10操作系统重启后,进入登录页面后卡死,鼠标键盘无响应的解决过程
  • 图 生成树
  • DolphinScheduler 3.1.9 单机版重启后,项目、流程定义等数据全部丢失
  • ManySpeech.AliParaformerAsr 使用指南
  • 资料拿取表
  • 易路:以“薪酬科技+AI”重塑中国企业薪酬管理新范式
  • 2025年太阳能板终极指南:选择、趋势与品牌推荐
  • 洛谷题单指南-进阶数论-CF776B Sherlock and his girlfriend
  • 下雪了 - L
  • 10/15
  • 2025 印尼物流专线公司推荐榜:聚焦合规高效,深圳恒翔物流凭实力登榜
  • 人文创新研究:在意义的边界探寻新境
  • 平面图最小割与对偶图最短路 - 干
  • 深入解析:Nodejs开发环境搭建
  • 项目管理:PERT/CPM
  • 智能物联网的实时通信之钥——WebSocket
  • 2025 苏州注册公司服务机构实用推荐:选择深度解析