tarjan，dfs

题意：

分析：

不知道怎么回事，这道题做的时候总是有点迷迷糊糊的，犯了好多低级错误。。。。。。

总之，如果接触到tarjan的话那么我们肯定能够反映过来：一定要缩点的。
缩点后啊，这张图就是一张拓扑图。有向无环。每割点都有权值，就是此节点缩的点数
那现在让我们从这张有向无环图中找一条路径，是这个路径的点权和最大！！

很简单啦，因为是有向无环图。所以我们可以对每一个点直接dfs。

int res[max_n];
int dfs(int u) {
    if (res[u] != 0)return res[u];
    for (int i = head2[u];i;i = E2[i].next) {
        int v = E2[i].to;
        res[u] = max(res[u], dfs(v));
    }res[u] += cs[u];
    return res[u];
}

int ans = 0;
    for (int i = 1;i <= colour;i++)
        ans = max(ans, dfs(i));

注意，记忆化搜索，否则tle

主要麻烦的事，对输入数据的处理。肯定是不能把矩形直接画出来的。太大了。

另外对于横天门和纵寰门，如果乖乖的连边的话肯定会爆炸！
所以我们可以这样做，对于第一个x行的横天们，我们把他与该行中每一个宫殿连上，
剩下的该行的横天门，我们都和第一个横天门链接就好了。

纵寰门也是如此！

那么***，我们就老老实实的连就好了。

注意地是，并不是所有的格子都有宫殿的，这是个相当稀疏的矩阵。我们用map进行处理。

代码如下：

#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#include<map>
using namespace std;
typedef pair<int, int> pii;
const int max_n = 1e5 + 100;
const int max_m = 12 * max_n;
int rr[max_n], cc[max_n];
int n, r, c;

struct edge{
    int to, next;
}E[max_m];
int head[max_n];
int cnt = 1;
void add(int from, int to) {
    E[cnt].to = to;
    E[cnt].next = head[from];
    head[from] = cnt++;
}

edge E2[max_m];
int head2[max_n];
int cnt2 = 1;
void add2(int from, int to) {
    E2[cnt2].to = to;
    E2[cnt2].next = head2[from];
    head2[from] = cnt2++;
}

int dfn[max_n], low[max_n], color[max_n];
int colour = 0, tot = 0;
int cs[max_n];
stack<int> st;
void tarjan(int u) {
    dfn[u] = low[u] = ++tot;st.push(u);
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (!dfn[v]) { tarjan(v);low[u] = min(low[u], low[v]); }
        else if (color[v] == 0)low[u] = min(low[u], dfn[v]);
    }if (low[u] != dfn[u])return;
    color[u] = ++colour;cs[colour]++;
    while (st.top() != u) {
        color[st.top()] = colour;
        st.pop();
        cs[colour]++;
    }st.pop();
}

int res[max_n];
int dfs(int u) {
    if (res[u] != 0)return res[u];
    for (int i = head2[u];i;i = E2[i].next) {
        int v = E2[i].to;
        res[u] = max(res[u], dfs(v));
    }res[u] += cs[u];
    return res[u];
}

struct node{
    int x, y, t;
};
map<pii, int> mp;
node input[max_n];
vector<int> rrt[max_n];
vector<int>cct[max_n];
int main() {
    ios::sync_with_stdio(0);
    cin >> n >> r >> c;
    for (int i = 1;i <= n;i++) {
        cin >> input[i].x >> input[i].y >> input[i].t;
        mp[{input[i].x, input[i].y}] = i;
        rrt[input[i].x].push_back(i);
        cct[input[i].y].push_back(i);
    }
    for (int i = 1;i <= n;i++) {
        int x = input[i].x, y = input[i].y, t = input[i].t;
        int num = mp[{x,y}];
        if (t == 1) {
            if (rr[x] != 0)add(num, rr[x]);
            else {
                for (int j : rrt[x])
                    if (j == num)continue;
                    else add(num, j);
                rr[x] = num;
            }
        }
        else if (t == 2) {
            if (cc[y] != 0)add(num, cc[y]);
            else {
                for (int j : cct[y])
                    if (j == num)continue;
                    else add(num, j);
                cc[y] = num;
            }
        }
        else {
            for (int j = x-1;j <= x+1;j++) {
                for (int k = y-1;k <= y+1;k++) {
                    if ((j == x && k == y) || !mp[{ j,k }])continue;
                    if (j <= r && j >= 1 && k <= c && k >= 1)
                        add(num, mp[{j, k}]);
                }
            }
        }
    }
    for (int i = 1;i <= n;i++)
        if (!dfn[i])tarjan(i);
    for (int i = 1;i <= n;i++) {
        for (int j = head[i];j;j = E[j].next) {
            int v = E[j].to;
            if (color[v] == color[i])continue;
            else add2(color[i], color[v]);
        }
    }int ans = 0;
    for (int i = 1;i <= colour;i++)
        ans = max(ans, dfs(i));
    cout << ans << endl;
}