A26403. 联盟
填空题
困难
知识点
题目描述
联盟
题目描述
在国际会议上，共有 n 个国家需要加入三个联盟中的一个。任何两个接壤的国家不能加入相同的联盟。现在给出各国的接壤情况，请计算存在多少种合法的联盟分配方案。
输入格式
第一行：单个整数 n 表示国家数量
第二行到第 n 行：在第 i+1 行有 n-i 个整数 ci,i+1,ci,i+2,…,ci,n，其中
ci,j=0-表示 i 号国家与 j 号国家不接壤
ci,j=1 表示 i 号国家与 j 号国家接壤
输出格式
单个整数：表示合法的联盟分配方案总数。
输入样例#1
3
1 1
1输出样例#1
6输入样例#2
4
1 1 1
1 1
1输出样例#2
0数据范围
对于 50% 的数据，1≤n≤12
对于 100% 的数据，1≤n≤20
样例1说明
三国两两接壤，形成三角形。三个联盟的排列方案为 3!=6种。
参考答案
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<vector<int>> adj;
vector<int> color;
int count = 0;
bool isValid(int country, int c) {
for (int i = 0; i < country; ++i) {
if (adj[i][country] && color[i] == c) {
return false;
}
}
return true;
}
void dfs(int country) {
if (country == n) {
count++;
return;
}
for (int c = 1; c <= 3; ++c) {
if (isValid(country, c)) {
color[country] = c;
dfs(country + 1);
color[country] = 0;
}
}
}
int main() {
cin >> n;
adj.resize(n, vector<int>(n, 0));
color.resize(n, 0);
for (int i = 0; i < n-1; ++i) {
for (int j = i+1; j < n; ++j) {
cin >> adj[i][j];
adj[j][i] = adj[i][j];
}
}
dfs(0);
cout << count << endl;
return 0;
}
上一题
下一题