bzoj3388(神奇的解法)

题目大意：

约翰的表哥罗恩生活在科罗拉多州。他近来打算教他的奶牛们滑雪，但是奶牛们非常害羞，不敢在游人如织的度假胜地滑雪。没办法，他只好自己建滑雪场了．罗恩的雪场可以划分为W列L行(1≤W≤500;1≤L≤500)，每个方格有一个特定的高度H(0≤H≤9999)。奶牛可以在相临方格间滑雪，而且不能由低到高滑。为了保证任意方格可以互通，罗恩打算造一些直达缆车。缆车很强大，可以连接任意两个方格，而且是双向的。而且同一个方格也可以造多台缆车。但是缆车的建造费用贵得吓人，所以他希望造尽量少的缆车。那最少需要造多少台呢？

 

思路：

要保证任意方格可以互通，只要让每个方格都能到旁边所有方格，且旁边所有方格都能到这个方格。将可以互达的方格看成一个集合，显然集合中所有方格的高度相同。将每个集合看成一个点，从高的点向低的点连一条有向边。那么入度为0的点就需要从别的点建造一台缆车。同样出度为0的点也需要向别的点建造一台缆车。统计入度为0的点的个数和出度为0的点的个数，由于一台缆车能解决一个出度为0的点和一个入度为0的点，所以答案就是其中较大值。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

inline char Nc(){

    static char buf[],*p1=buf,*p2=buf;

    if(p1==p2){

        p2=(p1=buf)+fread(buf,,,stdin);

        if(p1==p2)return EOF;

    }

    return *p1++;

}

inline void Read(int& x){

    char c=Nc();

    for(;c<''||c>'';c=Nc());

    for(x=;c>=''&&c<='';x=(x<<)+(x<<)+c-,c=Nc());

}

int a[]={,,-,};

int b[]={,-,,};

int i,j,k,n,m,h[][],f[][],x,y,Num;

bool In[],Out[];

inline void Dfs(int x,int y){

    if(f[x][y])return;

    f[x][y]=Num;

    for(int i=;i<;i++)

    if(a[i]+x>&&a[i]+x<=n)

    for(int j=;j<;j++)

    if(b[j]+y>&&b[j]+y<=m&&h[x][y]==h[x+a[i]][y+b[i]])Dfs(x+a[i],y+b[i]);

}

int main()

{

    Read(m);Read(n);

    for(i=;i<=n;i++)

    for(j=;j<=m;j++)

    Read(h[i][j]);

    for(i=;i<=n;i++)

    for(j=;j<=m;j++)

    if(!f[i][j])Num++,Dfs(i,j);

    if(Num==)return putchar(''),;

    for(i=;i<=n;i++)

    for(j=;j<=m;j++){

        if(i<n&&f[i][j]!=f[i+][j])

        if(h[i][j]>h[i+][j])Out[f[i][j]]=In[f[i+][j]]=;else In[f[i][j]]=Out[f[i+][j]]=;

        if(j<m&&f[i][j]!=f[i][j+])

        if(h[i][j]>h[i][j+])Out[f[i][j]]=In[f[i][j+]]=;else In[f[i][j]]=Out[f[i][j+]]=;

    }

    for(i=;i<=Num;i++){

        if(!In[i])x++;

        if(!Out[i])y++;

    }

    printf("%d\n",x>y?x:y);

    return ;

}

bzoj3388