Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
yukicoder No.19
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define var auto
#define mod 1000000007
#define inf 2147483647
#define nil -1
typedef long long ll;
using namespace std;
inline int input(){
int a;
cin >> a;
return a;
}
template <typename T>
inline void output(T a, int p) {
if(p){
cout << fixed << setprecision(p) << a << "\n";
}
else{
cout << a << "\n";
}
}
// end of template
int main() {
cin.tie(0);
// source code
int N = input();
vector<int> L(N), S(N);
vector<vector<int>> E(N, vector<int> (N)); // 有向辺E[to][from]
int ret = 0;
rep(to, N){
L[to] = input();
S[to] = input() - 1;
E[S[to]][to] = 1;
E[to][to] = 1;
ret += L[to];
}
// ワーシャルフロイド
rep(k, N){
rep(i, N){
rep(j, N){
E[i][j] |= E[i][k] && E[k][j];
}
}
}
vector<int> vis(N, 0);
rep(i, N){ // 頂点0から順に辿っていく.もし頂点iを含む強連結成分に有向辺が伸びていないならば,その強連結成分について全て調べ,costがminなものを採用.
if (vis[i]) continue;
bool isRoot = true;
rep(j, N){
if (E[j][i] && !E[i][j]) {
isRoot = false;
}
}
if (!isRoot) continue;
int tmp = inf;
rep(j, N){
if (E[i][j] && E[j][i]) {
tmp = min(tmp, L[j]);
vis[j] = 1;
}
}
ret += tmp;
}
output((double)ret / 2.0, 1);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment