NC20338. [SDOI2010]所驼门王的宝藏
描述
在宽广的非洲荒漠中，生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的Alpaca L. Sotomon是这个家族的领袖，外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐，他曾亲自率军粉碎河蟹帝国主义的野蛮侵略，为族人立下赫赫战功。所驼门王一生财宝无数，但因其生性节俭低调，他将财宝埋藏在自己设计的地下宫殿里，这也是今天Henry Curtis故事的起点。Henry是一个爱财如命的贪婪家伙，而又非常聪明，他费尽心机谋划了这次盗窃行动，破解重重机关后来到这座地下宫殿前。
整座宫殿呈矩阵状，由R×C间矩形宫室组成，其中有N间宫室里埋藏着宝藏，称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔，由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这N间藏宝宫室每间都架设了一扇传送门，没有宝藏的宫室不设传送门，所有的宫室传送门分为三种：
“横天门”：由该门可以传送到同行的任一宫室；
“纵寰门”：由该门可以传送到同列的任一宫室；
“自由门”：由该门可以传送到以该门所在宫室为中心周围8格中任一宫室（如果目标宫室存在的话）。
深谋远虑的Henry当然事先就搞到了所驼门王当年的宫殿招标册，书册上详细记录了每扇传送门所属宫室及类型。而且，虽然宫殿内外相隔，但他自行准备了一种便携式传送门，可将自己传送到殿内任意一间宫室开始寻宝，并在任意一间宫室结束后传送出宫。整座宫殿只许进出一次，且便携门无法进行宫室之间的传送。不过好在宫室内传送门的使用没有次数限制，每间宫室也可以多次出入。
现在Henry已经打开了便携门，即将选择一间宫室进入。为得到尽多宝藏，他希望安排一条路线，使走过的不同藏宝宫室尽可能多。请你告诉Henry这条路线最多行经不同藏宝宫室的数目。
输入描述
第一行给出三个正整数 N, R, C。以下 N 行，每行给出一扇传送门的信息，包含三个正整数xi, yi, Ti，表示该传送门设在位于第 xi行第yi列的藏宝宫室，类型为 Ti。Ti是一个1~3间的整数，1表示可以传送到第xi行任意一列的“横天门”，2表示可以传送到任意一行第yi列的“纵寰门”，3表示可以传送到周围8格宫室的“自由门”。保证 1 ≤ xi ≤ R，1 ≤ yi ≤ C，所有的传送门位置互不相同。
输出描述
只有一个正整数，表示你确定的路线所经过不同藏宝宫室的最大数目。
示例1
输入:
10 7 7 2 2 1 2 4 2 1 7 2 2 7 3 4 2 2 4 4 1 6 7 3 7 7 1 7 5 2 5 2 1
输出:
9
C++14(g++5.4) 解法, 执行用时: 528ms, 内存消耗: 51072K, 提交时间: 2020-08-25 14:55:07
#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;
}
C++ 解法, 执行用时: 301ms, 内存消耗: 72456K, 提交时间: 2022-06-28 11:26:05
#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e6 + 10;
int head[maxn],tot,tot2,h2[maxn];
struct node
{
int u,v,nxt;
}edge[maxn],e[maxn];
inline void add(int u,int v)
{
edge[++tot] = {u,v,head[u]},head[u] = tot;
}
inline void add_new(int u,int v)
{
e[++tot2] = {u,v,h2[u]},h2[u] = tot2;
}
int dfn[maxn],low[maxn],ins[maxn],scc[maxn],sz[maxn],sc,cnt;
int dis[maxn],disa[maxn];
stack<int> st;
void tarjan(int s)
{
dfn[s] = low[s] = ++cnt;
st.push(s),ins[s] = 1;
for(int i = head[s];i;i = edge[i].nxt)
{
int to = edge[i].v;
if(!dfn[to])
{
tarjan(to);
low[s] = min(low[s],low[to]);
}
else
{
if(ins[to]) low[s] = min(low[s],dfn[to]);
}
}
if(dfn[s] == low[s])
{
int u = s;
sc++;
while(true)
{
int tp = st.top();
st.pop();
ins[tp] = 0;
scc[tp] = sc;
// sz[sc]++;
sz[sc] += dis[tp];
if(tp == u) break;
}
}
}
map<pair<int,int>,int> mp;
int n,R,C;
int x[maxn],y[maxn],op[maxn],deg[maxn],dp[maxn];
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> R >> C;
for(int i = 1;i <= n;++i)
{
dis[R + C + i]=1;
cin >> x[i] >> y[i] >> op[i];
add(x[i],R + C + i);
add(y[i] + R,R + C + i);
if(op[i] == 1) add(R + C + i,x[i]);
else if(op[i] == 2) add(R + C + i,y[i] + R);
mp[make_pair(x[i],y[i])] = i;
}
for(int i = 1;i <= n;++i)
{
if(op[i] != 3) continue;
for(int dx = -1;dx <= 1;++dx)
{
for(int dy = -1;dy <= 1;++dy)
{
if(dx == 0 && dy == 0) continue;
int fx = dx + x[i];
int fy = dy + y[i];
if(mp.count(make_pair(fx,fy)))
{
add(R + C + i,R + C + mp[make_pair(fx,fy)]);
}
}
}
}
for(int i = 1;i <= R + C + n;++i)
{
if(!dfn[i]) tarjan(i);
}
for(int i = 1;i <= R + C + n;++i)
{
for(int j = head[i];j;j = edge[j].nxt)
{
int to = edge[j].v;
if(scc[i] != scc[to]) add_new(scc[i],scc[to]),deg[scc[to]]++;
}
}
queue<int> q;
for(int i = 1;i <= sc;++i)
{
if(deg[i] == 0)
{
q.push(i),dp[i] = sz[i];
}
}
while(!q.empty())
{
auto now = q.front();
q.pop();
for(int i = h2[now];i;i = e[i].nxt)
{
int to = e[i].v;
deg[to]--;
if(deg[to] == 0) q.push(to);
if(dp[to] < dp[now] + sz[to]) dp[to] = dp[now] + sz[to];
}
}
int ans = 0;
for(int i = 1;i <= sc;++i) ans = max(ans,dp[i]);
cout << ans << "\n";
return 0;
}