TopCoder SRM 350 Div1 Medium StarsInGraphs

TopCoder グラフ理論

問題

有向グラフが与えられる。
このグラフにおいてstarとは、
中心の1ノードおよび、そこから3本以上の辺が出ているような構造を言う。


あるノードに対して、star numberとは、
そのノードを中心としたstarの個数の数を言う。
例えば5本の辺が出ている頂点は、3本の辺が出ているstarが10通り、4本の辺が出ているstarが5通り、5本の辺が出ているstarが1通りなので10+5+1=16である。


このグラフの中のパスV1,V2,...,Vn（同じ頂点が複数あってもよい）で、

  • star numberがC以下であるようなstarの中心を結んでいる
  • Vi,Vi+1において、Viのstar number≦Vi+1のstar number

であるようなもののうち、長さ最大のものの長さを求めよ。


ただし、無限に長いパスが取れる場合-1を返せ。

制約条件

グラフの頂点数≦50
C≦10^9

方針

出次数がm本である頂点のstar numberは、
2^m - m(m*2)/2 - 1と表せる。
したがって、Cから出次数の最大値があらかじめ計算できる。


すると、あとはグラフから出次数が増加しているようなパスを見つけるだけの問題になるので、適当にメモ化再帰をして数えればよい。
ループを見つけられた場合は、-1を返す。

ソースコード

int ub,n,e[50][50],deg[50],dp[50];
int rec(int c){
	if(dp[c]>=0)return dp[c];
	if(!(3<=deg[c]&&deg[c]<=ub))return dp[c]=0;
	
	dp[c]=inf;
	int res=0;
	rep(i,n)if(e[c][i]&&deg[c]<=deg[i]&&deg[i]<=ub){
		res=max(res,rec(i));
	}
	return dp[c]=res+1;
}
class StarsInGraphs {
	public:
	int starryPaths(vector <string> adjacencyMatrix, int C) 
	{
		ub=2;
		for(;;ub++){
			#define calc(x) ((1ll<<(x))-(x)*(x+1)/2-1)
			if(calc(ub+1)>C)break;
		}
		if(ub<3)return 0;
		
		memset(deg,0,sizeof(deg));
		memset(dp,-1,sizeof(dp));
		
		n=adjacencyMatrix.size();
		rep(i,n)rep(j,n)e[i][j]=adjacencyMatrix[i][j]=='1';
		rep(i,n)rep(j,n)deg[i]+=e[i][j];
		
		int ans=-1;
		rep(i,n)ans=max(ans,rec(i));
		
		return ans>=inf?-1:ans;
	}
};