The Capital ( AOJ 2647 )

main.cpp

#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int yui = 0; yui < n; yui++ ){ cout << x[yui] << " "; } cout << endl

#define pb emplace_back
#define fi first
#define se second

using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ long long int x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head

// ただの union find です。あとで実装が多少楽になるのでマージテクは使わずにパス圧縮だけ使っています。
struct Unionfind{
  vi par;
  Unionfind(){}
  Unionfind( int n ) :  par(n){
    REP( i , n ) par[i] = i;
  }
  void init( int n ){
    par.resize( n );
    REP( i , n ) par[i] = i;
  }
  int find( int x ){
    if( par[x] == x ) return x;
    return par[x] = find( par[x] );
  }
  bool unite( int x , int y ){
    x = find(x);
    y = find(y);
    if( x == y ) return false;
    par[x] = y;
    return true;
  }
  bool same( int x , int y ){
    return find(x) == find(y);
  }
} uf;

// skew heap です。遅延伝播で全ての要素に定数を加算できるようになっています。あと対応する辺の番号 id も持っています。
struct Heap{
  Heap *l, *r;
  int add, v, id;
  Heap(){}
  Heap( int v , int id ) : l(NULL) , r(NULL) , add(0) , v(v) , id(id) {}
};
void lazy( Heap *a ){
  if( a->l ) a->l->add += a->add;
  if( a->r ) a->r->add += a->add;
  a->v += a->add;
  a->add = 0;
}
Heap* meld( Heap *a , Heap *b ){
  if( !a ) return b;
  if( !b ) return a;
  if( a->v + a->add > b->v + b->add ) swap( a , b );
  lazy( a );
  a->r = meld( a->r , b );
  swap( a->l , a->r );
  return a;
}
Heap* pop( Heap *a ){
  lazy( a );
  return meld( a->l , a->r );
}
Heap pool[10000010];
int it; // pool をどこまで使ったか

struct edge{
  int from, to, cost;
  edge( int from , int to , int cost ) : from(from) , to(to) , cost(cost) {}
};

int n, m;
bool kouho[10010];

vector<edge> edges;

Heap* come[10010]; // （圧縮されたグラフ上で）その点に入ってくる辺をコストの小さい順に管理するヒープです。
int used[10010]; // 0 : 未処理, 1 : 処理中, 2 : 完成
int from_cost[10010]; // 作っている木においてその点に入ってくる辺の（圧縮されたグラフ上の）コストです。
int from[10010]; // 作っている木においてその点に入ってくる辺の（圧縮されたグラフ上の） from です。

int MSA( int r ){ // r を根とする最小全域有向木のコストを計算します。
  // 初期化します。
  uf.init( n );
  it = 0;
  REP( i , n ){
    used[i] = 0;
    come[i] = NULL;
  }
  used[r] = 2; // 根だけは完成しています。

  // 最初に各点に入ってくる辺をヒープに追加します。
  REP( i , edges.size() ){
    edge &e = edges[i];
    pool[it] = Heap( e.cost , i );
    come[e.to] = meld( come[e.to] , &pool[it++] );
  }

  int res = 0;
  REP( start , n ){
    if( used[start] != 0 ) continue;
    int cur = start;
    vi processing(0);
    
    while( used[cur] != 2 ){ // パスを伸ばしていきます。ここが本質です。
      used[cur] = 1; // 現在の頂点を処理中にします。
      processing.pb( cur );
      
      if( !come[cur] ) return INF; // 入ってくる辺がなかったら全域有向木は存在しません。おしまい。
      
      from[cur] = uf.find( edges[ come[cur]->id ].from ); // 今の頂点に入って来る辺のうち、一番コストが小さい辺を使います。その辺の from です。 
      from_cost[cur] = come[cur]->v + come[cur]->add; // その辺のコストです。
      come[cur] = pop( come[cur] ); // もう用済みなのでヒープからその辺を取り除きます。
      if( from[cur] == cur ) continue; // 自己ループだったら使うのをやめてやり直しです（頂点を圧縮しているので最初に自己ループがなくても途中で生成されることがあります）
      
      res += from_cost[cur]; // この辺を使うことが確定したので、コストを計上しておきます。
      
      if( used[ from[cur] ] == 1 ){ // サイクルができた場合です。
	int p = cur;
      	do { // サイクルを回ります。現在の頂点は p です。
      	  if( come[p] ) come[p]->add -= from_cost[p]; // その頂点に入ってくる辺のコストを、サイクルの前の辺のコスト分だけ減らします。
      	  if( p != cur ){
      	    uf.unite( p , cur ); // サイクルの頂点を一つの頂点に圧縮していきます。
      	    come[cur] = meld( come[cur] , come[p] ); // ヒープもマージしていきます。
      	  }
      	  p = uf.find( from[p] ); // 一つ前の頂点です。パスを伸ばしていく途中で圧縮されているかもしれないので find する必要があります。
      	} while( p != cur );
      	// 次の頂点ですが、圧縮した頂点からはじめます。unionfind で cur に圧縮されているので cur を変更する必要はありません。（unionfind でマージテクを使った場合は cur を find して、マージしたヒープの場所を古い cur から 新しい cur に移してください。）
      } else { // サイクルができなかった場合です。
	cur = from[cur]; // そのまま次の頂点に移ります。
      }
    }
    // 伸びてきたパスが根につながりました。
    for( int v : processing ){
      used[v] = 2; // 使った頂点を完成させたことにします。
    }
  }
  return res;
}

int main(){

  n = in();
  m = in();
  REP( i , n ){
    kouho[i] = true;
  }
  REP( i , m ){
    int a = in();
    int b = in();
    kouho[b] = false;
    edges.pb( a , b , 0 );
    edges.pb( b , a , 1 );
  }
  
  vi ansv(0);
  int ansc = INF;
  REP( i , n ){
    if( kouho[i] ){
      int res = MSA( i );
      if( res < ansc ){
	      ansv = { (int)i };
	      ansc = res; 
      } else if( res == ansc ){
      	ansv.pb( i );
      }
    }
  }

  cout << ansv.size() << " " << ansc << endl;
  REP( i , ansv.size() ){
    if( i != 0 ){
      cout << " ";
    }
    cout << ansv[i];
  }
  cout << endl;
  
  return 0;
}