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; }