結果

問題 No.1316 Maximum Minimum Spanning Tree
コンテスト
ユーザー oToToT
提出日時 2023-08-10 18:11:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 3,230 bytes
コンパイル時間 2,165 ms
コンパイル使用メモリ 218,408 KB
最終ジャッジ日時 2025-02-16 00:34:16
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 78
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0