直接进入正题

题目要求所有村庄都能接受到来自水库的水

所以

如果水库建在 i 处，则一定满足：

∀x∈[1,n],x !=i: heighti​>heightx​

看出来没有？

需要建水库的村庄，一定是所有村庄中 海拔最高的村庄

贪心思想有了

在程序里排个序就好了

怎么样验证从水库出来的水能否到达每个村庄？

大家都讲得很清楚

一个深搜 or 广搜就好了

时间复杂度： Θ(nlog2​n)

复杂度的瓶颈在于排序

#include <cstdio>
#include <algorithm>
int n,m,height[305],rank[305];
int head[305],tot;
struct Edge {
	int next,to;
} e[605];
struct town {
	int id,height;
} t[305];
inline void add(int x,int y) {
	e[++tot].next = head[x];
	e[tot].to = y;
	head[x] = tot;
}
bool cmp(town a,town b) {
	return a.height > b.height;
}
int vis[305];
//四行暴搜吼啊 
inline void search(int u) {
	vis[u] = 1;
	for(int i=head[u],v;v=e[i].to,i;i=e[i].next)
		if(!vis[v] && t[rank[u]].height > t[rank[v]].height)
			search(v);
	return ;
}
int main() {
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; ++i)scanf("%d",&t[i].height),t[i].id = i;
	std::sort(t+1,t+n+1,cmp);
	for(int i=1;i<=n;++i)rank[t[i].id] = i;//存一个每个i对应排序后的第几项 
	if(n==1) {
		printf("Oui, j'ai trouve la solution.\n1");
		return 0;
	}
	if(t[1].height == t[2].height) {//如果有两个最高点，则直接不可能 
		printf("Non");
		return 0;
	}
	for(int i=1,a,b; i<=m; ++i)scanf("%d %d",&a,&b),add(a,b),add(b,a);
	search(t[1].id);
	for(int i=1; i<=n; ++i)
		if(!vis[i]) {
			printf("Non");
			return 0;
		}
	printf("Oui, j'ai trouve la solution.\n%d",t[1].id);
	return 0;
}