AOJ 2647: The Capital

ちょっとライブラリ風になった。
過去問からコードひっぱってくるときは、210みたいな数をちゃんと見てバグらないようにコピペすることが大事。
というか最小有向全域木は結構厄介なのでライブラリ化しましょう。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
using namespace std;
int t[150][150];
int T[150][150];
int in[11000];
int sp[60];
int ijk[11000];
int v[11000];
vector<int>g[11000];
vector<int>rev[11000];
int ans[60];
int n;
int Rev[210];
int u[210];
int w[210];
int solve(int a){
	int ret=0;
    int sz=n;
    int rt=a;
	for(int i=0;i<150;i++)for(int j=0;j<150;j++)t[i][j]=9999999;
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)t[i][j]=T[i][j];
	
	for(int i=0;i<150;i++)Rev[i]=v[i]=u[i]=w[i]=0;
    while(1){
        for(int i=0;i<sz;i++){
            if(v[i])continue;
            if(rt==i)continue;
            Rev[i]=-1;
            for(int j=0;j<sz;j++){
                if(v[j])continue;
                if(i==j)continue;
                if(!~Rev[i]||t[Rev[i]][i]>t[j][i])Rev[i]=j;
            }
 
            if(!u[i])ret+=t[Rev[i]][i];
            u[i]=1;
        }
        for(int i=0;i<210;i++)w[i]=0;
        int cnt=0;
        int SZ=sz;
        for(int i=0;i<SZ;i++){
            if(v[i])continue;
            if(w[i])continue;
            if(i==rt)continue;
            int at=i;
            while(1){
                if(w[at]==2){
                    cnt++;
                    vector<int>vs;
                    int a2=at;
                    if(w[rt]==2)rt=sz;
                    while(1){
                        if(w[a2]==1)break;
                        vs.push_back(a2);
                        w[a2]=1;v[a2]=1;
                        a2=Rev[a2];
                    }
                    for(int j=0;j<vs.size();j++){
                        for(int k=0;k<sz;k++){
                            if(t[vs[j]][k]<999999)t[sz][k]=min(t[sz][k],t[vs[j]][k]);
                            if(t[k][vs[j]]<999999)t[k][sz]=min(t[k][sz],t[k][vs[j]]-t[Rev[vs[j]]][vs[j]]);
                        }
                    }
                    sz++;
                    break;
                }
                if(w[at]==1)break;
                if(at==rt)break;
                w[at]=2;
                at=Rev[at];
            }
            at=i;//printf("%d %d\n",a,sz);
            while(1){
                if(w[at]==1)break;
                if(at==rt)break;
                w[at]=1;
                at=Rev[at];
            }
        }
        if(!cnt)break;
    }
	return ret;
}
int main(){
	int a,b;
 
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);
		in[q]++;
		g[p].push_back(q);
		rev[q].push_back(p);
	}
	int sz=0;
	for(int i=0;i<a;i++)if(!in[i])sp[sz++]=i;
	for(int i=0;i<sz;i++){
		for(int j=0;j<a;j++)ijk[j]=999999999;
		for(int j=0;j<a;j++)v[j]=0;
		deque<int> Q;
		Q.push_back(sp[i]);
		ijk[sp[i]]=0;
		while(Q.size()){
			int at=Q.front();
			int cost=ijk[at];
			Q.pop_front();
			if(v[at])continue;
			v[at]=1;
			for(int k=0;k<g[at].size();k++){
				if(!v[g[at][k]]&&ijk[g[at][k]]>cost){
					ijk[g[at][k]]=cost;
					Q.push_front(g[at][k]);
				}
			}
			for(int k=0;k<rev[at].size();k++){
				if(!v[rev[at][k]]&&ijk[rev[at][k]]>cost+1){
					ijk[rev[at][k]]=cost+1;
					Q.push_back(rev[at][k]);
				}
			}
		}
		for(int j=0;j<sz;j++)T[i][j]=ijk[sp[j]];
	}
	int ret=999999999;
	int now=0;
	n=sz;
 
	for(int i=0;i<sz;i++){
		int val=solve(i);
		if(ret==val)now++;
		else if(ret>val){
			ret=val;now=1;
		}
		ans[i]=val;
	}
	printf("%d %d\n",now,ret);
	int fi=0;
	for(int i=0;i<sz;i++){
		if(ans[i]==ret){
			if(fi)printf(" ");
			fi=1;
			printf("%d",sp[i]);
		}
	}
	printf("\n");
}