#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 200+1, mxM=1e4+2, oo = 1e9;
typedef complex<int> pt;
#define X real()
#define Y imag()
auto cross(pt u, pt v) {return (ll)u.X*v.Y-(ll)u.Y*v.X;}
auto sgn(ll a) {return a==0?0:(a>0?1:-1);}
auto ccw(pt p1, pt p2, pt p3) {auto u = p2-p1, v = p3-p2;return cross(u,v);}
auto in(pt p1, pt p2) {return (ll)p1.X*p2.X+(ll)p1.Y*p2.Y;}
auto norm(pt p) {return (ll)p.X*p.X+(ll)p.Y*p.Y;}
void read(pt& p) {
int a,b; cin >> a >> b;
p = {a,b};
}
struct DSU{
vector<int> sz,parent;
int components;
DSU(int n) {
sz.assign(n,1);
components = n;
parent.resize(n);
for(int i=0;i<n;++i) parent[i]=i;
}
void link(int a, int b) {
components--;
if(sz[a]<sz[b]) {
swap(a,b);
}
sz[a] = max(sz[a],sz[b]+1);
parent[b] = a;
}
bool unite(int a, int b) {
int pa = find(a),pb = find(b);
if(pa!=pb) link(pa,pb);
return pa!=pb;
}
int find(int a) {
if(a==parent[a]) return a;
return parent[a] = find(parent[a]);
}
};
ll ft,fc;
struct edge{
int a,b,t,c;
bool operator<(const edge& o) const {
return ft*t+fc*c < ft*o.t+fc*o.c;
}
};
int n,m;
edge edges[mxM];
pt kruskal(bool print=false) {
DSU dsu(n);
sort(edges,edges+m);
pt ans = 0;
for(int j=0;j<m;++j) {
auto& e = edges[j];
if(dsu.unite(e.a,e.b)) {
ans+=pt{e.t,e.c};
if(print) cout << e.a << ' ' << e.b << '\n';
}
if(dsu.components==1) break;
}
auto score = (ll)ans.X*ans.Y;
if(score<best) {
bestp = ans;
best = score;
bestft = ft;
bestfc = fc;
}
return ans;
}
int bestfc=0, bestft=1;
ll best=1e18;
complex<int> bestp=0;
void solve(pt ul, pt rd) {
ft = ul.Y-rd.Y;
fc = rd.X-ul.X;
if(ft==fc and ft==0) ft = 1;
auto nw = kruskal();
if(ccw(ul,nw,rd)==0) return;
solve(ul,nw), solve(nw,rd);
}
int main() {
cin >> n>>m;
for(int i=0;i<m;++i) {
int a,b,t,c; cin >> a >> b >> t >> c;
edges[i] = {a,b,t,c};
}
ft = 1, fc = 0;
auto p1 = kruskal();
ft = 0, fc = 1;
auto p2 = kruskal();
solve(p1,p2);
cout << bestp.X << ' ' << bestp.Y << '\n';
ft = bestft;
fc = bestfc;
kruskal(true);
}
Compilation message
timeismoney.cpp: In function 'pt kruskal(bool)':
timeismoney.cpp:73:14: error: 'best' was not declared in this scope
73 | if(score<best) {
| ^~~~
timeismoney.cpp:74:9: error: 'bestp' was not declared in this scope
74 | bestp = ans;
| ^~~~~
timeismoney.cpp:76:9: error: 'bestft' was not declared in this scope
76 | bestft = ft;
| ^~~~~~
timeismoney.cpp:77:9: error: 'bestfc' was not declared in this scope
77 | bestfc = fc;
| ^~~~~~
