QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#225582 | #3855. Regional development | Energy_is_not_over# | RE | 0ms | 0kb | C++17 | 3.0kb | 2023-10-24 20:14:48 | 2023-10-24 20:14:49 |
answer
//
// Stvoreno Energom o 24.10.23. 13:48:00
//
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
using namespace std;
#ifdef Energy_is_not_over
#define DEBUG for (int _____DEBUG=1;_____DEBUG;_____DEBUG=0)
#define LOG(...) print(#__VA_ARGS__" ::",__VA_ARGS__)<<endl
template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (0)
#define LOG(...)
#endif
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
const int max_n = 1011, inf = 1000111222;
const int max_m = 10011;
int n, m, mod, bal[max_n];
int From[max_m], To[max_m], val[max_m];
vector<int> g[max_n];
int parent[max_n];
queue<int> q;
bool augment() {
bool has_start = false;
for (int i = 0; i < n; ++i) {
parent[i] = -1;
if (bal[i] > 0) {
assert(bal[i] % mod == 0);
parent[i] = -2;
q.push(i);
has_start = true;
}
}
if (!has_start) {
return false;
}
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v]) {
const int to = v ^ From[id] ^ To[id];
if ((val[id] > 0) == (From[id] == v)) {
if (parent[to] == -1) {
parent[to] = id;
q.push(to);
}
}
}
}
int finish = -1;
for (int i = 0; i < n; ++i) {
if (bal[i] < 0 && parent[i] >= 0) {
finish = i;
break;
}
}
assert(finish != -1);
// cout << finish << " " << parent[finish] << " ";
bal[finish] += mod;
while (parent[finish] != -2) {
const int id = parent[finish];
// cout << "$" << id << "%" << endl;
if (val[id] > 0) {
val[id] -= mod;
} else {
val[id] += mod;
}
finish ^= From[id] ^ To[id];
}
// cout << finish << endl;
bal[finish] -= mod;
return true;
}
int main() {
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> mod;
for (int i = 0; i < m; ++i) {
cin >> From[i] >> To[i] >> val[i];
--From[i];
--To[i];
g[From[i]].push_back(To[i]);
g[To[i]].push_back(From[i]);
bal[From[i]] += val[i];
bal[To[i]] -= val[i];
}
while (augment()) {
// DEBUG {
// for (int i = 0; i < m; ++i) {
// cout << val[i] << " ";
// }
// cout << " ";
// for (int i = 0; i < n; ++i) {
// cout << bal[i] << " ";
// }
// cout << endl;
// }
}
for (int i = 0; i < m; ++i) {
cout << val[i] << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
10 23 3 2 10 1 2 6 1 6 9 1 7 9 1 6 7 1 3 6 1 1 3 1 1 6 2 6 10 1 2 9 1 4 9 2 4 7 2 3 10 2 3 9 1 6 8 1 7 8 2 3 5 1 5 9 1 8 9 2 3 8 2 1 5 2 1 4 1 5 10 2