Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ∧_∧
- ( ・ω・。)つ━☆・*。
- ⊂ ノ ・゜
- しーJ Accepted
- */
- // #pragma GCC optimize("O3")
- // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define ll long long
- #define all(x) begin(x), end(x)
- #define x first
- #define y second
- #define int long long
- using namespace std;
- using namespace __gnu_pbds;
- typedef long double ld;
- template<typename T>
- using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- const ld PI = atan2(0, -1);
- void seriy() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout << fixed << setprecision(14);
- #ifdef _offline
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- }
- const int MAXN = 1e6 + 10;
- const int MAXM = 600;
- const int INF = 1e18 + 7;
- const int BASE = 47;
- const int MOD = 1e9 + 7;
- const int MAXLOG = 51;
- const ld EPS = 1e-6;
- struct edge {
- int u, v, val;
- };
- vector<int> used, p, sz;
- bool f = 0;
- void dfs(vector<vector<int>> &g, int u, int p) {
- used[u] = 1;
- for(auto v : g[u]) {
- if(!used[v]) {
- dfs(g, v, u);
- }
- else if(v != p) {
- f = 1;
- }
- }
- }
- int get(int a) {
- if(p[a] == a) return a;
- return p[a] = p[p[a]];
- }
- void unite(int a, int b) {
- a = get(a);
- b = get(b);
- if(a != b) {
- if(sz[b] > sz[a]) {
- swap(a, b);
- }
- p[b] = a;
- sz[a] += sz[b];
- }
- }
- signed main() {
- seriy();
- int n, m;
- cin >> n >> m;
- used.resize(n);
- vector<pair<int, int>> a(m), b(m);
- vector<int> w(m);
- for(int i = 0; i < m; i++) {
- cin >> a[i].x >> a[i].y >> b[i].x >> b[i].y >> w[i];
- a[i].x--;
- a[i].y--;
- b[i].x--;
- b[i].y--;
- }
- if(m == n - 1) {
- vector<edge> es(m);
- for(int i = 0; i < m; i++) {
- es[i] = {b[i].x, b[i].y, w[i]};
- }
- sort(all(es), [&](edge a, edge b) {
- return a.val > b.val;
- });
- p.resize(n);
- sz.resize(n, 1);
- for(int i = 0; i < n; i++) {
- p[i] = i;
- }
- int cnt = 0, ans = 0;
- for(auto e : es) {
- if(get(e.u) != get(e.v)) {
- unite(e.u, e.v);
- ans += e.val;
- cout << ans << '\n';
- cnt++;
- }
- }
- while(cnt < m) {
- cout << "Impossible\n";
- cnt++;
- }
- return 0;
- }
- for(int i = 1; i <= m; i++) {
- int ans = -INF;
- for(int j = 0; j < (1 << m); j++) {
- if(__builtin_popcount(j) != i) continue;
- vector<vector<int>> g(n), r(n);
- int sum = 0;
- for(int k = 0; k < m; k++) {
- if((j >> k) & 1) {
- g[a[k].x].push_back(a[k].y);
- g[a[k].y].push_back(a[k].x);
- r[b[k].x].push_back(b[k].y);
- r[b[k].y].push_back(b[k].x);
- sum += w[k];
- }
- }
- f = 0;
- fill(all(used), 0);
- for(int k = 0; k < n; k++) {
- if(!used[k]) {
- dfs(g, k, -1);
- }
- }
- if(f) {
- continue;
- }
- f = 0;
- fill(all(used), 0);
- for(int k = 0; k < n; k++) {
- if(!used[k]) {
- dfs(r, k, -1);
- }
- }
- if(f) {
- continue;
- }
- // if(i == 3) {
- // cerr << j << '\n';
- // }
- ans = max(ans, sum);
- }
- if(ans == -INF) {
- cout << "Impossible\n";
- }
- else {
- cout << ans << '\n';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement