// https://yukicoder.me/submissions/592136 改変 // 正当な解法? // 全域木を時間いっぱいいろいろ試す. // 初期解を x = 0 としたときの最小全域木とし,辺を +1-1 したところを山登りする. // 全域木を固定すると,最小費用循環流に帰着される. #include 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 inline bool chmin(T &a, const T b) { if (a > b) { a = b; return true; } return false; } template 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 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> g; vector 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 dist; vector par; vector 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::max()); par.assign(n,nullptr); exc.erase(remove_if(all(exc),[&](int v){return b[v]-delta;}),def.end()); priority_queue,vector>,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]=(int)def.size())break; for(auto& e:g[u]){ if(e.residual_cap()=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; } } templatepair 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(delta0?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> E; vector depth, parent, edge; void build(const vector& v){ depth.resize(n); parent.resize(n); edge.resize(n); depth[0] = 0; vector>> 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 exchangable_edges(int e){ vector 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& vl, const vector& vr){ ll res = 0; for (auto i : vl) res += E[i][2]; res *= k; build(vl); MinCostFlow 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(2); if (!status) return INFll; res += f; return res; } struct UnionFind{ vector 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(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 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::system_clock::now() - start).count() < 1980) { 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 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'; }