概要 最小全域木を求める． typedef int Weight; struct Edge{ int from, to; Weight weight; Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { } }; typedef vector<Edge> Edges; typedef vector<Edges> Graph; bool operator< (const Edge &a, const Edge &</edges></edge>…

概要 有向グラフと目標頂点が与えられる． 目標頂点への往復経路が最も大きい頂点を探す． 解法 Dijkstraやるだけ． 復路の計算は与えられたグラフに対してDijkstra法を使えば簡単に求まる． 往路の計算は与えられたグラフの辺を逆向きにしたグラフにDijkstr…

蟻本の問題番号と，問題名の対応が間違ってた． 概要 負閉路検知やるだけ． const int INF = 100000000; typedef int Weight; struct Edge{ int from, to; Weight weight; Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { } }; typedef vector<Edge> </edge>…

概要 無向グラフが与えられるので，他のすべての頂点への距離の平均が最も小さい頂点を探す． 解法 Warshall-Floydやるだけ． const int INF = 100000000; int N, M; int d[310][310]; int c[310]; int main(){ scanf("%d%d", &N, &M); for(int i = 0; i <= …

概要 2種類の集合があって，2つの要素が異なる集合に属しているという情報と，2つの要素が同じ集合に属すかどうか問うクエリが来る． 解法 蟻本の練習問題と同様の考え方を用いる．要素vについて，集合Aに属している事象Avと，集合Bに属している事象Bvを用意…