SRM570 - div2 - hard - 1000
組み合わせの数を求める問題
A社はケーブル持ってて
B社はケーブル持ってないので
B社がなんとかなる組み合わせ(ケーブルがつながってる組み合わせ)
の数を数える
#include<iostream> #include<vector> #include<string> #include<stack> #include<queue> #include<cmath> #include<cstdio> using namespace std; class CentaurCompanyDiv2{ private: bool conect[60][60]; long long dp[60]; int N; bool vis[60]; vector<int> sort; public: long long dfs(int x){ vis[x]=1; if(dp[x]!=-1){ return dp[x]; } long long res=1; for(int i=0;i<N;i++){ if(vis[i]==0 && conect[x][i]==1){ res*=(dfs(i)+1); if(res==0){ cout<<"hogehoge"<<x<<i<<endl; } } } if(res==0){ cout<<"hogee"<<endl; } dp[x]=res; cout<<x<<" "<<dp[x]<<endl; return res; } long long count(vector <int> a, vector <int> b){ long long ans=1; for(int i=0;i<60;i++){ dp[i]=-1; for(int j=0;j<60;j++){ conect[i][j]=0; } } N=a.size()+1; for(int i=0;i<N-1;i++){ conect[a[i]-1][b[i]-1]=1; conect[b[i]-1][a[i]-1]=1; } for(int i=0;i<N;i++){ vis[i]=0; } dfs(0); for(int i=0;i<N;i++){ ans+=dp[i]; } return ans; } };
ケーブル接続が木になっている
(木:ループがないグラフ)
各ノード毎にdpを行う
木dpってのになるっぽい
各ノード以下の木でできる組み合わせの数を保持させる
(枝の長さ*枝の長さ)*枝の長さ・・・・
みたいな感じ
深さ優先探索しながらDPして
dpで保持した値を全部足す+[B社がなにも持ってないパターンの1]
が答え