ちょっとライブラリ風になった。
過去問からコードひっぱってくるときは、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"); }