题目描述
blablabla
样例
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n;
int w[N][N];//价值
bool g[N][N];//图,是否被控
void dfs(int x,int y)//x是否控y
{
if(g[x][y]!=0) return;//被控
g[x][y]=true;//没被控
for(int i=1;i<=100;i++)
w[x][i]+=w[y][i];//价值传递性
for(int i=1;i<=100;i++)
if(g[i][x])
dfs(i,y);//搜到底
for(int i=1;i<=100;i++)
if(w[x][i]>50)
dfs(x,i);//达到%
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=100;i++)
g[i][i]=true;//初始化
for(int i=1;i<=n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
for(int j=1;j<=100;j++)
if(g[j][a])//
{
w[j][b]+=c;
if(w[j][b]>50)
dfs(j,b);
}
}
for(int i=1;i<=100;i++)
for(int j=1;j<=100;j++)
if(i!=j&&g[i][j])//除自己控自己和关系
printf("%d %d\n",i,j);
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla