#899982 (C++17) No.1316 Maximum Minimum Spanning Tree

提出ソース

結果

問題	No.1316 Maximum Minimum Spanning Tree
ユーザー	oToToT
提出日時	2023-08-10 18:11:23
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	19 ms / 2,000 ms
コード長	3,230 bytes
コンパイル時間	2,723 ms
コンパイル使用メモリ	225,856 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-11-17 02:54:24
合計ジャッジ時間	5,726 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	3 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	12 ms 5,248 KB
testcase_08	AC	13 ms 5,248 KB
testcase_09	AC	16 ms 5,248 KB
testcase_10	AC	15 ms 5,248 KB
testcase_11	AC	4 ms 5,248 KB
testcase_12	AC	4 ms 5,248 KB
testcase_13	AC	4 ms 5,248 KB
testcase_14	AC	4 ms 5,248 KB
testcase_15	AC	15 ms 5,248 KB
testcase_16	AC	18 ms 5,248 KB
testcase_17	AC	16 ms 5,248 KB
testcase_18	AC	17 ms 5,248 KB
testcase_19	AC	3 ms 5,248 KB
testcase_20	AC	3 ms 5,248 KB
testcase_21	AC	3 ms 5,248 KB
testcase_22	AC	3 ms 5,248 KB
testcase_23	AC	3 ms 5,248 KB
testcase_24	AC	4 ms 5,248 KB
testcase_25	AC	3 ms 5,248 KB
testcase_26	AC	3 ms 5,248 KB
testcase_27	AC	3 ms 5,248 KB
testcase_28	AC	3 ms 5,248 KB
testcase_29	AC	3 ms 5,248 KB
testcase_30	AC	3 ms 5,248 KB
testcase_31	AC	3 ms 5,248 KB
testcase_32	AC	3 ms 5,248 KB
testcase_33	AC	3 ms 5,248 KB
testcase_34	AC	3 ms 5,248 KB
testcase_35	AC	3 ms 5,248 KB
testcase_36	AC	2 ms 5,248 KB
testcase_37	AC	2 ms 5,248 KB
testcase_38	AC	3 ms 5,248 KB
testcase_39	AC	3 ms 5,248 KB
testcase_40	AC	3 ms 5,248 KB
testcase_41	AC	3 ms 5,248 KB
testcase_42	AC	3 ms 5,248 KB
testcase_43	AC	8 ms 5,248 KB
testcase_44	AC	8 ms 5,248 KB
testcase_45	AC	12 ms 5,248 KB
testcase_46	AC	11 ms 5,248 KB
testcase_47	AC	9 ms 5,248 KB
testcase_48	AC	8 ms 5,248 KB
testcase_49	AC	9 ms 5,248 KB
testcase_50	AC	8 ms 5,248 KB
testcase_51	AC	7 ms 5,248 KB
testcase_52	AC	7 ms 5,248 KB
testcase_53	AC	10 ms 5,248 KB
testcase_54	AC	11 ms 5,248 KB
testcase_55	AC	15 ms 5,248 KB
testcase_56	AC	14 ms 5,248 KB
testcase_57	AC	14 ms 5,248 KB
testcase_58	AC	15 ms 5,248 KB
testcase_59	AC	15 ms 5,248 KB
testcase_60	AC	14 ms 5,248 KB
testcase_61	AC	15 ms 5,248 KB
testcase_62	AC	15 ms 5,248 KB
testcase_63	AC	14 ms 5,248 KB
testcase_64	AC	15 ms 5,248 KB
testcase_65	AC	16 ms 5,248 KB
testcase_66	AC	18 ms 5,248 KB
testcase_67	AC	17 ms 5,248 KB
testcase_68	AC	15 ms 5,248 KB
testcase_69	AC	16 ms 5,248 KB
testcase_70	AC	16 ms 5,248 KB
testcase_71	AC	17 ms 5,248 KB
testcase_72	AC	19 ms 5,248 KB
testcase_73	AC	18 ms 5,248 KB
testcase_74	AC	18 ms 5,248 KB
testcase_75	AC	3 ms 5,248 KB
testcase_76	AC	4 ms 5,248 KB
testcase_77	AC	3 ms 5,248 KB
testcase_78	AC	15 ms 5,248 KB
testcase_79	AC	15 ms 5,248 KB
testcase_80	AC	17 ms 5,248 KB
testcase_81	AC	10 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#ifndef CHIKA_DINIC_HPP
#define CHIKA_DINIC_HPP

#include <cinttypes>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

template <typename Cap = int64_t> class Dinic {
private:
  struct E {
    int to, rev;
    Cap cap;
  };
  int n, ed;
  std::vector<std::vector<E>> G;
  std::vector<int> lv, idx;
  std::vector<std::pair<int, int>> inv;
  bool BFS(int st) {
    lv.assign(n, -1);
    std::queue<int> bfs;
    bfs.push(st);
    lv[st] = 0;
    while (not bfs.empty()) {
      int u = bfs.front();
      bfs.pop();
      for (auto e : G[u]) {
        if (e.cap <= 0 or lv[e.to] != -1)
          continue;
        bfs.push(e.to);
        lv[e.to] = lv[u] + 1;
      }
    }
    return lv[ed] != -1;
  }
  Cap DFS(int u, Cap f) {
    if (u == ed)
      return f;
    Cap ret = 0;
    for (int &i = idx[u]; i < int(G[u].size()); ++i) {
      auto &e = G[u][i];
      if (e.cap <= 0 or lv[e.to] != lv[u] + 1)
        continue;
      Cap nf = DFS(e.to, std::min(f, e.cap));
      ret += nf;
      e.cap -= nf;
      f -= nf;
      G[e.to][e.rev].cap += nf;
      if (f == 0)
        return ret;
    }
    if (ret == 0)
      lv[u] = -1;
    return ret;
  }

public:
  Dinic(int n_) : n(n_), G(n) {}
  void add_edge(int u, int v, Cap c) {
    G[u].push_back({v, int(G[v].size()), c});
    G[v].push_back({u, int(G[u].size()) - 1, 0});
    inv.emplace_back(v, int(G[v].size()) - 1);
  }
  Cap operator()(int st, int ed_) {
    ed = ed_;
    Cap ret = 0;
    while (BFS(st)) {
      idx.assign(n, 0);
      Cap f = DFS(st, std::numeric_limits<Cap>::max());
      ret += f;
      if (f == 0)
        break;
    }
    return ret;
  }
  Cap operator[](int i) const { return G[inv[i].first][inv[i].second].cap; }
  std::vector<bool> get_visible(int s) const {
    std::vector<bool> vis(n);
    std::queue<int> bfs;
    bfs.push(s);
    vis[s] = true;
    while (not bfs.empty()) {
      int u = bfs.front();
      bfs.pop();
      for (auto e : G[u]) {
        if (vis[e.to] or e.cap == 0)
          continue;
        bfs.push(e.to);
        vis[e.to] = true;
      }
    }
    return vis;
  }
};

#endif // CHIKA_DINIC_HPP

#include <bits/stdc++.h>
using namespace std;

constexpr int kInf = 1 << 30;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m, k;
	cin >> n >> m >> k;
	vector<tuple<int, int, int, int>> e(m);
	for (auto &[u, v, c, d] : e)
		cin >> u >> v >> c >> d;

	sort(e.begin(), e.end(), [](const auto &lhs, const auto &rhs) {
		return get<2>(lhs) < get<2>(rhs);
	});
	vector<int64_t> y(m);
	for (int i = 0; i < m; ++i) {
		auto [u, v, c, d] = e[i];

		const int S = 0, T = n + 1;
		Dinic<int64_t> flow(n + 2);
		for (int j = 0; j < m; ++j) {
			if (i == j)
				continue;
			auto [uj, vj, _, __] = e[j];
			flow.add_edge(S, uj, y[j]);
			flow.add_edge(uj, vj, y[j]);
		}
		for (int j = 1; j <= n; ++j) {
			if (j == u or j == v)
				continue;
			flow.add_edge(j, T, k);
		}
		
		y[i] = flow(S, T) + k - accumulate(y.begin(), y.end(), 0LL);
		y[i] = min<int64_t>(y[i], d);
	}
	
	if (accumulate(y.begin(), y.end(), 0LL) != 1LL * k * (n - 1)) {
		cout << "-1\n";
		return 0;
	}

	int64_t ans = 0;
	for (int i = 0; i < m; ++i)
		ans += y[i] * get<2>(e[i]);
	cout << ans << '\n';
	return 0;
}

yukicoder

結果

テストケース

ソースコード