在宽广的非洲荒漠中，生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的Alpaca L. Sotomon是这个家族的领袖，外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐，他曾亲自率军粉碎河蟹帝国主义的野蛮侵略，为族人立下赫赫战功。所驼门王一生财宝无数，但因其生性节俭低调，他将财宝埋藏在自己设计的地下宫殿里，这也是今天Henry Curtis故事的起点。Henry是一个爱财如命的贪婪家伙，而又非常聪明，他费尽心机谋划了这次盗窃行动，破解重重机关后来到这座地下宫殿前。
整座宫殿呈矩阵状，由R×C间矩形宫室组成，其中有N间宫室里埋藏着宝藏，称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔，由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这N间藏宝宫室每间都架设了一扇传送门，没有宝藏的宫室不设传送门，所有的宫室传送门分为三种：
- “横天门”：由该门可以传送到同行的任一宫室；
- “纵寰门”：由该门可以传送到同列的任一宫室；
- “自由门”：由该门可以传送到以该门所在宫室为中心周围8格中任一宫室（如果目标宫室存在的话）。
深谋远虑的Henry当然事先就搞到了所驼门王当年的宫殿招标册，书册上详细记录了每扇传送门所属宫室及类型。而且，虽然宫殿内外相隔，但他自行准备了一种便携式传送门，可将自己传送到殿内任意一间宫室开始寻宝，并在任意一间宫室结束后传送出宫。整座宫殿只许进出一次，且便携门无法进行宫室之间的传送。不过好在宫室内传送门的使用没有次数限制，每间宫室也可以多次出入。
现在Henry已经打开了便携门，即将选择一间宫室进入。为得到尽多宝藏，他希望安排一条路线，使走过的不同藏宝宫室尽可能多。请你告诉Henry这条路线最多行经不同藏宝宫室的数目。
[无耻地借用洛谷的图片]
首先缩一下点……
然后跑DP……
很简单QAQ
在BZOJ写了7000B，成功拿到『最近几页的最长代码』成就
在洛谷跑了400ms，超级快。//好像空间还用的很少
|
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 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<iterator> #include<utility> #include<cmath> #include<queue> using namespace std; //graph struct no { int x,y,type,code; }nodes[100010]={0},nodes1[100010]={0},nodes2[100010]={0}; int nodenum,r,c; int vdir1[100010]={0},vdir2[100010]={0}; //tarjan int tstamp=0,dfn[100010]={0},low[100010]={0},stackx[100010]={0},headx=0; int sccnum=0,belong[100010]={0}; bool instack[100010]={0}; //DAG struct ed { int pre,to; }edge[5000010]={0}; int nodev[100010]={0},edgenum=0,pointer[100010]={0},fx,tx; //dp int f[100010]={0}; bool cmp1(no a,no b) { if (a.x==b.x) return a.y<b.y; return a.x<b.x; } bool cmp2(no a,no b) { if (a.y==b.y) return a.x<b.x; return a.y<b.y; } void tarjan(int u) { dfn[u]=low[u]=++tstamp; instack[u]=true; stackx[++headx]=u; int v; if (nodes[u].type==1)//the first condition { int pos=vdir1[nodes[u].code];//该点在nodes1里的位置 for (int i=1;pos+i<=nodenum;i++) { if (nodes1[pos+i].x==nodes[u].x) { v=nodes1[pos+i].code; if (!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if (instack[v]) low[u]=min(low[u],dfn[v]); } else break; } for (int i=1;pos-i>=1;i++) { if (nodes1[pos-i].x==nodes[u].x) { v=nodes1[pos-i].code; if (!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if (instack[v]) low[u]=min(low[u],dfn[v]); } else break; } } else if (nodes[u].type==2)//the second condition { int pos=vdir2[nodes[u].code]; for (int i=1;pos+i<=nodenum;i++) { if (nodes2[pos+i].y==nodes[u].y) { v=nodes2[pos+i].code; if (!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if (instack[v]) low[u]=min(low[u],dfn[v]); } else break; } for (int i=1;pos-i>=1;i++) { if (nodes2[pos-i].y==nodes[u].y) { v=nodes2[pos-i].code; if (!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if (instack[v]) low[u]=min(low[u],dfn[v]); } else break; } } else//the third condition { int pos=vdir1[nodes[u].code]; for (int i=1;pos+i<=nodenum;i++) { int nx=nodes1[pos+i].x,ny=nodes1[pos+i].y,posy=nodes[u].y,posx=nodes[u].x;//get position if ((nx-posx<=1) && (abs(ny-posy)<=1)) { v=nodes1[pos+i].code; if (!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if (instack[v]) low[u]=min(low[u],dfn[v]); } else if (nx>posx+1) break; } for (int i=1;pos-i>=1;i++) { int nx=nodes1[pos-i].x,ny=nodes1[pos-i].y,posy=nodes[u].y,posx=nodes[u].x;//get position if ((posx-nx<=1) && (abs(ny-posy)<=1)) { v=nodes1[pos-i].code; if (!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if (instack[v]) low[u]=min(low[u],dfn[v]); } else if (nx<posx-1) break; } } if (low[u]==dfn[u])//still instack { int cache1; sccnum++; do { cache1=stackx[headx]; headx--; belong[cache1]=sccnum; instack[cache1]=false; }while (cache1!=u); } } inline void Insert() { edgenum++; edge[edgenum].pre=pointer[fx]; edge[edgenum].to=tx; pointer[fx]=edgenum; } inline void Shrink() { for (register int k=1;k<=nodenum;k++) { fx=belong[k]; nodev[fx]++; switch (nodes[k].type) { case 1: { int pos=vdir1[nodes[k].code]; for (int i=1;pos+i<=nodenum;i++) { if (nodes1[pos+i].x==nodes[k].x) { if (fx!=belong[nodes1[pos+i].code]) { tx=belong[nodes1[pos+i].code]; Insert(); } } else break; } for (int i=1;pos-i>=1;i++) { if (nodes1[pos-i].x==nodes[k].x) { if (fx!=belong[nodes1[pos-i].code]) { tx=belong[nodes1[pos-i].code]; Insert(); } } else break; } } break; case 2: { int pos=vdir2[nodes[k].code]; for (int i=1;pos+i<=nodenum;i++) { if (nodes2[pos+i].y==nodes[k].y) { if (fx!=belong[nodes2[pos+i].code]) { tx=belong[nodes2[pos+i].code]; Insert(); } } else break; } for (int i=1;pos-i>=1;i++) { if (nodes2[pos-i].y==nodes[k].y) { if (fx!=belong[nodes2[pos-i].code]) { tx=belong[nodes2[pos-i].code]; Insert(); } } else break; } } break; case 3: { int pos=vdir1[nodes[k].code]; for (int i=1;pos+i<=nodenum;i++) { int nx=nodes1[pos+i].x,ny=nodes1[pos+i].y,posy=nodes[k].y,posx=nodes[k].x;//get position if ((nx-posx<=1) && (abs(ny-posy)<=1)) { if (fx!=belong[nodes1[pos+i].code]) { tx=belong[nodes1[pos+i].code]; Insert(); } } else if (nx>posx+1) break; } for (int i=1;pos-i>=1;i++) { int nx=nodes1[pos-i].x,ny=nodes1[pos-i].y,posy=nodes[k].y,posx=nodes[k].x;//get position if ((posx-nx<=1) && (abs(ny-posy)<=1)) { if (fx!=belong[nodes1[pos-i].code]) { tx=belong[nodes1[pos-i].code]; Insert(); } } else if (nx<posx-1) break; } } break; } } } int dp(int nownode) { if (!f[nownode]) { int prex=pointer[nownode]; while (prex) { if (!f[edge[prex].to]) f[nownode]=max(f[nownode],dp(edge[prex].to)); else f[nownode]=max(f[nownode],f[edge[prex].to]); prex=edge[prex].pre; } f[nownode]+=nodev[nownode]; } return f[nownode]; } int main() { scanf("%d%d%d",&nodenum,&r,&c); for (int i=1;i<=nodenum;i++) { scanf("%d%d%d",&nodes[i].x,&nodes[i].y,&nodes[i].type); nodes[i].code=i; } memcpy(nodes1,nodes,sizeof(nodes)); memcpy(nodes2,nodes,sizeof(nodes)); sort(nodes1+1,nodes1+nodenum+1,cmp1); sort(nodes2+1,nodes2+nodenum+1,cmp2); for (int i=1;i<=nodenum;i++)//编号为i的点在nodes1和nodes2数组里的位置 { vdir1[nodes1[i].code]=i; vdir2[nodes2[i].code]=i; } for (int i=1;i<=nodenum;i++) if (!belong[i]) tarjan(i); Shrink(); int ans=0; for (int i=1;i<=sccnum;i++) { if (!f[i]) dp(i); ans=max(ans,f[i]); } printf("%d\n",ans); return 0; } |