// TLE 解法 // 全域木を全部試す.全域木を固定すると,最小費用循環流に帰着される. #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 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 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 using V = vector; using ll = long long; using Vi = V; using VVi = V; 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; } 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 /////////////////////////////////////////////////////////////////////////// templatestruct 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}; } }; /////////////////////////////////////////////////////////////////////// struct UnionFind { vector 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 struct RMQ { vector 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 &_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<> G; Vi tl, tour, dep; RMQ R; int r; vector 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 exchangable_edges(int u, int v) { int w = tour[R.index(min(tl[u], tl[v]), max(tl[u], tl[v]))]; vector 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> 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 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(2); if (!status) return INFll; res += f; return res; } int main() { cin >> n >> m >> D; E.assign(m, array()); 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)); } while (next_permutation(all(v))); if (ans == INFll) ans = -1; cout << ans << '\n'; }