Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
The Capital ( AOJ 2647 )
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment