P1394 山上的国度

最喜欢saber了 · 2018-11-01 21:14:09 · 题解

这道题我第一眼看上去好像可以bfs，就是先找出最高的点，再由高的点向低的点连一条有向边，然后再bfs一遍看看有没有断点，（我这个想法不知道是否正确），然后写完后我发现了一个严酷的问题，我好像不会写bfs（果然我太弱了），于是写炸了。

于是我换了一条路——用并查集，因为有个条件，水从高向低流，于是我想，可不可以这样做，通过并查集对每一组点进行操作，使更高的点作为更低的点的父亲，就是这样的操作： h_{i}>h_{j} ,fa[j]=i，于是如果他们是联通的，那么fa_{1}即为答案，否则直接输出Non（但好像没有这种样例）。

大体就是这个想法，具体实现在代码上，（求管理员过）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<queue>
using namespace std;
const int maxa = 350;
int n,m,fa[maxa],ans=0,h[maxa],u[maxa],v[maxa];
inline int find(int x){
    if(x==fa[x])return x;
    else return fa[x]=find(fa[x]);
}
void merge(int x,int y){//合并
    int rx=find(x);//一定要找父亲
    int ry=find(y);
    fa[ry]=rx;
}
bool check = true;//算是一个预处理,假设全联通。
int main(){
    //int mark,am=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&h[i]);
      //  am=max(h[i],am);//失败bfs痕迹
        //mark=i;
    }
    for(int i=1;i<=n;++i)fa[i]=i;//初始化“我是我的父亲”
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u[i],&v[i]);
        if(h[u[i]]>h[v[i]]){//合并判断
            merge(u[i],v[i]);
        }
        if(h[u[i]]<h[v[i]]){
            merge(v[i],u[i]);
        }
    }
    for(int i=2;i<=n;++i){
        if(find(i-1)!=find(i)){//如果有没在集合中的点，直接 沙特down
            check=false;
        }
    }
    if(!check){
        printf("Non");
    }
    else{
        printf("Oui, j'ai trouve la solution.\n");
        printf("%d",find(1));    
    }
    return 0;
}

请记住，我太弱了