题解 P1394 【山上的国度】

· · 题解

首先我一定要吐槽一下这个题的数据给的太随便了

只有一个Non...

让我连续三次觉得自己打对了

然后当我wa了将近n次时

我无意间看到了那个输出最高村庄的序号

我当时真的是...

然后就不多说别的了直接进入题解部分

首先这道题的思想主要是搜索

然后直接贪心就可以了

贪心主要是因为只要能连通并且满足条件就一定要输出最高的村庄的序号然后就没有然后了

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

const int maxn=10010;
int num;
int n,m;
int tot;
int a[maxn];
int head[maxn];
bool book[maxn];

struct Edge{
    int to;
    int next;
}e[maxn];//邻接表

struct QwQ{
    int num;
    int high;
}qwq[maxn];//坑人的顺序

bool cmp(QwQ x,QwQ y){
    return x.high>y.high;
}

void add(int x,int y){
    tot++;
    e[tot].to=y;
    e[tot].next=head[x];
    head[x]=tot;
}//存图

void dfs(int x){
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].to;
        book[x]=1;
        if(x>y){//如果满足就往下搜否则就不搜
            num++;
            dfs(y);
        } 
        book[x]=0;
    }
}//树上搜索

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int w;
        w=i;
        cin>>qwq[i].high;
        qwq[i].num=w;
    } 
    sort(qwq+1,qwq+1+n,cmp);//贪心
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);//双向存图
    }
    for(int i=1;i<=n;i++) dfs(i);//每个点都dfs一边
    if(num<n-1) cout<<"Non"<<endl;//不满足就输出Non
    else{//否则按要求输出
        cout<<"Oui, j'ai trouve la solution."<<endl;
        cout<<qwq[1].num<<endl;
    }
    return 0;//完美结束
}

/*
4 3
1 2 4 3
1 2
3 4
2 3
这个是我自己重新打了一个样例
*/

最后祝大家ak各种oi

真心希望管理大大给过~~~

2020/2/16 update：

因为现在疫情的影响，我在家闲着没事儿，想着我这个AFO选手是不是该回来看看

于是我回来了，然后一回来就发现我题解被hack了

我就非常难受

我再看这道题发现我以前的方法不仅麻烦或者说思想根本就不对

然后我重新做了一遍于是就有了接下来的题解

我们考虑如果满足题目条件的话，他一定是一条可以遍历的链

但是这个图如果全建出来再遍历会有很多细节需要考虑

（当时我就栽到着了，没考虑全）

所以我们想着怎么能减少建图的难度呢

不难想到，题目要求从高往低走，那我们就从高往低建

这样如果建图不是一条链的话就一定不满足

是一条链的话就一定满足并且直接输出最高的就可以了

这样想的话这道题就非常简单了

那么代码如下

（我真的无法理解我以前的代码风格）

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

const int maxn=100100;
int n,m;
int num;
int tot;
int maxx;
int size=1;
int head[maxn];
bool book[maxn];

struct volige{
    int high;
    int num;
}v[maxn];

struct edge{
    int to;
    int nxt;
}e[2*maxn];

void add(int x,int y){
    tot++;
    e[tot].to=y;
    e[tot].nxt=head[x];
    head[x]=tot;
}

void dfs(int x,int fa){
    if(size==n){
        cout<<"Oui, j'ai trouve la solution.\n";
        cout<<v[1].num<<'\n';
        exit(0);
    }
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==fa) continue;
        size+=1;
        dfs(y,x);
    }
}

bool cmp(volige a,volige b){
    return a.high>b.high;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i].high;
        v[i].num=i;
    }
    int a,b;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        if(v[a].high>v[b].high) add(a,b);
        else add(b,a);
    }
    sort(v+1,v+1+n,cmp);
    dfs(v[1].num,0);
    cout<<"Non\n";
    return 0;
}

/*

5 5
5 4 3 2 1
1 2
1 4
2 3
4 3
3 5

*/

如果又被hack了请通知我

最后说一句中国加油

祝各位oier能在这条路上走得更远