Guest User

Untitled

a guest
Nov 18th, 2018
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.10 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #ifdef LOCAL
  4. #define see(x) cout <<"<DBG> " << #x << ": " << (x) << endl
  5. #endif
  6. #ifndef LOCAL
  7. #define see(x)
  8. #endif
  9. template<typename T> void dprintln(const T &t) { cout << t << endl; } // for debug use
  10. template<typename T, typename ...Args> void dprintln(const T &t, const Args &...rest) { cout << t << ' '; dprintln(rest...); }
  11. template<typename T> void println(const T &t) { cout << t << '\n'; }
  12. template<typename T, typename ...Args> void println(const T &t, const Args &...rest) { cout << t << ' '; println(rest...); }
  13.  
  14. template<typename T> void print(const T &t) { cout << t << ' '; }
  15.  
  16. template<typename T, typename ...Args> void print(const T &t, const Args &...rest) { cout << t; print(rest...); }
  17.  
  18. // this overload is chosen when there's only one argument
  19. template<class T> void scan(T &t) { cin >> t; }
  20. template<class T, class ...Args> void scan(T &a, Args &...rest) { cin >> a; scan(rest...); }
  21. using ll = long long;
  22. using vl = vector<ll>;
  23. using vi = vector<int>;
  24. using pii = pair<int,int>;
  25. using vb = vector<bool>;
  26. using vpii = vector<pii>;
  27.  
  28. #define rng(i, a, b) for(int i = (a); i < (b); ++i)
  29. #define dwn(i, b, a) for (int i = (b); i >= (a); i--)
  30. #define rep(n) for(int _ = 0, __ = (int)n; _ < __; _++)
  31. #define stp(i, a, b, c) for (int i = (a); i < (b); i += (c))
  32. #define FOR(x, cont) for (auto &x: cont)
  33. #define all(x) (x).begin(), (x).end()
  34. #define pb push_back
  35. #define mp make_pair
  36. #define eb emplace_back
  37. #define SZ(x) (int)(x).size()
  38. #define pq(T,COMP) priority_queue<T, vector<T>, COMP>
  39. #define popcnt(x) __builtin_popcount((x))
  40. #define SET(arr, v) memset(arr, (v), sizeof (arr))
  41. #define UNIQ(vec) (vec).erase(unique(all(vec)), (vec).end())
  42. auto bet = [](const ll x, const ll y, const ll i) {
  43. return x <= i && i <= y;
  44. };
  45. inline int h_bit(unsigned int x) {
  46. return 31 - __builtin_clz(x);
  47. }
  48. inline int h_bitll(unsigned long long x) {
  49. return 63 - __builtin_clzll(x);
  50. }
  51.  
  52. struct frac{
  53. using ll = long long;
  54. ll fz, fm;
  55. frac() = default;
  56.  
  57. frac(ll fz, ll fm) { // 构造函数变量名最好不要跟类成员名一样!
  58. assert(fm != 0);
  59. if (fm < 0) fm *= -1, fz *= -1;
  60. ll g = __gcd(abs(fz), fm);
  61. fz /= g, fm /= g;
  62. this->fz = fz, this->fm = fm;
  63. }
  64.  
  65. frac(ll x):fz(x),fm(1){} // implicit conversion
  66.  
  67. frac operator*(const frac &other)const{
  68. return {fz * other.fz, fm * other.fm};
  69. }
  70.  
  71. frac operator-()const{
  72. return {-fz, fm};
  73. }
  74. frac operator-(const frac &other)const{
  75. return *this + (-other);
  76. }
  77. frac operator+(const frac &other)const{
  78. ll _fz = fz * other.fm + fm * other.fz;
  79. ll _fm = fm * other.fm;
  80. return {_fz, _fm};
  81. }
  82. bool operator==(const frac &other)const{
  83. return other.fz == fz && other.fm == fm;
  84. }
  85. bool operator<(const frac &other)const{
  86. return fz * other.fm < other.fz * fm;
  87. }
  88. bool operator>(const frac &other)const{
  89. return fz * other.fm > other.fz * fm;
  90. }
  91. bool operator>=(const frac &other)const{
  92. return !(*this < other);
  93. }
  94. bool operator<=(const frac &other)const{
  95. return !(*this > other);
  96. }
  97. frac operator/(const int &x)const{
  98. return {fz, fm * x};
  99. }
  100. double to_double() const {
  101. return fz / (double)fm;
  102. }
  103.  
  104. };
  105.  
  106. template <typename T>
  107. struct bit {
  108. vector<T> a;
  109. explicit bit(int n, int v = 0) {
  110. a.resize(n + 1);
  111. if(v != 0) {
  112. for (int i = 1; i <= n; ++i) a[i] = v;
  113. }
  114. }
  115.  
  116. T sum(T x) {
  117. T res = 0;
  118. while (x) {
  119. res += a[x];
  120. x -= x & -x;
  121. }
  122. return res;
  123. }
  124.  
  125. T sum(int l, int r) {
  126. if (l > r) return 0;
  127. return sum(r) - sum(l - 1);
  128. }
  129.  
  130. void add(int x, T v) {
  131. while (x < a.size()) {
  132. a[x] += v;
  133. x += x & -x;
  134. }
  135. }
  136. void clear(){
  137. fill(a.begin(), a.end(), 0);
  138. }
  139. };
  140. vi get_prime(int n) {
  141. vi minp(n + 1), p;
  142. for (int i = 2; i <= n; i++) {
  143. if (!minp[i]) {
  144. minp[i] = i;
  145. p.pb(i);
  146. }
  147. FOR(x, p) {
  148. if (x <= minp[i] && x * i <= n)
  149. minp[x * i] = x;
  150. else break;
  151. }
  152. }
  153. return p;
  154. }
  155.  
  156. const int mod = 1000000009;
  157.  
  158. inline void add_mod(ll &x, const ll &y) {
  159. x += y;
  160. if (x >= mod) x -= mod;
  161. }
  162. void sub_mod(ll &x, const ll &y) {
  163. x -= y;
  164. if (x < 0) x += mod;
  165. }
  166. // alias templates
  167. template<typename T> using vv = vector<vector<T>>;
  168. template <typename T1, typename T2 = T1> using vp = vector<pair<T1,T2>>;
  169.  
  170.  
  171.  
  172. using vec = vector<ll>;
  173. using mat = vector<vec>;
  174. mat get_I(int n) {
  175. mat res(n, vec(n));
  176. for (int i = 0; i < n; i++)
  177. res[i][i] = 1;
  178. return res;
  179. }
  180.  
  181. mat operator*(const mat &a, const mat &b) {
  182. mat c(a.size(), vec(b[0].size()));
  183. for (size_t i = 0; i < a.size(); i++) {
  184. for (size_t j = 0; j < a[0].size(); j++) {
  185. if (a[i][j]) { // optimization for sparse matrix
  186. for (size_t k = 0; k < b[0].size(); k++) {
  187. add_mod(c[i][k], a[i][j] * b[j][k] % mod);
  188. }
  189. }
  190. }
  191. }
  192. return c;
  193. }
  194.  
  195. vec operator*(const mat &a, const vec &b) {
  196. vec c(a.size());
  197. for (size_t i = 0; i < a.size(); i++) {
  198. for (size_t j = 0; j < a[0].size(); j++) {
  199. add_mod(c[i], a[i][j] * b[j] % mod);
  200. }
  201. }
  202. return c;
  203. }
  204.  
  205. mat pow(mat a, ll n) {
  206. mat res(a.size(), vec(a[0].size()));
  207. for (size_t i = 0; i < a.size(); i++) {
  208. res[i][i] = 1;
  209. }
  210. while (n) {
  211. if (n & 1) {
  212. res = res * a;
  213. }
  214. a = a * a;
  215. n >>= 1;
  216. }
  217. return res;
  218. }
  219.  
  220.  
  221.  
  222. vi get_popcnt(int n) {
  223. vi res(n + 1);
  224. rng (i, 0, n) {
  225. if (i * 2 <= n) res[i * 2] = res[i];
  226. if ((i & 1) == 0) res[i + 1] = res[i] + 1;
  227. }
  228. return res;
  229. }
  230.  
  231. /**** SUPER MACROs ****/
  232. #define FAIL {println("NO"); return 0;}
  233. const int N = 100005;
  234. int fa[N];
  235. int find(int x){
  236. return fa[x]==x?x:fa[x]=find(fa[x]);
  237. }
  238.  
  239. //void unite(int x, int y) {
  240. //// x = find(x), y = find(y);
  241. //// fa[x] = y;
  242. ////}
  243. struct edge{
  244. int u, v, w;
  245. void read(){scan(u, v, w);}
  246. void read2(){scan(u, v);}
  247. };
  248.  
  249. vector<pii> g[N];
  250. int dis[N];
  251. int par[N][18];
  252. int max_w[N][18];
  253.  
  254. int dep[N];
  255.  
  256. bool vis[N];
  257. void dfs(int u) {
  258. vis[u] = true;
  259. FOR(e, g[u]) {
  260. int v = e.first, w= e.second;
  261. if (!vis[v]) {
  262. dep[v] = dep[u] + 1;
  263. max_w[v][0] = w;
  264. par[v][0] = u;
  265. rng (i, 1, 17) {
  266. int t = par[v][i-1];
  267. par[v][i] = par[t][i-1];
  268. max_w[v][i] = max(max_w[v][i-1], max_w[t][i-1]);
  269. }
  270. dfs(v);
  271. }
  272. }
  273. }
  274.  
  275. int LCA(int u, int v) {
  276. if (dep[u] < dep[v]) swap(u, v);
  277. int dif = dep[u] - dep[v];
  278. int mx = INT_MIN;
  279. rng (i, 0, 17) {
  280. if (dif & 1 << i) {
  281. mx = max(mx, max_w[u][i]);
  282. u = par[u][i];
  283. }
  284. }
  285. if (u != v) {
  286. dwn(i, 16, 0) {
  287. if (par[u][i] != par[v][i]) {
  288. mx = max(mx, max(max_w[u][i], max_w[v][i]));
  289. u = par[u][i];
  290. v = par[v][i];
  291. }
  292. }
  293. }
  294. return mx;
  295. }
  296.  
  297. // f[n][k] = f[n-1][k] + f[n][k-1]*n
  298. int main() {
  299. #ifdef LOCAL
  300. freopen("main.in", "r", stdin);
  301. // freopen("main.out", "w", stdout);
  302. #endif
  303. ios::sync_with_stdio(false);
  304. cin.tie(nullptr);
  305.  
  306. int n, m1, m2;
  307.  
  308. cin >> n >> m2 >> m1;
  309.  
  310. vector<edge> e1(m1), e2(m2);
  311. FOR(e, e2) {e.read2();}
  312. FOR(e, e1) e.read();
  313.  
  314. sort(all(e1), [](edge a, edge b){return a.w < b.w;});
  315.  
  316. rng (i, 1, n+1) fa[i]=i;
  317.  
  318. FOR(e, e1) {
  319. int ru = find(e.u);
  320. int rv = find(e.v);
  321. if (ru != rv) {
  322. g[e.v].eb(e.u, e.w);
  323. g[e.u].eb(e.v, e.w);
  324. fa[ru] = fa[rv];
  325. }
  326. }
  327.  
  328. rng (i, 1, n + 1) {
  329. if(!vis[i]) dfs(i);
  330. }
  331.  
  332. ll ans = 0;
  333. FOR(e, e2) {
  334. println(find(e.u), find(e.v));
  335. if (find(e.u) != find(e.v)) {
  336. println(-1);
  337. return 0;
  338. }
  339. ans += LCA(e.u, e.v);
  340. }
  341.  
  342. println(ans);
  343.  
  344.  
  345.  
  346. #ifdef LOCAL
  347. cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  348. #endif
  349. return 0;
  350. }
Add Comment
Please, Sign In to add comment