UVa 626 Ecosystem

题目描述在生态系统中不同物种之间存在食物链关系。例如老鹰吃老鼠老鼠吃谷物。给定一个n×nn \times nn×n的邻接矩阵其中grid[i][k] 1表示物种iii捕食物种kkk0表示不捕食。要求找出所有长度为333的循环食物链即三个物种i,j,ki, j, ki,j,k满足iii捕食jjjjjj捕食kkkkkk捕食iii。由于循环链的旋转和反向会产生重复需要去重输出。输出按一定排序规则并且统计总数。输入格式输入包含多组测试数据每组数据第一行为整数nnn3≤n≤1003 \le n \le 1003≤n≤100表示物种数量。接下来nnn行每行nnn个整数000或111表示邻接矩阵。输入直到文件结束。输出格式对于每组数据输出所有满足条件的循环链每行一个三元组物种编号按顺序输出用空格分隔然后输出一行total:X其中XXX为循环链总数。每组数据输出后跟一个空行。样例输入3 0 1 0 0 0 1 1 0 0 3 0 0 1 1 0 0 0 1 0 3 0 1 1 1 0 1 1 1 0 4 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0输出1 2 3 total:1 3 2 1 total:1 1 2 3 3 2 1 total:2 1 2 3 1 2 4 1 3 4 2 3 4 3 2 1 4 2 1 4 3 1 4 3 2 total:8题目分析本题要求找出有向图中的所有长度为333的环循环食物链。由于环是无序的但输出要求去重每个环有三个顶点它们可以按顺序排列成3!63! 63!6种排列但环的旋转和反向会产生重复。判断条件对于所有三元组(i,j,k)(i, j, k)(i,j,k)若iii捕食jjjjjj捕食kkkkkk捕食iii并且i,j,ki, j, ki,j,k互不相同且满足单调性递增或递减则输出该三元组并计数。解题思路读入nnn和邻接矩阵。三重循环枚举所有有序三元组(i,j,k)(i, j, k)(i,j,k)其中1≤i,j,k≤n1 \le i, j, k \le n1≤i,j,k≤n。若i,j,ki, j, ki,j,k中有相等则跳过。检查是否存在循环捕食关系grid[i][j] grid[j][k] grid[k][i]。若满足再检查是否满足(i j j k) || (i j j k)若满足则输出并计数。循环结束后输出总计数并打印一个空行。复杂度分析三重循环O(n3)O(n^3)O(n3)n≤100n \le 100n≤100最多10610^6106次迭代完全可接受。空间复杂度O(n2)O(n^2)O(n2)。代码实现// Ecosystem// UVa ID: 626// Verdict: Accepted// Submission Date: 2017-03-02// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intgrid[110][110],n;while(cinn){memset(grid,0,sizeof(grid));for(inti1;in;i)for(intj1;jn;j)cingrid[i][j];inttotal0;for(inti1;in;i)for(intj1;jn;j)for(intk1;kn;k){if(ij||jk||ki)continue;if(grid[i][j]grid[j][k]grid[k][i]){if((ijjk)||(ijjk)){couti j k\n;total;}}}couttotal:total\n\n;}return0;}总结本题通过三重循环枚举所有可能的三元组直接根据邻接矩阵判断循环捕食关系并利用单调性条件去重输出。由于nnn最大为100100100O(n3)O(n^3)O(n3)的算法在时间上是可行的。关键点在于理解题目对输出顺序的要求即只输出严格递增或严格递减的三元组避免重复。该解法简单直观适合作为基础枚举练习。