###### qq_27279883

2016-06-23 03:06 阅读 2.9k

# 回溯法与分支限界法解算法问题，求完整c或c++程序

20

``````A:BCDH
``````

B：

4

A:BCD

B:ACD

C:ABD

D:ABC

4

22 3

7 0 1

110

4 2

1 2 1

4 2 2

2 3 3

2

1 3

5

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享

#### 2条回答默认 最新

• T_Lucifer 2016-06-24 08:00

同学 你的算法课这学期挂了

点赞 评论 复制链接分享
• 至善之剑 2021-06-22 09:28

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <ctime>
#define fur(i,a,b) for(int i=(a);i<=(b);i++)
#define furr(i,a,b) for(int i=(a);i>=(b);i--)
#define cl(a) memset((a),0,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int mod =  1000000007;
const double pi = acos(-1.0);
const int N = 1010;
int n;
int neighbor[N][N];
int color[N];
int color_num = 0;
void Backtrack(int t);
char record[N];
bool color_ok(int i, int num);
int main()
{

while (scanf("%d\n", &n) !=EOF)
{
for (int i = 0; i < n; i++)
{
scanf("%s",record);
for (int j = 2; record[j] != 0; j++)
{
neighbor[i][record[j] - 'A'] = 1;
}
}
Backtrack(0);
}
return 0;
}

bool color_ok(int i, int num)
{
for (int j = 0; j < n; j++)
{
if (neighbor[i][j]==1)
if (color[j] == num)
return false;
}
return true;
}
void Backtrack(int t)
{
if (t>=n)
{
printf("%d\n", color_num);
return;
}
else
{
int i = 1;
for (; i <= t; i++) {
color[t] = i;
if (color_ok(t, i))
{
Backtrack(t + 1);
return;
}
}
color[t] = i;
if (color_ok(t,i))
{
color_num++;
Backtrack(t + 1);
return;
}
}
}

点赞 评论 复制链接分享