SRM648は不参加。
仮に出てたら、Easy早解きMedium時間切れでレート維持かな…。
http://community.topcoder.com/stat?c=problem_statement&pm=13648
問題
N頂点の有効グラフが与えられる。
articulation pairとは2つの異なる頂点の対で、その2点を除くとグラフの連結数が変化するものをいう。
articulation pairの数を求めよ。
解法
特にひっかけの無い実装問題。
2つの頂点対を総当たりし、Union-FindなりWarshall-Floyedで連結数を数えればよい。
総当たり+Warshall-FloyedでO(N^5)で間に合う。
int mat[21][21]; class Fragile2 { public: int N; int numcom(int x,int y) { int i,j,k; int vis[21]={}; int comp=0; FOR(i,N) FOR(j,N) FOR(k,N) mat[j][k] |= mat[j][i]&&mat[i][k]; FOR(i,N) if(vis[i]==0) { if(i==x) continue; if(i==y) continue; comp++; vis[i]=1; FOR(j,N) if(mat[i][j]) vis[j]=1; } return comp; } int countPairs(vector <string> graph) { int num,i,j,x,y,ret=0; N=graph.size(); FOR(i,N) FOR(j,N) mat[i][j]=graph[i][j]=='Y'; int b=numcom(-1,-1); FOR(y,N) FOR(x,y) { FOR(i,N) FOR(j,N) mat[i][j]=graph[i][j]=='Y'; FOR(i,N) mat[i][x]=mat[x][i]=mat[y][i]=mat[i][y]=0; if(numcom(x,y)>b) ret++; } return ret; } }
まとめ
Div2Mediumとしてはだいぶストレートな問題。