题目描述
在生态系统中，不同物种之间存在食物链关系。例如，老鹰吃老鼠，老鼠吃谷物。给定一个n×nn \times nn×n的邻接矩阵，其中grid[i][k] = 1表示物种iii捕食物种kkk，0表示不捕食。要求找出所有长度为333的循环食物链，即三个物种i,j,ki, j, ki,j,k满足iii捕食jjj，jjj捕食kkk，kkk捕食iii。由于循环链的旋转和反向会产生重复，需要去重输出。输出按一定排序规则，并且统计总数。
输入格式
输入包含多组测试数据，每组数据第一行为整数nnn（3≤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捕食jjj，jjj捕食kkk，kkk捕食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//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intgrid[110][110],n;while(cin>>n){memset(grid,0,sizeof(grid));for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)cin>>grid[i][j];inttotal=0;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)for(intk=1;k<=n;k++){if(i==j||j==k||k==i)continue;if(grid[i][j]&&grid[j][k]&&grid[k][i]){if((i<j&&j<k)||(i>j&&j>k)){cout<<i<<' '<<j<<' '<<k<<'\n';total++;}}}cout<<"total:"<<total<<"\n\n";}return0;}总结
本题通过三重循环枚举所有可能的三元组，直接根据邻接矩阵判断循环捕食关系，并利用单调性条件去重输出。由于nnn最大为100100100，O(n3)O(n^3)O(n3)的算法在时间上是可行的。关键点在于理解题目对输出顺序的要求，即只输出严格递增或严格递减的三元组，避免重复。该解法简单直观，适合作为基础枚举练习。