test/aoj/3208.test.cpp

• View this file on GitHub
• Last update: 2020-10-30 12:18:04+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3208

Depends on

• graph/topologicalsort.cpp
• io/precision.cpp
• tools/chminmax.cpp

Code

// 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;
}

Back to top page