四色定理+dfs(poj 1129)
2024-10-18 04:19:42
题意:要求A:BCD,A与B,C,D都不相同,求不同的值,典型的四色定理;
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set> #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
#define swa(x,y) {LL s;s=x;x=y;y=s;}
using namespace std ;
#define N 105 const double PI = acos(-1.0);
typedef long long LL ; int mapp[N][N], color[N];
int col,flag;
int n;
string s;
bool ok(int i){
for(int j = ; j <= ; j++){
if(!mapp[i][j]) continue;
if(color[i] == color[j]) return false;
}
return true;
} void dfs(int num){
if(num > n) {flag = ; return ;}
for(int i = ; i <= col; i ++){
color[num] = i;
if(ok(num))
dfs(num+);
color[num]= ; ///记得回溯时要清零啊!!!
}
} int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(cin>>n && n){
flag = ;
zero(mapp);
for(int i = ; i< n;i++){
cin>>s;
int k = s.size();
int x,y;
for(int j = ;j< k;j++){
x = s[] - 'A' +;
y = s[j] - 'A' +;
mapp[x][y] = mapp[y][x] = ;
}
}
for(col = ; col <= ; col++){
dfs();
if(flag) break;
}
if(col == )
printf("%d channel needed.\n", col);
else
printf("%d channels needed.\n", col);
}
return ;
}
最新文章
- SQL Server快捷键
- 【转载】Markdown使用笔记
- 关于获取web应用的文件路径的注意事项
- Cocos2d-x 3.2 学习笔记(十)Joystick 搖杆控件
- LeetCode : 287. Find the Duplicate Number
- 502 Proxy Error。The ISA Server denied the specified Uniform Resource Locator (URL).
- centos下配置sftp且限制用户访问目录[转]
- SSH反向连接及Autossh
- python并发(阻塞、非阻塞、epoll)
- go相关知识点
- 强化学习基础算法入门 【PPT】
- 8、java5线程池之动态缓存线程池newCachedThreadPool
- GameObject数组
- 02-分页器,自定义分页器,解耦函数分页器,分页器class
- 简单的Stack
- python开发_filecmp
- Leetcode 590. N-ary Tree Postorder Traversal
- 编程技巧:使用异或操作符(XOR)交换两数值
- 体验SpringBoot
- util.inherits