老葛

用户名：gezhijin666

访问量：9558

签　名：

Shit Code

等　　级
排　　名	198
经　　验	6430
参赛次数	17
文章发表	16
年　　龄	99
在职情况	待业
学　　校	GUET
专　　业	信息与计算科学

　　自我简介：

TA的其他文章

蓝桥杯基础练习VIP-矩形面积交（C语言）-题解(内含详细图解，看不懂算我输)
浏览：1388

蓝桥杯算法提高VIP-前10名-题解(C语言代码)冒泡排序求解
浏览：867

蓝桥杯算法提高VIP-单词个数统计-题解(C语言代码)
浏览：152

你可能喜欢

A+B for Input-Output Practice (VII) （C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

忙碌的小L-题解(C语言：图论弗洛伊德算法)目前题解中代码最短的，并且有图解

　　作者: 老葛　　　　发表时间：2020-02-04 20:33:00 浏览：607　|　评论：1　

原题链接：忙碌的小L

# 这是一道很有自己想法的入门题，真的有点难度
我是使用了图论来理解这道题目的，具体怎么说呢，简单的来说就是A教会B用A->B这个单向图来表示，当有很多人时候就会生成一个很多人的单项图。当然其中可能存在闭环的可能。
## 下面我们以题目所给的数据讲解
首先我们要把数据输进去，并且生成一个初始的单向图关系矩阵
![](/image_editor_upload/20200204081452_73414.png)
**上图的代码中矩阵不是对称矩阵，表示的就是一个初始的单向图，你可以代入数据验证一下**
###### 具体什么思想，你品！你细品！
## 接着我们需要对这个初始图加工
**因为这个过程是一个具有传递的过程，例如AB=1，BC=1，那么AC也一定为1**
这个过程可以把所有的这个传递关系**一丝不挂**地找出来，我用了图论的**弗洛伊德算法**（算法自行体会）
![](/image_editor_upload/20200204082005_62023.png)
经过弗洛伊德算法后，这个图才是我们最终要的图。**（你再细品）**

## 最后筛除能通过间接方式被教会的人，剩下的人就是需要小L直接去教的人
先看序号1，他能把2，3，4，5（间接）都可以教会，那么就把他们标记为1，如果有6个，假设1不能教会6，那么就不需要在管2-5之间的人了，直接从6再开始寻找就行了**（因为2-5此时已经被标记为1，并且他们能直接被1教会，根据上面弗洛伊德算法，能被2-5教会的也一定更新到了1的门户之下，所以直接从6开始）。**
```c
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i!=j&&(path[i][j]==1)&&(number[i]!=1))//如果number[i]==1，在之前地图一定会更新到其他的位置。 
			number[j]=1; //为1表示这个人可以通过其他人被教会，无关紧要 
		}
	} 
```
![](/image_editor_upload/20200204083103_31970.png)
**就像这样，你再品！**
## 完整代码
```c
#include<stdio.h>
int main()
{
	int n,a,i,j,k,path[201][201]={0},number[201]={0},count=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++)//输入数据，并生成初始地图 
	{
		while(1)
		{
			scanf("%d",&a);
			if(a==0)
			break;
			else
			path[i][a]=1;//储存联系 
		}
	}
	for(i=1;i<=n;i++)//程序核心，弗洛伊德算法，用来升级关系图 
	{
		for(j=1;j<=n;j++)
		{
			for(k=1;k<=n;k++)
			{
				if((path[i][k]==1)&&(path[k][j]==1))
				path[i][j]=1;
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i!=j&&(path[i][j]==1)&&(number[i]!=1))//如果number[i]==1，在之前地图一定会更新到其他的位置。 
			number[j]=1; //为1表示这个人可以通过其他人被教会，无关紧要 
		}
	} 
	for(i=1;i<=n;i++)
	{
		if(number[i]==0)
		count++;
	}
	printf("%d\n",count);
	return 0;
} 
```

0.0分

12 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

啥也不是的辣椒油

核心算法最内层的循环23，24行代码可以加一个break稍微优化一下

2020-02-09 20:48:31

老葛

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (VII) （C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

忙碌的小L-题解(C语言：图论弗洛伊德算法)目前题解中代码最短的，并且有图解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

输出正反三角形（C语言代码）

字符串的输入输出处理（C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

GC的苦恼（C语言代码）

【偶数求和】（C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

老葛

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (VII) （C语言代码）

C语言训练-计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

忙碌的小L-题解(C语言：图论弗洛伊德算法)目前题解中代码最短的，并且有图解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码） 用函数传参的方法

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

输出正反三角形 （C语言代码）

字符串的输入输出处理 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

GC的苦恼 （C语言代码）

【偶数求和】 （C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

　　评论区

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

输出正反三角形（C语言代码）

字符串的输入输出处理（C语言代码）

GC的苦恼（C语言代码）

【偶数求和】（C++代码）