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

提出ソース

結果

問題	No.1316 Maximum Minimum Spanning Tree
ユーザー	opt
提出日時	2020-12-11 15:33:37
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	9,167 bytes
コンパイル時間	3,359 ms
コンパイル使用メモリ	243,296 KB
実行使用メモリ	13,760 KB
最終ジャッジ日時	2024-09-19 22:02:11
合計ジャッジ時間	8,340 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,760 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	1,903 ms 6,940 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
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	--	-

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

ソースコード

raw source code

// WA 解法
// 全域木を時間いっぱいいろいろ試す．全域木を固定すると，最小費用循環流に帰着される．

#include <bits/stdc++.h>
using namespace std;
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#ifdef LOCAL
void debug_out() { cerr << endl; }
template <class Head, class... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#define debug(...) cerr << 'L' << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << 'L' << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
template<class T> using V = vector<T>;
using ll = long long;
using Vi = V<int>;  using VVi = V<Vi>;
template<class T> inline bool chmin(T &a, const T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T &a, const T b) { if (a < b) { a = b; return true; } return false; }
inline ll cDiv(const ll x, const ll y) { return (x+y-1) / y; } // ceil(x/y)
inline int fLog2(const ll x) { assert(x > 0); return 63-__builtin_clzll(x); } // floor(log2(x))
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
const ll INFll = (1ll<<60) - 1;


///////////////////////////////////////////////////////////////////////////
// Minimum cost b-flow by TKO919: https://judge.yosupo.jp/submission/23643
///////////////////////////////////////////////////////////////////////////

template<typename Flow,typename Cost,int type=1>struct MinCostFlow{ //Maximize=-1
   struct ptr{int v_id,e_id;};
   struct edge{
      int from,to,rev; Flow flow,cap; Cost weight;
      edge(int _f,int _t,Flow _c,Cost _w,int _r)
         :from(_f),to(_t),flow(0),cap(_c),weight(_w),rev(_r){}
      Flow residual_cap()const{return cap-flow;}
   };
   int n; vector<vector<edge>> g; vector<Flow> b,pot;
   MinCostFlow(int _n):n(_n),g(_n),b(_n),pot(_n){}
   ptr add_edge(int from,int to,Flow lb,Flow ub,Cost cost){
      int f_id=g[from].size(),t_id=(from==to?f_id+1:g[to].size());
      g[from].push_back(edge(from,to,ub,cost*type,t_id));
      g[to].push_back(edge(to,from,-lb,-cost*type,f_id));
      return ptr{from,f_id};
   }
   void add_supply(int v,Flow amount){b[v]+=amount;}
   Flow get_flow(ptr& p){return g[p.v_id][p.e_id].flow;}

   Cost farthest;
   vector<Cost> dist; vector<edge*> par;
   vector<int> exc,def;
   void push(edge& e,Flow amount){
      e.flow+=amount; g[e.to][e.rev].flow-=amount;
   }
   Cost residual_cost(int from,int to,edge& e){
      return e.weight+pot[from]-pot[to];
   }

   bool dual(const Flow& delta){
      dist.assign(n,numeric_limits<Cost>::max()); par.assign(n,nullptr);
      exc.erase(remove_if(all(exc),[&](int v){return b[v]<delta;}),exc.end());
      def.erase(remove_if(all(def),[&](int v){return b[v]>-delta;}),def.end());
      priority_queue<pair<Cost,int>,vector<pair<Cost,int>>,greater<>> pq;
      for(auto& v:exc)pq.push({dist[v]=0,v});
      farthest=0; int def_cnt=0;
      while(!pq.empty()){
         auto [d,u]=pq.top(); pq.pop();
         if(dist[u]<d)continue;
         farthest=d;
         if(b[u]<=-delta)def_cnt++;
         if(def_cnt>=(int)def.size())break;
         for(auto& e:g[u]){
            if(e.residual_cap()<delta)continue;
            int v=e.to; Cost nd=d+residual_cost(u,v,e);
            if(nd>=dist[v])continue;
            pq.push({dist[v]=nd,v}); par[v]=&e;
         }
      }
      rep(v,n)pot[v]+=min(dist[v],farthest);
      return def_cnt>0;
   }
   void primal(const Flow& delta){
      for(auto& t:def){
         if(dist[t]>farthest)continue;
         Flow f=-b[t]; int v;
         for(v=t;par[v]!=nullptr;v=par[v]->from){
            chmin(f,par[v]->residual_cap());
         }
         chmin(f,b[v]); f-=f%delta;
         if(f<=0)continue;
         for(v=t;par[v]!=nullptr;){
            auto& e=*par[v];
            push(e,f);
            int u=par[v]->from;
            if(e.residual_cap()<=0)par[v]=nullptr;
            v=u;
         }
         b[t]+=f; b[v]-=f;
      }
   }
   template<typename T>pair<bool,T> solve(const Flow& sf){
      Flow max_flow=1;
      for(auto& t:b)chmax(max_flow,abs(t));
      for(auto& es:g)for(auto& e:es)chmax(max_flow,abs(e.residual_cap()));
      Flow delta=1;
      while(delta<max_flow)delta*=sf;
      for(;delta;delta/=sf){
         for(auto& es:g)for(auto& e:es){
            Flow rcap=e.residual_cap();
            rcap-=rcap%delta;
            Cost rcost=residual_cost(e.from,e.to,e);
            if(rcost<0 or rcap<0){
               push(e,rcap);
               b[e.from]-=rcap; b[e.to]+=rcap;
            }
         }
         rep(v,n)if(b[v]!=0){
            (b[v]>0?exc:def).push_back(v);
         }
         while(dual(delta))primal(delta);
      }
      T res=0;
      for(auto& es:g)for(auto& e:es)res+=T(e.flow)*T(e.weight);
      res/=2;
      if(exc.empty() and def.empty())return {1,res*type};
      else return {0,res*type};
   }
};
///////////////////////////////////////////////////////////////////////



struct UnionFind {
  vector<int> d;
  int m; // number of connected components
  UnionFind(int n = 0) : d(n, -1), m(n) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    --m;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -d[find(x)]; }
};


template<typename T>
struct RMQ {
  vector<T> v;
  VVi st;
  int op(const int a, const int b) {
    return (v[a] == v[b]) ? min(a, b) : ((v[a] < v[b]) ? a : b);
  } 
  void init(const vector<T> &_v) {
    v = _v;
    int n = v.size();
    st = {Vi(n)}; iota(all(st[0]), 0);
    for (int j = 0; n>>(j+1); ++j) {
      int m = n+1-(1<<(j+1));
      st.push_back(Vi(m));
      rep(i, m) st[j+1][i] = op(st[j][i], st[j][i+(1<<j)]);
    }
  }
  int index(const int l, const int r) { int d = fLog2(r-l); return op(st[d][l], st[d][r-(1<<d)]); }
  T query(const int l, const int r) { return v[index(l, r)]; }
};


struct LCA {
  struct edge {
    int v, id;
    edge(int v = 0, int i = 0) : v(v), id(i) {}
  };
  vector<vector<edge>> G;
  Vi tl, tour, dep;
  RMQ<int> R;
  int r;

  vector<edge> Gpar;

  LCA(int n) : G(n), tl(n), tour(2*n), dep(2*n), Gpar(n, {-1, -1}) {}
  void add_edge(int u, int v, int i) {
    G[u].emplace_back(v, i);
    G[v].emplace_back(u, i);
  }
  void dfs(int &t, int u, int p=-1, int d=0) {
    tour[t] = u; dep[t] = d;
    tl[u] = t++;
    for (auto &[v, i] : G[u]) {
      if (v == p) Gpar[u] = {v, i};
      else dfs(t, v, u, d+1);
    }
    tour[t] = p; dep[t] = d-1;
    ++t;
  }

  void init(int _r=0) { r = _r; int t = 0; dfs(t, r); R.init(dep); }
  vector<int> exchangable_edges(int u, int v) {
    int w = tour[R.index(min(tl[u], tl[v]), max(tl[u], tl[v]))];
    vector<int> res;
    rep(i, 2) {
      while (u != w) {
        auto [x, i] = Gpar[u];
        res.push_back(i);
        u = x;
      }
      swap(u, v);
    }
    return res;
  }
};


int n, m, D;
vector<array<int, 4>> E;


// 「G の最小全域木として vl が採用されうる」という条件の下で x を動かしたときの最大値を求める．
ll subsolve(const Vi &vl, const Vi &vr) {
  ll res = 0;
  for (auto i : vl) res += E[i][2];
  res *= D;

  LCA G(n);
  for (auto i : vl) G.add_edge(E[i][0], E[i][1], i);
  G.init();

  MinCostFlow<ll,ll> mcf(m+2);
  int s = m, t = m+1;
  const ll BIG = 1e10;

  for (auto j : vr) {
    // vl に含まれない辺 j を追加したとき，代わりに取り除ける辺 i を列挙
    int u = E[j][0], v = E[j][1];  
    for (auto i : G.exchangable_edges(u, v)) mcf.add_edge(i, j, 0, BIG, E[j][2] - E[i][2]);
  }
  for (auto i : vl) mcf.add_edge(s, i, max(D - E[i][3], 0), BIG, 0);
  for (auto j : vr) mcf.add_edge(j, t, 0, E[j][3], 0);
  mcf.add_edge(t, s, 0, BIG, 0);
  
  auto [status, f] = mcf.solve<ll>(2);
  if (!status) return INFll;
  res += f;
  return res;
}


int main() {
  chrono::system_clock::time_point start, now;
  start = chrono::system_clock::now();


  cin >> n >> m >> D;
  E.assign(m, array<int, 4>());
  for (auto &[a, b, c, d] : E) {
    cin >> a >> b >> c >> d;
    --a, --b;
  }

  Vi v(m);
  rep(i, n-1) v[m-1-i] = 1;

  ll ans = 0;

  do {
    UnionFind uf(n);
    rep(i, m) if (v[i]) uf.unite(E[i][0], E[i][1]);
    if (uf.m != 1) continue;

    // vl: 全域木をなす辺添字集合
    // vr: それ以外の辺添字集合
    Vi vl, vr;
    rep(i, m) {
      if (v[i]) vl.push_back(i);
      else vr.push_back(i);
    }
    chmax(ans, subsolve(vl, vr));

    now = chrono::system_clock::now();
    auto dur = std::chrono::duration_cast<std::chrono::milliseconds>(now - start).count();
    if (dur > 1900) break;    
  } while (next_permutation(all(v)));

  if (ans == INFll) ans = -1;
  cout << ans << '\n';
}

yukicoder

結果

テストケース

ソースコード