程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1129-Channel Allocation(四色定理+迭代深搜)

POJ 1129-Channel Allocation(四色定理+迭代深搜)

編輯:C++入門知識

POJ 1129-Channel Allocation(四色定理+迭代深搜)


題目鏈接:傳送門

題意:n個信號站,給出連接情況,要用信號覆蓋所有信號站,要求相連的信號站不能用同一個信號。

等價問題==無向圖染色==四色定理(每個平面地圖都可以只用四種顏色來染色,而且沒有兩個鄰接的區域顏色相同。已證明)

思路:深搜一條路(枚舉顏色,判斷當前點用已有的顏色能不能染,如不能則加一種顏色,判斷強判就行了),搜到頭答案就出來了。。然後返回就可以了

注意單復數。。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define maxn 360
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define pp pair
#define ull unsigned long long
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int n, ans, ok, vis[28];
bool ma[28][28];
bool check(int u, int sb)
{
	for (int i = 1; i <= n; i++)
		if (ma[u][i] && vis[i] == sb) {
			return 0;
		}

	return 1;
}
void dfs(int u, int s)
{

	if (ok) {
		return ;
	}

	if (u == n + 1) {
		ans = s;
		ok = 1;
		return ;
	}

	for (int k = 1; k <= s; k++) {
		if (check(u, k)) {
			vis[u] = k;
			dfs(u + 1, s);
		}
	}

	vis[u] = ++s;
	dfs(u + 1, s);
}
int main()
{
	char s[38];

	while (scanf("%d", &n) != EOF && n) {
		memset(ma, 0, sizeof(ma));
		memset(vis, 0, sizeof(vis));
		getchar();

		for (int i = 1; i <= n; i++) {
			scanf("%s", s);
			int len = strlen(s);

			for (int j = 2; j <= len - 1; j++) {
				ma[i][s[j] - 'A' + 1] = 1;
				ma[s[j] - 'A' + 1][i] = 1;
			}
		}

		ok = 0;
		dfs(1, 1);

		if (ans == 1) {
			puts("1 channel needed.");
		} else {
			printf("%d channels needed.\n", ans);
		}
	}

	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved