結果
| 問題 | No.1316 Maximum Minimum Spanning Tree |
| ユーザー |
👑  hitonanode
|
| 提出日時 | 2020-12-11 01:38:49 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,188 bytes |
| コンパイル時間 | 11,865 ms |
| コンパイル使用メモリ | 383,592 KB |
| 実行使用メモリ | 8,696 KB |
| 最終ジャッジ日時 | 2023-10-20 02:13:49 |
| 合計ジャッジ時間 | 14,123 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
8,696 KB |
| testcase_01 | AC | 2 ms
4,348 KB |
| testcase_02 | AC | 2 ms
4,348 KB |
| testcase_03 | WA | - |
| testcase_04 | AC | 2 ms
4,348 KB |
| testcase_05 | AC | 2 ms
4,348 KB |
| testcase_06 | WA | - |
| testcase_07 | TLE | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#include <boost/multiprecision/cpp_dec_float.hpp>
// Simplex from <https://kopricky.github.io/code/Computation_Advanced/simplex.html>
// using Float = long double;
using Float = boost::multiprecision::cpp_dec_float_100;
#define EPS 1e-30
// max c * x s.t. A*x <= b, x >= 0
class Simplex {
private:
using Arr = vector<Float>;
using Mat = vector<vector<Float> >;
int* index;
Float** a;
int row, column, L;
void Set(const Mat& A, const Arr& b, const Arr& c){
infinity = none = false;
row = A.size(),column = A[0].size() + 1;
index = new int[row + column];
int i, j;
for(i = 0; i < row + column; i++) index[i] = i;
L = row;
a = new Float*[row + 2];
for(i = 0; i < row + 2; i++) a[i] = new Float[column + 1];
for(i = 0; i < row; i++){
for(j = 0; j < column - 1; j++) a[i][j] = -A[i][j];
a[i][column-1] = 1, a[i][column] = b[i];
if(a[L][column] > a[i][column]) L = i;
}
for(j = 0; j < column - 1; j++) a[row][j] = c[j];
a[row+1][column-1] = -1;
}
void solve(){
int E, i, j;
int* ls = new int[column + 2];
for(E = column - 1;;){
if(L < row){
swap(index[E], index[L + column]);
a[L][E] = 1 / a[L][E];
int prv = column + 1;
for(j = 0; j < column + 1; j++){
if(j != E){
a[L][j] *= -a[L][E];
if(abs(a[L][j]) > EPS) ls[prv] = j, prv = j;
}
}
ls[prv] = column + 1;
for(i = 0; i < row + 2; i++){
if(abs(a[i][E]) < EPS || i == L) continue;
for(j = ls[column + 1]; j < column + 1; j = ls[j]){
a[i][j] += a[i][E] * a[L][j];
}
a[i][E] *= a[L][E];
}
}
E = -1;
// Float pre = EPS;
for(j = 0; j < column; j++){
if(E < 0 || index[E] > index[j]){
if(a[row + 1][j] > EPS || (abs(a[row + 1][j]) < EPS && a[row][j] > EPS)) E = j;
// if(a[row + 1][j] > pre) E = j, pre = a[row + 1][j];
// else if(abs(a[row + 1][j]) < EPS && a[row][j] > pre) E = j, pre = a[row][j];
}
}
if(E < 0) break;
L = -1;
for(i = 0; i < row; i++){
if(a[i][E] < -EPS){
if(L < 0) L = i;
else if(a[L][column] / a[L][E] - a[i][column] / a[i][E] < -EPS) L = i;
else if(a[L][column] / a[L][E] - a[i][column] / a[i][E] < EPS && index[L] > index[i]) L = i;
// if(L < 0 || a[L][column] / a[L][E] - a[i][column] / a[i][E] < EPS) L = i;
}
}
if(L < 0){
infinity = true;
return;
}
}
if(a[row + 1][column] < -EPS){
none = true;
return;
}
x.assign(column - 1, 0);
for(i = 0; i < row; i++){
if(index[column + i] < column - 1) x[index[column + i]] = a[i][column];
}
ans = a[row][column];
}
public:
bool infinity, none;
Float ans;
Arr x;
Simplex(const Mat& A, const Arr& b, const Arr& c){
Set(A,b,c);
solve();
}
};
// UnionFind Tree (0-indexed), based on size of each disjoint set
struct UnionFind {
std::vector<int> par, cou;
UnionFind(int N = 0) : par(N), cou(N, 1) { iota(par.begin(), par.end(), 0); }
int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); }
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (cou[x] < cou[y]) std::swap(x, y);
par[y] = x, cou[x] += cou[y];
return true;
}
int count(int x) { return cou[find(x)]; }
bool same(int x, int y) { return find(x) == find(y); }
};
int main()
{
cin.tie(nullptr);
ios::sync_with_stdio(false);
int N, M, K;
cin >> N >> M >> K;
vector<int> A(M), B(M), C(M), D(M);
vector<pair<int, int>> c2i;
for (int eid = 0; eid < M; eid++) {
cin >> A[eid] >> B[eid] >> C[eid] >> D[eid];
A[eid]--, B[eid]--, c2i.emplace_back(C[eid], eid);
}
sort(c2i.begin(), c2i.end());
UnionFind uf(N);
vector<int> mstedge(M);
vector<vector<pair<int, int>>> tree(N);
vector<int> vpar(N, -1), epar(N, -1), depth(N);
long long ret = 0;
vector<long long> xdefault(M);
for (const auto [cost, eid] : c2i) {
const int u = A[eid], v = B[eid];
if (uf.unite(u, v)) {
mstedge[eid] = 1;
ret += (long long)C[eid] * K;
tree[u].emplace_back(v, eid);
tree[v].emplace_back(u, eid);
}
}
auto dfs = [&](auto &&self, int now, int prv, int dnow) -> void {
depth[now] = dnow;
for (const auto [nxt, eid] : tree[now]) {
if (nxt != prv) {
vpar[nxt] = now, epar[nxt] = eid;
self(self, nxt, now, dnow + 1);
}
}
};
dfs(dfs, 0, -1, 0);
vector<vector<Float>> matA(1, vector<Float>(M, 0));
vector<Float> vecb{1};
vector<Float> vecc(M);
auto add_constraint = [&](int emst, int eadd) {
vector<Float> v(M);
v[emst] = 1, v[eadd] = -1;
matA.emplace_back(v);
vecb.emplace_back(C[eadd] - C[emst]);
};
for (int eid = 0; eid < M; eid++) {
vecc[eid] = mstedge[eid] * K - D[eid];
if (!mstedge[eid]) {
int u = A[eid], v = B[eid];
while (depth[u] > depth[v]) add_constraint(epar[u], eid), u = vpar[u];
while (depth[v] > depth[u]) add_constraint(epar[v], eid), v = vpar[v];
while (u != v) add_constraint(epar[u], eid), u = vpar[u], add_constraint(epar[v], eid), v = vpar[v];
}
}
Simplex simplex(matA, vecb, vecc);
if (simplex.infinity) puts("-1");
else cout << ret + llround(simplex.ans) << '\n';
}