題目大意： 約翰的表哥羅恩生活在科羅拉多州。他近來打算教他的奶牛們滑雪，但是奶牛們非常害羞，不敢在游人如織的度假勝地滑雪。沒辦法，他只好自己建滑雪場了．羅恩的雪場可以劃分為W列L行(1≤W≤500;1≤L≤500)，每個方格有一個特定的高度H(0≤H≤9999)。奶牛可以在相臨方格間滑雪，而且不能由 ...
題目大意：
約翰的表哥羅恩生活在科羅拉多州。他近來打算教他的奶牛們滑雪，但是奶牛們非常害羞，不敢在游人如織的度假勝地滑雪。沒辦法，他只好自己建滑雪場了．羅恩的雪場可以劃分為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[100000],*p1=buf,*p2=buf; if(p1==p2){ p2=(p1=buf)+fread(buf,1,100000,stdin); if(p1==p2)return EOF; } return *p1++; } inline void Read(int& x){ char c=Nc(); for(;c<'0'||c>'9';c=Nc()); for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=Nc()); } int a[4]={0,0,-1,1}; int b[4]={1,-1,0,0}; int i,j,k,n,m,h[501][501],f[501][501],x,y,Num; bool In[250000],Out[250000]; inline void Dfs(int x,int y){ if(f[x][y])return; f[x][y]=Num; for(int i=0;i<4;i++) if(a[i]+x>0&&a[i]+x<=n) for(int j=0;j<4;j++) if(b[j]+y>0&&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=1;i<=n;i++) for(j=1;j<=m;j++) Read(h[i][j]); for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(!f[i][j])Num++,Dfs(i,j); if(Num==1)return putchar('0'),0; for(i=1;i<=n;i++) for(j=1;j<=m;j++){ if(i<n&&f[i][j]!=f[i+1][j]) if(h[i][j]>h[i+1][j])Out[f[i][j]]=In[f[i+1][j]]=1;else In[f[i][j]]=Out[f[i+1][j]]=1; if(j<m&&f[i][j]!=f[i][j+1]) if(h[i][j]>h[i][j+1])Out[f[i][j]]=In[f[i][j+1]]=1;else In[f[i][j]]=Out[f[i][j+1]]=1; } for(i=1;i<=Num;i++){ if(!In[i])x++; if(!Out[i])y++; } printf("%d\n",x>y?x:y); return 0; }bzoj3388
