BOI - Pipes
Source: BOI13 - Pipes
Tags: Graph, Maths
Problem:
Nguồn cung cấp nước của thành phố Hotham gồm có N hồ chứa nước nối với nhau bằng M ống dẫn nước. Mọi hồ chứa nước đều thông với nhau, trực tiếp hoặc trung gian qua những hồ chứa khác, và giữa hai hồ chứa khác nhau chỉ có tối đa một ống dẫn nối trực tiếp.
Jester tấn công vào hệ thống cung cấp nước của thành phố Hotham bằng cách phá thủng một số ống dẫn nước làm tại ống đó bị rò rỉ ra một lượng nước, điều đó làm cho hai hồ chứa nước được nối bằng ống dẫn đó cũng bị thất thoát một lượng tương ứng bằng nửa lượng rò rỉ ra. Tức là, tại ống dẫn p nối hồ chứa u và hồ chứa v, nếu Jester làm rò rỉ tại đó một lượng là 2v (mét khối) thì mỗi bên hồ chứa sẽ thất thoát một lượng là v (mét khối).
Để làm cho tình hình càng trở nên rối ren, và cũng là một tên thích đùa cợt, Jester cũng bơm thêm nước vào một số ống dẫn nước, đồng thời hai hồ chứa được nối bằng ống dẫn đó cũng được tăng lên một lượng tương ứng bằng nửa lượng được bơm vào. Tức là, tại ống dẫn p nối hồ chứa u và hồ chứa v, nếu Jester bơm vào đó một lượng là 2v (mét khối) thì mỗi bên hồ chứa sẽ được tăng lên một lượng là v (mét khối).
Thị trưởng thành phố Gotham đã trang bị cảm biến ở các hồ chứa để theo dõi sự thay đổi lượng nước trong các hồ chứa, tuy nhiên điều này không thực sự cho giúp ích lắm cho việc biết được cụ thể Jester đã phá các ống dẫn nước ra sao. Bằng các số liệu thu thập được, bạn hãy giúp thị trưởng xác định lượng nước mà Jester đã làm rò rỉ/ bơm thêm ở các ống dẫn nước. Jester luôn làm rò rỉ/ bơm thêm tại các ống dẫn một lượng là số chẵn.
Dòng đầu là 2 số N, M. N dòng sau mỗi dòng chứa một số c[i] thể hiện sự thay đổi lượng nước ở hồ chứa i (c[i] âm nếu bị thất thoát, c[i] dương nếu được tăng lên, c[i] = 0 nếu không có thay đổi). M dòng sau mỗi dòng chứa 2 số u, v thể hiện có ống dẫn nối hồ chứa u và hồ chứa v.
In ra M dòng mỗi dòng chứa một số x[i] (x[i] âm nếu Jester làm rò rỉ ống nối thứ i, x[i] dương nếu Jester bơm thêm vào ống nối thứ i, x[i] = 0 nếu Jester không tác động gì lên ống nối thứ i). Nếu không thể xác định cụ thể Jester đã tác động như thế nào hoặc phát hiện số liệu có sai sót (không tồn tại cách nào để ra được số liệu đó) thì in ra 0.
N ≤ 1e5. M ≤ 5e5. |c[i]| ≤ 1e9. Nếu có đáp án đảm bảo x[i] nguyên có giá trị tuyệt đối không quá 1e9.
Ví dụ:
Input:
4 3
-1
1
-3
1
1 2
1 3
1 4
Tags: Graph, Maths
Problem:
Nguồn cung cấp nước của thành phố Hotham gồm có N hồ chứa nước nối với nhau bằng M ống dẫn nước. Mọi hồ chứa nước đều thông với nhau, trực tiếp hoặc trung gian qua những hồ chứa khác, và giữa hai hồ chứa khác nhau chỉ có tối đa một ống dẫn nối trực tiếp.
Jester tấn công vào hệ thống cung cấp nước của thành phố Hotham bằng cách phá thủng một số ống dẫn nước làm tại ống đó bị rò rỉ ra một lượng nước, điều đó làm cho hai hồ chứa nước được nối bằng ống dẫn đó cũng bị thất thoát một lượng tương ứng bằng nửa lượng rò rỉ ra. Tức là, tại ống dẫn p nối hồ chứa u và hồ chứa v, nếu Jester làm rò rỉ tại đó một lượng là 2v (mét khối) thì mỗi bên hồ chứa sẽ thất thoát một lượng là v (mét khối).
Để làm cho tình hình càng trở nên rối ren, và cũng là một tên thích đùa cợt, Jester cũng bơm thêm nước vào một số ống dẫn nước, đồng thời hai hồ chứa được nối bằng ống dẫn đó cũng được tăng lên một lượng tương ứng bằng nửa lượng được bơm vào. Tức là, tại ống dẫn p nối hồ chứa u và hồ chứa v, nếu Jester bơm vào đó một lượng là 2v (mét khối) thì mỗi bên hồ chứa sẽ được tăng lên một lượng là v (mét khối).
Thị trưởng thành phố Gotham đã trang bị cảm biến ở các hồ chứa để theo dõi sự thay đổi lượng nước trong các hồ chứa, tuy nhiên điều này không thực sự cho giúp ích lắm cho việc biết được cụ thể Jester đã phá các ống dẫn nước ra sao. Bằng các số liệu thu thập được, bạn hãy giúp thị trưởng xác định lượng nước mà Jester đã làm rò rỉ/ bơm thêm ở các ống dẫn nước. Jester luôn làm rò rỉ/ bơm thêm tại các ống dẫn một lượng là số chẵn.
Dòng đầu là 2 số N, M. N dòng sau mỗi dòng chứa một số c[i] thể hiện sự thay đổi lượng nước ở hồ chứa i (c[i] âm nếu bị thất thoát, c[i] dương nếu được tăng lên, c[i] = 0 nếu không có thay đổi). M dòng sau mỗi dòng chứa 2 số u, v thể hiện có ống dẫn nối hồ chứa u và hồ chứa v.
In ra M dòng mỗi dòng chứa một số x[i] (x[i] âm nếu Jester làm rò rỉ ống nối thứ i, x[i] dương nếu Jester bơm thêm vào ống nối thứ i, x[i] = 0 nếu Jester không tác động gì lên ống nối thứ i). Nếu không thể xác định cụ thể Jester đã tác động như thế nào hoặc phát hiện số liệu có sai sót (không tồn tại cách nào để ra được số liệu đó) thì in ra 0.
N ≤ 1e5. M ≤ 5e5. |c[i]| ≤ 1e9. Nếu có đáp án đảm bảo x[i] nguyên có giá trị tuyệt đối không quá 1e9.
Ví dụ:
Input:
4 3
-1
1
-3
1
1 2
1 3
1 4
Output:
2
-6
2
Input:
4 5
1
2
1
2
1 2
2 3
3 4
4 1
1 3
Output:
0
Solution:
Gán p[i] = x[i] / 2, ta có c[u] = tổng(p[i]) với mọi ống dẫn i nối trực tiếp đến hồ chứa u, như vậy từ bước này ta có thể quy bài toán thành một hệ phương trình có N phương trình và M ẩn. Việc cần làm tiếp theo là chúng ta sẽ đi giải hệ phương trình này.
Nếu số phương trình ít hơn số ẩn, hệ phương trình sẽ có vô số nghiệm, lúc này ta in ra 0 do không thể xác định được nghiệm cụ thể.
Nếu số phương trình nhiều hơn số ẩn, trường hợp duy nhất là M = N - 1, tức đồ thị lúc này là cây, ta có thể giải quyết dễ dàng bằng nhận xét, những đỉnh là lá thì c[u] = p[i], từ đó giải quyết dần vào trong. Tuy nhiên trường hợp này có thể tồn tại trường hợp vô nghiệm, do đó khi giải quyết còn 1 cạnh cuối cùng cần xét xem c[u] và c[v] có bằng nhau không (u và v là 2 đỉnh được nối bằng cạnh cuối cùng đó).
Với trường hợp M = N, trong lý thuyết đồ thị thì trường hợp này đồ thị tồn tại duy nhất một chu trình đơn, tuy nhiên vẫn có những nhánh khác không thuộc chu trình. Những nhánh này thực chất cũng lại là những cây con khác của đồ thị, ta có thể giải quyết đơn giản phần này và cập nhật lại đỉnh nối trực tiếp với cây con đó. Sau khi đã tỉa xong các nhánh không thuộc chu trình, ta còn một chu trình đơn. Lúc này, gọi N' là số lượng đỉnh còn lại trong chu trình, gồm các đỉnh c[1]', c[2]', ..., c[N']' (c[i]' là đỉnh thứ i trong chu trình) và các cạnh liên tiếp lần lượt là p[1]', p[2]', ..., p[N']' (p[i]' nối đỉnh thứ i và i + 1 trong chu trình, p[N']' nối đỉnh thứ N' và 1), ta có:
Nếu N' là số chẵn, giả sử ta có một lời giải, ta có thể cộng một số bất kỳ vào p[1]', p[3]', ..., p[N' - 1]' và trừ một số tương ứng vào p[2]', p[4]', ..., p[N']' mà vẫn giữ nguyên được c[u] tại tất cả các đỉnh u trong chu trình, do đó nếu N' là số chẵn, lời giải không thể duy nhất được.
Nếu N' là số lẻ, ta có:
c[1]' = p[1]' + p[N']'
<=> p[N']' = c[1]' - p[1]'
<=> p[N']' = c[1]' - c[2]' + p[2]'
<=> ...
<=> p[N']' = c[1]' - c[2]' + c[3]' - ... + c[N']' - p[N']'
<=> p[N']' = (c[1]' - c[2]' + c[3]' - ... + c[N']') / 2
Lúc này ta đã có giá trị của một ẩn, từ đây ta có thể suy ra nghiệm của hệ phương trình.
Bạn cũng có thể tham khảo lời giải từ BTC.
Code:
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int n, m, c[100015], adjcnt[100015], p[500000], ncycle, sum, oper = 1;
vector <pair <int, int>> a[100015];
pair <int, int> trace[100015];
bool trim_graph() {
queue <int> q;
for (int u = 1; u <= n; ++u)
if (adjcnt[u] == 1)
q.push(u);
while (!q.empty()) {
int u = q.front(); q.pop();
--ncycle;
for (auto e: a[u])
if (adjcnt[e.first]) {
int v = e.first;
--adjcnt[u]; --adjcnt[v];
p[e.second] = 2 * c[u];
c[v] -= c[u];
if (ncycle == 1 && c[v])
return false;
if (adjcnt[v] == 1)
q.push(v);
}
}
return true;
}
void dfs(int u) {
sum += c[u] * oper; oper = -oper;
for (auto e: a[u])
if (adjcnt[e.first] == 2) {
int v = e.first;
--adjcnt[u]; --adjcnt[v],
trace[u] = e; dfs(v);
return;
}
for (auto e: a[u])
if (adjcnt[e.first] == 1) {
int v = e.first;
p[e.second] = sum;
c[u] -= sum / 2;
c[v] -= sum / 2;
return;
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int u = 1; u <= n; ++u)
cin >> c[u];
for (int i = 0, u, v; i < m; ++i)
cin >> u >> v,
a[u].push_back({v, i}),
a[v].push_back({u, i}),
++adjcnt[u], ++adjcnt[v];
if (m > n) goto NO;
ncycle = n;
if (!trim_graph()) goto NO;
if (m == n) {
if (ncycle % 2 == 0) goto NO;
int u;
for (u = 1; u <= n; ++u)
if (adjcnt[u] == 2) {
dfs(u); break;
}
for (; trace[u].first; u = trace[u].first)
p[trace[u].second] = 2 * c[u],
c[trace[u].first] -= c[u];
}
for (int i = 0; i < m; ++i)
cout << p[i] << '\n';
return 0;
NO: cout << 0;
}
Nhận xét
Đăng nhận xét