#include <iostream> #include <algorithm> #include <string> #define N 30 #define f(i,a,b) for(i=a;i<b;i++)//简化代码 using namespace std; //图论中的染色问题,使得相邻两个节点颜色不同最少需要几种颜色 //搜索就是暴力的枚举,记住 bool maps[N][N]; int n,i,j,k,q; char ch[N]; void solve(){ //如果出现四个区域,每个区域都和其他三个邻接,试探C42次,用四种颜色 f(i,0,n) f(j,0,n) f(k,0,n) f(q,0,n) if(maps[i][j]&&maps[i][k] &&maps[i][q]&&maps[j][k] &&maps[j][q]&&maps[k][q]) { cout<<"4 channels needed."<<endl; return; } //如果有三个区域两两邻接,试探C32次,要用三种颜色 f(i,0,n) f(j,0,n) f(k,0,n) if(maps[i][j]&& maps[i][k] && maps[j][k]) { cout<<"3 channels needed."<<endl; return; } //如果存在两个区域邻接的情况,试探C22次,要用2种颜色 f(i,0,n) f(j,0,n) if(maps[i][j]) { cout << "2 channels needed." << endl; return; } //没有区域邻接 cout << "1 channel needed." << endl; } int main(){ while(cin>>n,n!=0){ memset(maps,0,sizeof(maps)); f(i,0,n){ cin>>ch; f(j,2,strlen(ch)){ maps[ch[0]-'A'][ch[j]-'A'] = 1; maps[ch[j]-'A'][ch[0]-'A'] = 1; } } solve(); } return 0; }
您还没有登录,请您登录后再发表评论
北大POJ1129-Channel Allocation【四色定理】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1686093
POJ1321棋盘问题 很好两种解法很值得去参考一下 完整的实验报告还有代码希望kan
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
放炮问题,北大网站 POJ 1185 算法
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析
北大POJ初级-简单搜索 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ1048,加强版的约瑟夫问题 难度中等
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ1004-Financial Management 解题报告+AC代码
北大poj1012-Joseph【经典约瑟夫问题】 poj1012-Joseph【经典约瑟夫问题】
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ 1328 java做!雷达问题!java版本!AC答案~
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
简单搜索题 数独 答案 POJ 2676 也可以没事玩玩数独。
百练POJ1088滑雪问题的源代码,C写的,不过后缀是.cpp。写的还算比较易懂,呵呵
相关推荐
北大POJ1129-Channel Allocation【四色定理】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1686093
POJ1321棋盘问题 很好两种解法很值得去参考一下 完整的实验报告还有代码希望kan
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
放炮问题,北大网站 POJ 1185 算法
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析
北大POJ初级-简单搜索 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ1048,加强版的约瑟夫问题 难度中等
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ1004-Financial Management 解题报告+AC代码
北大poj1012-Joseph【经典约瑟夫问题】 poj1012-Joseph【经典约瑟夫问题】
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ 1328 java做!雷达问题!java版本!AC答案~
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
简单搜索题 数独 答案 POJ 2676 也可以没事玩玩数独。
百练POJ1088滑雪问题的源代码,C写的,不过后缀是.cpp。写的还算比较易懂,呵呵