NC106972 Cow Ski Area

题目：

• N*M的滑雪场，每个点都有他的高度，滑雪的时候只能向四周相邻的不高于当前点的高度的点滑，现在滑雪场准备修建若干个缆车线路，使得奶牛可以从任意一个点运动到滑雪场的每个点，问最少需要建多少条缆车线路。

题解：

本质还是有向图，通过加边使其强连通
• 相邻且高度一样的点建双向边，相邻但是高度不同的点建单向边，然后就是上一个题了——
tarjan缩点，统计入度和出度为零的点的个数。
• 有必要建图么？
• 相邻且高度一样的点在同一个连通块里——bfs就可以缩点，没必要tarjan

代码：

#include<map>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N  = 260000;
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
int mat[550][550];
int DFN[N];
int low[N];
int block[N];
int Stack[N];
int out[N];
int in[N];
bool instack[N];
int head[N];
int tot, sccnum, index, top, n, m;

struct node
{
    int next;
    int to;
}edge[N << 2];

void addedge(int from, int to)
{
    edge[tot].to = to;
    edge[tot].next = head[from];
    head[from] = tot++;
}

void tarjan(int u)
{
    DFN[u] = low[u] = ++index;
    Stack[top++] = u;
    instack[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        if (DFN[v] == 0)
        {
            tarjan(v);
            if (low[u] > low[v])
            {
                low[u] = low[v];
            }
        }
        else if (instack[v])
        {
            if (low[u] > DFN[v])
            {
                low[u] = DFN[v];
            }
        }
    }
    if (DFN[u] == low[u])
    {
        sccnum++;
        do
        {
            top--;
            block[Stack[top]] = sccnum;
            instack[Stack[top]] = 0;
        }while (Stack[top] != u);
    }
}

void solve(int ret)
{
    memset( instack, 0, sizeof(instack) );
    memset( DFN, 0, sizeof(DFN) );
    memset( low, 0, sizeof(low) );
    memset( in, 0, sizeof(in) );
    memset( out, 0, sizeof(out) );
    sccnum = index = top = 0;
    for (int i = 0; i < ret; i++)
    {
        if (DFN[i] == 0)
        {
            tarjan(i);
        }
    }
    if(sccnum == 1)
    {
        printf("0\n");
        return ;
    }
    for (int i = 0; i < ret; i++)
    {
        for (int j = head[i]; j != -1; j = edge[j].next)
        {
            if (block[i] != block[edge[j].to])
            {
                out[block[i]]++;
                in[block[edge[j].to]]++;
            }
        }
    }
    int a = 0, b = 0;
    for (int i = 1; i <= sccnum; i++)
    {
        if (in[i] == 0)
        {
            a++;
        }
        if (out[i] == 0)
        {
            b++;
        }
    }
    printf("%d\n", max(a, b));
}

bool is_legal(int x, int y)
{
    if (x < 0 || x >= m || y < 0 || y >= n)
    {
        return false;
    }
    return true;
}

int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        memset( head, -1, sizeof(head) );
        tot = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                scanf("%d", &mat[i][j]);
            }
        }
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                for (int k = 0; k < 4; k++)
                {
                    int ii = i + dir[k][0];
                    int jj = j + dir[k][1];
                    if ( !is_legal(ii, jj) )
                    {
                        continue;
                    }
                    if(mat[i][j] < mat[ii][jj])
                    {
                        continue;
                    }
                    else
                    {
                        addedge(i * n + j, ii * n + jj);
                    }
                }
            }
        }
        solve(n * m);
    }
    return 0;
}