This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3208 // verification-helper: ERROR 1e-10 #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../io/precision.cpp" #include "../../tools/chminmax.cpp" #include "../../graph/topologicalsort.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,m; while(cin>>n>>m,n){ TopologicalSort G(n); for(int i=0;i<m;i++){ int a,b; cin>>a>>b; a--;b--; G.add_edge(a,b); } auto ps=G.build(); if(ps.empty()){ cout<<0<<endl; continue; } vector<int> dp(n,0); for(int i=n-1;i>=0;i--){ int v=ps[i]; for(int u:G.G[v]) chmax(dp[v],dp[u]+1); } cout<<-1.0/accumulate(dp.begin(),dp.end(),0.0)<<endl; } return 0; }
#line 1 "test/aoj/3208.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3208 // verification-helper: ERROR 1e-10 #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "io/precision.cpp" #line 3 "io/precision.cpp" using namespace std; #endif //BEGIN CUT HERE struct Precision{ Precision(){ cout<<fixed<<setprecision(12); } }precision_beet; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 1 "tools/chminmax.cpp" #line 3 "tools/chminmax.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 1 "graph/topologicalsort.cpp" #line 3 "graph/topologicalsort.cpp" using namespace std; #endif //BEGIN CUT HERE struct TopologicalSort{ vector<vector<int>> G; vector<int> indeg; TopologicalSort(int n):G(n),indeg(n,0){} void add_edge(int s,int t){ G[s].emplace_back(t); indeg[t]++; } vector<int> build(){ int n=G.size(); queue<int> que; vector<int> used(n,0); auto push=[&](int v){ if(used[v]) return; que.emplace(v); used[v]=1; }; for(int i=0;i<n;i++) if(indeg[i]==0) push(i); vector<int> ps; while(!que.empty()){ int v=que.front();que.pop(); ps.emplace_back(v); for(int u:G[v]){ indeg[u]--; if(indeg[u]==0) push(u); } } if(n!=(int)ps.size()) return {}; return ps; } }; //END CUT HERE #ifndef call_from_test #endif #line 11 "test/aoj/3208.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,m; while(cin>>n>>m,n){ TopologicalSort G(n); for(int i=0;i<m;i++){ int a,b; cin>>a>>b; a--;b--; G.add_edge(a,b); } auto ps=G.build(); if(ps.empty()){ cout<<0<<endl; continue; } vector<int> dp(n,0); for(int i=n-1;i>=0;i--){ int v=ps[i]; for(int u:G.G[v]) chmax(dp[v],dp[u]+1); } cout<<-1.0/accumulate(dp.begin(),dp.end(),0.0)<<endl; } return 0; }