第2回swapコンの振り返り【ABC270】
みなさん、こんにちは。第2回swapコンの振り返りを投稿します。
swapコンの詳細はこちら: https://qiita.com/swapman/items/62e9fedc2a3e39b9d28c
結果としては、A-C, Eはノーペナで行けましたが、Dができませんでした。ゲームDPの復習がいるかなと感じました！
(A-Eの解説はこちら: https://qiita.com/swapman/items/2eb1a550febc9a5acea1)
この記事では、自分が解けなかったF問題の解説を覚書として残したいと思います。それではいきましょう！
ABC270のリンク: https://atcoder.jp/contests/abc270
【解説を見る前の僕の考察と反省】
嬉しいことに長頂点を作ると言う発想はできていました。しかし、港も空港も建設しなくていい場合をどう処理すればいいのかが理解できていませんでした。と言うより、港と空港の長頂点に辺を張ってMSTを求めると言うことは、空港および港を少なくとも一つは使う場合であることを理解できていませんでした。これを踏まえると次に説明する正しい解法に行き着くことができます。
【解説を拝見してAC】
上記の反省を踏まえると、クラスカル法を以下の4パターン全てにおいて行う必要があります。
①空港も港も使わない
②空港は少なくとも1つ使う
③港は少なくとも1つ使う
④空港も港も少なくとも1つは使う
ここで注意しなければならないのは①の場合はMSTを作れているかを確認する必要があります。これはACLのDSUを使えば解決できますね。
さて4回もクラスカル法をする必要があるわけですが、めんどくさいです。ライブラリ化しましょう。参考にしたというか、パクらせていただいたライブラリのリンクを張っておきます。
クラスカル法のライブラリ: https://algo-logic.info/kruskal-mst
これを踏まえるとコードは以下です。
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using mint = modint998244353;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const double EPS = 1e-10;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int dx[8] = {1,1,1,0,0,-1,-1,-1};
const int dy[8] = {1,0,-1,1,-1,1,0,-1};
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define yes {puts("Yes"); return;}
# define no {puts("No"); return;}
# define dame {puts("-1"); return;}
# define yn {puts('Yes');} else{puts('No');}
# define ret(x) {cout << (x) << endl; return 0;}
# define ll long long
# define fi first
# define se second
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define vvi vector<vector<int>>
# define vvl vector<vector<long long>>
# define vvb vector<vector<bool>>
# define vpi vector<pair<int, int>>
# define vpl vector<pair<ll, ll>>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define rep(i,n) for(int i = 0; i < n; i++)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define all(obj) (obj).begin(), (obj).end()
# define rall(obj) (obj).rbegin(), (obj).rend()
# define _GLIBCXX_DEBUG
# define Pll pair<ll, ll>
# define P pair<int,int>
# define bit(x,i) (((x) >> (i)) & 1)
# define equals(a, b) (fabs((a) - (b)) < EPS) // 誤差を考慮した同値判定
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(vector<T>&v){stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v){if(v.size())o<<join(v);return o;}
template<typename T>ostream& operator<<(ostream&o,vector<vector<T>>&vv){if(vv.size())o<<join(vv);return o;}
/* UnionFind：素集合系管理の構造体(union by rank)
isSame(x, y): x と y が同じ集合にいるか。 計算量はならし O(α(n))
unite(x, y): x と y を同じ集合にする。計算量はならし O(α(n))
*/
struct UnionFind { // The range of node number is u 0 v n-1
vector<int> rank, parents;
UnionFind() {}
UnionFind(int n) { // make n trees.
rank.resize(n, 0);
parents.resize(n, 0);
for (int i = 0; i < n; i++) {
makeTree(i);
}
}
void makeTree(int x) {
parents[x] = x; // the parent of x is x
rank[x] = 0;
}
bool isSame(int x, int y) { return findRoot(x) == findRoot(y); }
void unite(int x, int y) {
x = findRoot(x);
y = findRoot(y);
if (rank[x] > rank[y]) {
parents[y] = x;
} else {
parents[x] = y;
if (rank[x] == rank[y]) {
rank[y]++;
}
}
}
int findRoot(int x) {
if (x != parents[x]) parents[x] = findRoot(parents[x]);
return parents[x];
}
};
// 辺の定義
struct Edge {
long long u;
long long v;
long long cost;
};
bool comp_e(const Edge &e1, const Edge &e2) { return e1.cost < e2.cost; } // 辺を直接比較するための関数
/* Kruskal :クラスカル法で minimum spanning tree を求める構造体
入力: 辺のvector, 頂点数V
最小全域木の重みの総和: sum
計算量: O(|E|log|V|)
*/
struct Kruskal {
UnionFind uft;
long long sum; // 最小全域木の重みの総和
vector<Edge> edges;
int V;
Kruskal(const vector<Edge> &edges_, int V_) : edges(edges_), V(V_) { init(); }
void init() {
sort(edges.begin(), edges.end(), comp_e); // 辺の重みでソート
uft = UnionFind(V);
sum = 0;
for (auto e : edges) {
if (!uft.isSame(e.u, e.v)) { // 閉路にならなければ加える
uft.unite(e.u, e.v);
sum += e.cost;
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin >> n >> m;
vector<int> x(n), y(n), a(m), b(m), z(m);
rep(i,n) cin >> x[i];
rep(i,n) cin >> y[i];
rep(i,m) {
cin >> a[i] >> b[i] >> z[i];
--a[i]; --b[i];
}
dsu uf(n);
rep(i,m) uf.merge(a[i], b[i]);
//空港も港もなしで、すでにMSTが構築できる場合
ll ans = LINF;
vector<Edge> edges;
if(uf.size(0) == n) {
rep(i,m) edges.push_back({a[i], b[i], z[i]});
Kruskal krs0(edges, n);
chmin(ans, krs0.sum);
}
//空港だけ建設する
edges.clear();
rep(i,m) edges.push_back({a[i], b[i], z[i]});
rep(i,n) edges.push_back({i,n,x[i]});
Kruskal krs1(edges,n+1);
chmin(ans,krs1.sum);
//港だけ建設する
edges.clear();
rep(i,m) edges.push_back({a[i], b[i], z[i]});
rep(i,n) edges.push_back({i,n,y[i]});
Kruskal krs2(edges,n+1);
chmin(ans,krs2.sum);
//両方建設する
edges.clear();
rep(i,m) edges.push_back({a[i],b[i],z[i]});
rep(i,n) edges.push_back({i,n,x[i]});
rep(i,n) edges.push_back({i,n+1,y[i]});
Kruskal krs3(edges,n+2);
chmin(ans,krs3.sum);
cout << ans << endl;
}
【終わりに】
長頂点を作成するアイデアはありましたが、すぐにそれに飛びつくようでは、まだまだですね。いい経験になりました。まぁこの問題が長頂点を作成するアイデアを使う初めての問題だったので、それにしてはよくできたと思いたいですね。
ここまで読んでいただきありがとうございました！swapコンへの参加もよろしくお願いいたします！それでは！