問題
http://topcoder.bgcoder.com/print.php?id=1666
有効グラフが存在する。
ある一つのノードについて、starpathがC個以下であればそのノードはstarとみなされる。
starpathは辺が５本のとき、5C3+5C4+5C5で表わされる。
このとき、starのうちstarpathが小さいものから大きいものへのパスの最長の長さを求める。
ただし、無限ループが存在する場合はー１を返す。
解き方
問題文を読み解くのに一苦労。
はじめにC個以下を満たす最大の辺の数を求め、３以上かつもとめた最大の辺以下のノードを抽出する。
次に、今回はパスに閉路が存在しうるのでダイクストラ法ではなくベルマンフォード法を利用する。
閉路がないか判定しつつ、最長の経路を求める。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class StarsInGraphs {
public:
int C(int n,int k){
double ret=1;
FORE(i,0,k)ret*=(double)(n-i)/(i+1);
return (int)ret;
}
int calc(int x){
int ret=0;
FORE(i,3,x+1){
ret+=C(x,i);
}
return ret;
}
int starryPaths(vector<string> adjacencyMatrix, int C) {
int n=adjacencyMatrix.size();
int mindeg=3,maxdeg=3;
while(calc(maxdeg+1)<=C)maxdeg++;
int p[n];
memset(p,0,sizeof(p));
FORE(i,0,n)FORE(j,0,n)if(adjacencyMatrix[i][j]=='1')p[i]++;
int dp[n];
FORE(i,0,n){
if(mindeg<=p[i]&&p[i]<=maxdeg)dp[i]=1;
else dp[i]=-1e+9;
}
FORE(x,0,n+2)FORE(i,0,n)FORE(j,0,n){
if(p[i]<=p[j] && mindeg<=p[i] && p[j]<=maxdeg && adjacencyMatrix[i][j]=='1' && dp[j]<dp[i]+1){
dp[j]=dp[i]+1;
if(x==n+1)return -1;
}
}
int ret=0;
FORE(i,0,n)ret=max(ret,dp[i]);
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class StarsInGraphs {
public:
int C(int n,int k){
double ret=1;
FORE(i,0,k)ret*=(double)(n-i)/(i+1);
return (int)ret;
}
int calc(int x){
int ret=0;
FORE(i,3,x+1){
ret+=C(x,i);
}
return ret;
}
int starryPaths(vector<string> adjacencyMatrix, int C) {
int n=adjacencyMatrix.size();
int mindeg=3,maxdeg=3;
while(calc(maxdeg+1)<=C)maxdeg++;
int p[n];
memset(p,0,sizeof(p));
FORE(i,0,n)FORE(j,0,n)if(adjacencyMatrix[i][j]=='1')p[i]++;
int dp[n];
FORE(i,0,n){
if(mindeg<=p[i]&&p[i]<=maxdeg)dp[i]=1;
else dp[i]=-1e+9;
}
FORE(x,0,n+2)FORE(i,0,n)FORE(j,0,n){
if(p[i]<=p[j] && mindeg<=p[i] && p[j]<=maxdeg && adjacencyMatrix[i][j]=='1' && dp[j]<dp[i]+1){
dp[j]=dp[i]+1;
if(x==n+1)return -1;
}
}
int ret=0;
FORE(i,0,n)ret=max(ret,dp[i]);
return ret;
}
};