図のmシェーディング問題解題レポート


図のmシェーディングの問題
【問題の説明】
       無方向連通図Gとmの異なる色が与えられる.これらの色で図Gの各頂点をシェーディングし、各頂点に1色ずつ着色する.Gの各辺の2つの頂点を異なる色に着色する着色法がある場合、この図をm着色可能と呼ぶ.図のmシェーディング問題は,所与の図Gとm種の色に対して,すべての異なるシェーディング法を探し出すことである.
【プログラミングタスク】
       所与の無方向連通図Gとmの異なる色について、図のすべての異なる着色法をプログラミングして計算する.
【入力形式】
       1行目には3つの正の整数n,k,mがあり、与えられた図Gにn個の頂点とk個のエッジがあり、m種の色があることを示す.頂点番号は1,2,...,nです.次のk行では、各行に2つの正の整数u,vがあり、図Gのエッジ(u,v)を表す.
【出力形式】
       プログラムの実行が終了すると、計算された異なるシェーディングスキームの数が出力されます.
【入力サンプル】
5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
【出力サンプル】
48
【問題解きの考え方】
実はこの问题は始まったばかりで依然として考えがなくて(検索が始まったばかりであまりにも熟练していないで、、、..许しを求めます)、fyeおじいさんは再び典型的な梦の中の人!!!
おじいさんがダイヤルしてからこの問題はとてもはっきりしています.の実は私たちは前の部族衛隊のような考え方を使うことができます:敵関係と色関係は実は同じ表現方法で表すことができます;
f[i][j]は、iに接続された点がいくつか色jであることを示す.
同色のものはつながらないので、f[i][j]が0の場合は取ることができ、0でない場合は取ることができない.
周囲に同じ色の点が複数ある可能性があるため、f配列はboolではなくカウンタ(int)でなければならない.
そのまま...
【コード】
#include
#include
#include
using namespace std;
int n,k,m,x,y,i,ans=0;
int a[1001][1001],f[1001][1001];

void dfs(int dep)//dep     
{
	int i,j;
	if (dep==n+1)
	{
		ans++;
		return;
	}
	for (i=1;i<=m;++i)//  m   
	  if (!f[dep][i])//  dep       i    ,            i
	  {
	  	for (j=1;j<=n;++j)
	  	  if (a[dep][j])
	  	    f[j][i]++;//      dep     +1
	  	dfs(dep+1);
	  	for (j=1;j<=n;++j)
	  	  if (a[dep][j])
	  	    f[j][i]--;//    
	  }
    return;
} 

int main()
{
	scanf("%d%d%d",&n,&k,&m);
	for (i=1;i<=k;++i)
	{
		scanf("%d%d",&x,&y);
		a[x][y]=1;//         
		a[y][x]=1;
	}
	dfs(1);
	printf("%d",ans);
	return 0;
}