「BZOJ1924」[SDOI2010] 所驼门王的宝藏
「问题描述」
==============================================================
在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的 Alpaca L. Sotomon 是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调, 他将财宝埋藏在自己设计的地下宫殿里,这也是今天 Henry Curtis 故事的起点。Henry 是一个爱财如命的贪婪家伙,而又非常聪明,他费尽心机谋划了这次盗窃行动,破解重重机关后来到这座地下宫殿前。
==============================================================
整座宫殿呈矩阵状,由 R×C 间矩形宫室组成,其中有 N 间宫室里埋藏着宝藏,称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔,由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这 N 间藏宝宫室每间都架设了一扇传送门,没有宝藏的宫室不设传送门,所有的宫室传送门分为三种:
1、“横天门”:由该门可以传送到同行的任一宫室;
2、“纵寰门”:由该门可以传送到同列的任一宫室;
3、“自由门”:由该门可以传送到以该门所在宫室为中心周围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,所有的传送门位置互不相同。
「输出格式」
只有一个正整数,表示你确定的路线所经过不同藏宝 宫室的最大数目。
「样例输入输出」
输入
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
「数据规模和约定」
| 测试点编号 | N | R | C |
| 1 | 16 | 20 | 20 |
| 2 | 300 | 1,000 | 1,000 |
| 3 | 500 | 100,000 | 100,000 |
| 4 | 2,500 | 5,000 | 5,000 |
| 5 | 50,000 | 5,000 | 5,000 |
| 6 | 50,000 | 1,000,000 | 1,000,000 |
| 7 | 80,000 | 1,000,000 | 1,000,000 |
| 8 | 100,000 | 1,000,000 | 1,000,000 |
| 9 | 100,000 | 1,000,000 | 1,000,000 |
| 10 | 100,000 | 1,000,000 | 1,000,000 |
题解
此题数据很弱
我的做法是每一行选定一个横天门，向该行横天门连双向边，其余门单向边
纵列同理
而自由门用map判周围八个点是否存在，存在即连边
然后缩环成DAG用dp求最长路
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int xx[8]={0,0,1,1,1,-1,-1,-1},yy[8]={1,-1,0,1,-1,0,1,-1}; int K,n,m,cnt,ind,scc,top,ans; int last[100005],last2[100005]; int x[100005],y[100005],opt[100005]; int bl[100005],low[100005],dfn[100005],num[100005],q[100005]; int deep[100005]; bool mark[100005]; vector<int> a[1000005],b[1000005]; map<int,int> mp[1000005]; struct edge{ int to,next; }e[1000005],ed[1000005]; void insert(int u,int v) { if(u==v)return; e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; } void insert2(int u,int v) { ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt; } void build() { for(int i=1;i<=n;i++) { int x=0,t=a[i].size(); for(int j=0;j<t;j++) if(opt[a[i][j]]==1){x=a[i][j];break;} for(int j=0;j<t;j++) { insert(x,a[i][j]); if(opt[a[i][j]]==1)insert(a[i][j],x); } } for(int i=1;i<=m;i++) { int x=0,t=b[i].size(); for(int j=0;j<t;j++) if(opt[b[i][j]]==2){x=b[i][j];break;} for(int j=0;j<t;j++) { insert(x,b[i][j]); if(opt[b[i][j]]==2)insert(b[i][j],x); } } for(int i=1;i<=K;i++) if(opt[i]==3) for(int k=0;k<8;k++) { int t=mp[x[i]+xx[k]][y[i]+yy[k]]; if(t)insert(i,t); } } void tarjan(int x) { low[x]=dfn[x]=++ind; q[++top]=x;mark[x]=1; for(int i=last[x];i;i=e[i].next) if(!dfn[e[i].to]) { tarjan(e[i].to); low[x]=min(low[x],low[e[i].to]); } else if(mark[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); if(low[x]==dfn[x]) { int now=0;scc++; while(now!=x) { now=q[top--];mark[now]=0; bl[now]=scc;num[scc]++; } } } void rebuild() { cnt=0; for(int x=1;x<=K;x++) { for(int i=last[x];i;i=e[i].next) if(bl[x]!=bl[e[i].to]) insert2(bl[x],bl[e[i].to]); } } void dp(int x) { mark[x]=1; for(int i=last2[x];i;i=ed[i].next) { if(!mark[ed[i].to])dp(ed[i].to); deep[x]=max(deep[x],deep[ed[i].to]); } deep[x]+=num[x]; ans=max(deep[x],ans); } int main() { K=read();n=read();m=read(); for(int i=1;i<=K;i++) { x[i]=read(),y[i]=read(),opt[i]=read(); mp[x[i]][y[i]]=i; a[x[i]].push_back(i); b[y[i]].push_back(i); } build(); for(int i=1;i<=K;i++) if(!dfn[i])tarjan(i); rebuild(); for(int i=1;i<=scc;i++) if(!mark[i])dp(i); printf("%d\n",ans); return 0; } |
OI 课件=>
