首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#13161

联盟 题目描述 在国际会议上,共有 n 个国家需要加入三个联盟中的一个。任何两个接壤的国家不能加入相同的联盟。现在给出各国的接壤情况,请计算存在多少种合法的联盟…

联盟

题目描述

在国际会议上,共有 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种。

限制

时间限制:1000ms

内存限制:512MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; int n; vector&lt;vector&lt;int&gt;&gt; adj; vector&lt;int&gt; color; int count = 0; bool isValid(int country, int c) {     for (int i = 0; i &lt; country; ++i) {         if (adj[i][country] &amp;&amp; color[i] == c) {             return false;         }     }     return true; } void dfs(int country) {     if (country == n) {         count++;         return;     }          for (int c = 1; c &lt;= 3; ++c) {         if (isValid(country, c)) {             color[country] = c;             dfs(country + 1);             color[country] = 0;         }     } } int main() {     cin &gt;&gt; n;     adj.resize(n, vector&lt;int&gt;(n, 0));     color.resize(n, 0);          for (int i = 0; i &lt; n-1; ++i) {         for (int j = i+1; j &lt; n; ++j) {             cin &gt;&gt; adj[i][j];             adj[j][i] = adj[i][j];         }     }          dfs(0);     cout &lt;&lt; count &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。