link:http://www.bnuoj.com/bnuoj/problem_show.php?pid=26110

题意很明确,给你一个n*n的矩阵,代表每个人之间的所爱关系,问是否未出现“三角恋”。。

其实说的直白点就是构建图之后检查是否出现环~~~与hdu 1285大同小异,一个是求是否出现环

一个是上输出每个人的关系表。。其实可以用一个模板完成,用拓扑排序检查是否存在环、、

code:

#include <stdio.h>
#include <string.h>
#define N 2005
char map[N][N];
int degree[N];
void Topo(int n)
{
int i,j,k,flag=1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(degree[j]==0)
{
degree[j]=-1;
k=j;
break;
}
}
if(j==n)
{
flag=0;
break;
}
for(j=0;j<n;j++)
{
if(map[k][j]==’1′)
degree[j]–,map[k][j]=’0′;
}
}
if(flag)
printf(“No\n”);
else
printf(“Yes\n”);
}
int main()
{
int i,j,t,n;
int cas;
scanf(“%d”,&t);
for(cas=1;cas<=t;cas++)
{
printf(“Case #%d: “,cas);
scanf(“%d”,&n);
for(i=0;i<n;i++)
scanf(“%s”,map[i]);
memset(degree,0,sizeof(degree));
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
if(map[i][j]==’1′)
degree[j]++;
}
Topo(n);
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation