Cow Ski Area

题目描述：

滑冰，给你一个地图，值代表高度，你只能从高到低滑，相同高度的点可以随便滑，除了根据势能来滑动，你还可以建造传送门，可以无视传送机起点到终点的高度随便走，即双向的，众所周知，传送门很贵，你现在想知道最少造几个传送门使得任意一个点都可以滑到全图所有点

思路：

和Network of Schools差不多，这次只需要求出max(入度为0，出度为0)即可，仔细想一下，这个题真的需要建图吗？建图的意义是什么？在上一个题，建图的意义是使用tarjan缩点，但是这里给出了地图，相同高度的点可以随便到，就相当于一个点，这不就和缩点一样了嘛，那我们干嘛还建图跑tarjan，直接跑dfs即可，跑完了以后就可以去搞出度入度，开俩数组就解决

这里本来是需要vis数组的，但是我发现用color记录颜色的时候就可以起到vis的作用，所以我就没开（能省一点是一点

坑点：

  • 和Network of Schools的坑点一样，直接就是一个强连通图的话直接输出0
  • 最后统计出度入度的时候，判断u到v必须是tr[u] > tr[v]，不能有等于号，因为写了等于号在一些时候就会自己连自己，形成自环，这样in和out都变了，会wa 
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
//#define inf 0x3f3f3f3f
#define MAX  2000000 + 50
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define max(a,b) (((a)>(b)) ? (a):(b))
#define min(a,b) (((a)>(b)) ? (b):(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, tot, a, b;
int tr[505][505];
int color[505][505];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool judge(int x, int y){
    if(x > n || x < 1 || y > m || y < 1)return false;
    if(color[x][y])return false;
    return true;
}

void dfs(int x, int y){
    color[x][y] = tot;
    for(int i = 0; i < 4; ++i){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(judge(xx, yy) && tr[x][y] == tr[xx][yy]){
            dfs(xx, yy);
        }
    }
    return;
}

int in[MAX], out[MAX];

int main(){
    sdd(m, n);
    for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)sd(tr[i][j]);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(!color[i][j]){
                ++tot;
                dfs(i, j);
            }
        }
    }
    if(tot == 1){//特判
        cout<<0<<endl;
        return 0;
    }
    for(int x = 1; x <= n; ++x){
        for(int y = 1; y <= m; ++y){
            for(int k = 0; k < 4; ++k){
                int xx = x + dx[k];
                int yy = y + dy[k];
                if(xx > 0 && xx <= n && yy > 0 && yy <= m && tr[x][y] > tr[xx][yy]){
                    ++in[color[xx][yy]];
                    ++out[color[x][y]];
                }
            }
        }
    }

    for(int i = 1; i <= tot; ++i){
        if(!in[i])++a;
        if(!out[i])++b;
    }
    cout<<max(a, b)<<endl;
    return 0;
}