結果

問題 No.1316 Maximum Minimum Spanning Tree
コンテスト
ユーザー 👑 tatyam
提出日時 2020-12-12 02:45:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 8,777 bytes
コンパイル時間 3,608 ms
コンパイル使用メモリ 230,624 KB
最終ジャッジ日時 2025-01-16 22:40:26
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40 WA * 5 TLE * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://yukicoder.me/submissions/592136 改変
// 正当な解法？
// 全域木を時間いっぱいいろいろ試す．
// 初期解を x = 0 としたときの最小全域木とし，辺を +1-1 したところを山登りする．
// 全域木を固定すると，最小費用循環流に帰着される．

#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 all(x) begin(x), end(x)
using ll = long long;
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; }
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};
    }
};

///////////////////////////////////////////////////////////////////////

int n, m, k;
vector<array<int, 4>> E;
vector<int> depth, parent, edge;
void build(const vector<int>& v){
    depth.resize(n);
    parent.resize(n);
    edge.resize(n);
    depth[0] = 0;
    vector<vector<pair<int, int>>> g(n);
    for(int i : v){
        int a = E[i][0], b = E[i][1];
        g[a].emplace_back(b, i);
        g[b].emplace_back(a, i);
    }
    auto dfs = [&](int from, int at, auto dfs) -> void {
        const int d2 = depth[at] + 1;
        for(auto [to, id] : g[at]) if(to != from){
            depth[to] = d2;
            parent[to] = at;
            edge[to] = id;
            dfs(at, to, dfs);
        }
    };
    dfs(-1, 0, dfs);
}
vector<int> exchangable_edges(int e){
    vector<int> ans;
    int a = E[e][0], b = E[e][1];
    while(a != b){
        if(depth[a] < depth[b]) swap(a, b);
        ans.push_back(edge[a]);
        a = parent[a];
    }
    return ans;
}
// 「G の最小全域木として vl が採用されうる」という条件の下で x を動かしたときの最大値を求める．
ll subsolve(const vector<int>& vl, const vector<int>& vr){
    ll res = 0;
    for (auto i : vl) res += E[i][2];
    res *= k;
    
    build(vl);
    
    MinCostFlow<ll, ll> mcf(m+2);
    int s = m, t = m+1;
    const ll BIG = 1e10;
    
    for (auto j : vr) {
        // vl に含まれない辺 j を追加したとき，代わりに取り除ける辺 i を列挙
        for (auto i : exchangable_edges(j)) mcf.add_edge(i, j, 0, BIG, E[j][2] - E[i][2]);
    }
    for (auto i : vl) mcf.add_edge(s, i, max(k - 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;
}
struct UnionFind{
    vector<int> data;
    UnionFind(int n): data(n, -1){}
    bool unite(int a, int b){
        a = root(a); b = root(b);
        if(a == b) return 0;
        if(data[a] > data[b]) swap(a, b);
        data[a] += data[b];
        data[b] = a;
        return 1;
    }
    bool find(int a, int b){ return root(a) == root(b); }
    int root(int a){ return data[a] < 0 ? a : data[a] = root(data[a]); }
    int size(int a){ return -data[root(a)]; }
    int operator[](int a){ return root(a); }
};
struct Xorshift64{
    using result_type = uint32_t;
    static constexpr result_type min(){ return 0; }
    static constexpr result_type max(){ return -1; }
    uint64_t x = random_device{}();
    result_type operator()(){
        x ^= (x << 13);
        x ^= (x >> 7);
        x ^= (x << 17);
        return static_cast<uint32_t>(x);
    }
}rnd;
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    E.resize(m);
    for (auto& [a, b, c, d] : E){
        cin >> a >> b >> c >> d;
        a--; b--;
    }
    sort(all(E), [](const auto& a, const auto& b){ return a[2] < b[2]; });
    UnionFind uf(n);
    vector<int> vl, vr;
    rep(i, m){
        int a = E[i][0], b = E[i][1];
        if(uf.unite(a, b)) vl.push_back(i);
        else vr.push_back(i);
    }
    
    ll ans = subsolve(vl, vr);
    if(vr.size()){
        
        auto start = chrono::system_clock::now();
        while (chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() < 1990) {
            auto p = vr.begin() + rnd() % vr.size();
            auto v = exchangable_edges(*p);
            auto q = find(vl.begin(), vl.end(), v[rnd() % v.size()]);
            iter_swap(p, q);
            vector<int> depth_, parent_, edge_;
            swap(depth, depth_);
            swap(parent, parent_);
            swap(edge, edge_);
            const ll ans2 = subsolve(vl, vr);
            chmax(ans, ans2);
            if(ans != ans2){
                iter_swap(p, q);
                depth = move(depth_);
                parent = move(parent_);
                edge = move(edge_);
            }
        }
        
    }
    
    if (ans == INFll) ans = -1;
    cout << ans << '\n';
}
0