题目链接：
?id=2375
题目大意：
有一片供奶牛滑雪的滑雪场，可供滑雪的区域是W(宽)*L(长)的矩阵。上边有W*L个点。规定
奶牛从一个点只能向它上、下、左、右相邻的并且高度不大于它的点运动。现在想要在某些
点对之间架设缆车，使得奶牛可以从较低的地方想较高的地方运动，那么问题来了：最少需
要多少辆这样的缆车就可以使奶牛从每个点运动到可供滑雪区域的每个角落。
思路：
把奶牛符合从点u移动到点v的条件当做一条单向边。那么所有点和边就可以构成有向图。根
据奶牛可以从点u移动到邻近并且高度不大于它的点v，可以分为两种情况：(1)点v比点u的高
这条双向边拆分成两条单向边(u，v)和(v，u)。然后根据这种关系建图，就构成了一个有向图。
因为双向边可以互相到达，，所以邻近的且高度相同的点都可以互相到达，这里可以看做是有向
图的一个强连通分量。根据这样的性质，可将这些点进行缩点处理。
这道题目是求：可以使奶牛从每个点运动到可供滑雪区域的每个角落所需要架设的最小缆车数。
也就是使整个图变成一个强连通有向图。这里就和之前的POJ1236一样了。把一个有向无环图
出度为0的点之间最少加多少边。很明显的可以看出，答案就是max(SumIn，SumOut)。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 550;const int MAXM = MAXN*MAXN;struct EdgeNode{int to;int next;}Edges[MAXM << 2];int Head[MAXM],vis[MAXM],low[MAXM],Map[MAXN][MAXN];int dfn[MAXM],Stack[MAXM],indegree[MAXM],outdegree[MAXM];int id,m;void AddEdges(int u,int v){Edges[id].to = v;Edges[id].next = Head[u];Head[u] = id++;}int TarBFS(int pos, int lay, int &scc){vis[pos] = 1;dfn[pos] = low[pos] = lay;Stack[++m] = pos;for(int i = Head[pos]; i != -1; i = Edges[i].next){if( !vis[Edges[i].to])TarBFS(Edges[i].to, ++lay, scc);if(vis[Edges[i].to] == 1)low[pos] = min(low[pos], low[Edges[i].to]);}if(low[pos] == dfn[pos]){++scc;do{low[Stack[m]] = scc;vis[Stack[m]] = 2;}while(Stack[m–] != pos);}return 0;}void Tarjan(int N){int scc, temp, lay;scc = temp = m = 0;lay = 1;memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));for(int i = 1; i <= N; ++i)if(vis[i] == 0)TarBFS(i, lay, scc);for(int i = 1; i <= N; ++i)for(int j = Head[i]; j != -1; j = Edges[j].next)if(low[i] != low[Edges[j].to]){outdegree[low[i]]++;indegree[low[Edges[j].to]]++;}int SumIn,SumOut;SumIn = SumOut = 0;for(int i = 1; i <= scc; ++i){if( !indegree[i] )SumIn++;if( !outdegree[i] )SumOut++;}if(scc == 1)printf("0\n");elseprintf("%d\n",max(SumIn,SumOut));}int main(){int N,M;while(~scanf("%d%d",&M, &N)){memset(Head,-1,sizeof(Head));memset(outdegree,0,sizeof(outdegree));memset(indegree,0,sizeof(indegree));for(int i = 1; i <= N; ++i)for(int j = 1; j <= M; ++j)scanf("%d",&Map[i][j]);id = 0;for(int i = 1; i <= N; ++i){for(int j = 1; j <= M; ++j){for(int k = -1; k <= 1; ++k){for(int l = -1; l <= 1; ++l){if(i+k>=1 && i+k<=N && j+l>=1 && j+l<=M && (k==0||l==0) && (k||l)){if(Map[i][j] >= Map[i+k][j+l])AddEdges((i-1)*M+j,(i-1+k)*M+j+l);}}}}}Tarjan(M*N);}return 0;}
地球仍然转重，世间依旧善变，而我永远爱你。
