Instantly share code, notes, and snippets.

# ctylim/yukicoder19.cpp Created Nov 28, 2015

What would you like to do?
yukicoder No.19
 #include #include #include #include #include #include #include #include #include #include #include #include #include #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 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 L(N), S(N); vector> E(N, vector (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 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; }