洛谷P2403 [SDOI2010]所驼门王的宝藏

xiaoxiao2022-07-06  11


某平台价值19860元的编程课程资料免费领取【点我领取】


明显同一行的横天门、同一列的纵寰门都是互达的,所以可以将其合并为一个点,自由门按题意要求建边

Tarjan缩一波点之后建出新图,在DAG上DP找最长链即可

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cctype> #include <vector> #include <functional> #include <algorithm> #include <queue> #include <set> #include <cstdlib> #include <ext/hash_map> #define eps 1e-8 #include <ext/hash_set> #define LL long long #define db double namespace __gnu_cxx { template<> struct hash< std::string > { size_t operator()( const std::string& x ) const { return hash< const char* >()( x.c_str() ); } }; } namespace __gnu_cxx { template<> struct hash<long long> { size_t operator()(long long x) const { return (unsigned) x; } }; } using namespace std; using namespace __gnu_cxx; #define LL long long #define db double template <typename T> inline void CheckMax(T &a, T &b) { a = a > b ? a : b; } template <typename T> inline void CheckMin(T &a, T &b) { a = a < b ? a : b; } template <typename T> inline void read(T &x) { int ch = getchar(); bool fg = false; for (x = 0; !isdigit(ch); ch = getchar()) { if (ch == '-') { fg = true; } } for (; isdigit(ch); ch = getchar()) { x = x * 10 + ch - '0'; } if (fg) { x = -x; } } const int MAXN = 100010; const int MAXE = 500200; const int MAXB = 20; const int INF = 0x3f3f3f3f; struct Edge { int to, nxt; Edge() {} Edge(int _to, int _nxt) : to(_to), nxt(_nxt) {} }E[MAXE]; int h[MAXN], ins[MAXN], dfn[MAXN], low[MAXN], Stack[MAXN], belong[MAXN]; int Clock_t, cnt, Ins, SCC, sz[MAXN]; inline void add_edge(int x, int y) { E[++cnt] = Edge(y, h[x]), h[x] = cnt; } void Tarjan(int x) { dfn[x] = low[x] = ++Clock_t; Stack[++Ins] = x; ins[x] = 1; for(int i = h[x]; ~i; i = E[i].nxt) { int to = E[i].to; if(!dfn[to]) { Tarjan(to); low[x] = min(low[x], low[to]); } else if(ins[to]) low[x] = min(low[x], dfn[to]); } if(low[x] == dfn[x]) { SCC++;int i = 0; do { i = Stack[Ins --]; ins[i] = 0; belong[i] = SCC; sz[SCC]++; }while(i != x); } return ; } void init() { SCC = Clock_t = cnt = Ins = 0; memset(dfn, 0, sizeof(dfn)); memset(ins, 0, sizeof(ins)); memset(belong, 0, sizeof(belong)); memset(h, -1, sizeof(h)); } int n, m, R, C, totnode, Ans; int typ[MAXN]; int dx[12] = {0, 1, 0, -1, 1, 1, -1, -1}; int dy[12] = {1, 0, -1, 0, 1, -1, 1, -1}; int in[MAXN], out[MAXN], vis[MAXN]; vector<int>rr[MAXN * 10], cc[MAXN * 10], ff; int fir[MAXN * 10][2][5]; pair<int, int> Pos[MAXN]; hash_map<long long, int>Mp; namespace DP { struct Edge { int to, nxt; Edge() {} Edge(int _to, int _nxt) : to(_to), nxt(_nxt) {} }E[MAXE]; int h[MAXN], cnt, dep[MAXN]; int pos[MAXN]; inline void add_edge(int x, int y) { E[++cnt] = Edge(y, h[x]), h[x] = cnt; } void Init() { memset(h, 0, sizeof(h)); cnt = 0; memset(dep, 0, sizeof(dep)); } void solve(int x) { vis[x] = 1; for(int i = h[x]; i; i = E[i].nxt) { int v = E[i].to; if(!vis[v]) solve(v); CheckMax(dep[x], dep[v]); } dep[x] += sz[x]; CheckMax(Ans, dep[x]); return ; } } #define Index(i ,j) (i - 1) * R + j void build() { for(int i = 1; i <= R; i++) { if(fir[i][0][1]) { int x = fir[i][0][1]; for(int j = 0; j < (int) rr[i].size(); j++) { int v = rr[i][j]; if(v == x) continue; if(typ[v] == 1) { add_edge(x, v); add_edge(v, x); } else add_edge(x, v); } } } for(int i = 1; i <= C; i++) { if(fir[i][1][2]) { int x = fir[i][1][2]; for(int j = 0; j < (int) cc[i].size(); j++) { int v = cc[i][j]; if(v == x) continue; if(typ[v] == 2) { add_edge(x, v); add_edge(v, x); } else add_edge(x, v); } } } for(int i = 0; i < (int) ff.size(); i++) { int v = ff[i]; long long x = Pos[v].first, y = Pos[v].second; for(int j = 0; j < 8; j++) { long long fx = x + dx[j], fy = y + dy[j]; if(Mp[Index(fx, fy)]) { add_edge(v, Mp[Index(fx, fy)]); } } } } signed main() { read(n), read(R), read(C); init(); for(int i = 1; i <= n; i++) { long long x, y; int p; read(x), read(y), read(p); Mp[(x - 1) * R + y] = ++totnode; Pos[totnode] = make_pair((int)x, (int)y); rr[x].push_back(totnode); cc[y].push_back(totnode); if(!fir[x][0][p]) fir[x][0][p] = totnode; if(!fir[y][1][p]) fir[y][1][p] = totnode; typ[totnode] = p; if(p == 3) ff.push_back(totnode); } build(); for(int i = 1; i <= totnode; i++) { if(!dfn[i]) { Tarjan(i); } } for(int x = 1; x <= totnode; x++) { for(int i = h[x]; ~i; i = E[i].nxt) { int v = E[i].to; if(belong[x] != belong[v]) { in[belong[v]]++; out[belong[x]]++; DP::add_edge(belong[x], belong[v]); } } } for(int i = 1; i <= SCC; i++) { if(!vis[i]) { DP::solve(i); } } printf("%d\n", Ans); return 0; }

 

转载请注明原文地址: https://www.6miu.com/read-4968546.html

最新回复(0)