[JZOJ3809]设备塔

其实我并没有JZOJ的号...但既然dalao说了是JZOJ上的题，那就是了吧......

　　为了封印辉之环，古代塞姆利亚大陆的人民在异空间中建造了一座设备塔。简单的说，这座设备塔是一个漂浮在异空间中的圆柱体，圆柱体两头的圆是计算核心，而侧面则是传输信息所用的数据通道，划分成 N ∗ m 个区块。然而，随着工作的继续进行，他们希望把侧面的一部分区块也改造成其他模块。然而，任何时候都必须保证存在一条数据通道，能从圆柱体的一端通向另一端。由于无法使用辉之环掌控下的计算系统，他们寻求你的帮助来解决这个问题。他们将逐个输入想要改造的区域，而你则执行所有可行的改造并忽略可能导致数据中断的改造。

Input

　　第一行，包含两个整数 N, M, K，表示侧面的长和宽，以及操作数。

　　接下来 K 行，每行包含三个整数 xi , yi，表示操作的区块的坐标。

　　数据保证不会对已经操作成功的区块进行操作。

Output

　　输出一行，表示有多少个操作可以被执行。

•对于分值为 30 的子任务 1，保证 N, M ≤ 100, K ≤ 5000

• 对于分值为 30 的子任务 2，保证 N, M ≤ 3000, K ≤ 5000

• 对于分值为 40 的子任务 3，保证 N, M ≤ 3000, K ≤ 300000。

30分暴力做法：

对于每一个点DFS暴力判断是否可以加入

代码大概长得是这个样子：

 1 #include<cstdio>
 2 #include<queue>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<ctime>
 6 #include<cstdlib>
 7 #include<algorithm> 
 8 using namespace std;
 9 inline int read(){
10     int ans=0,f=1;char chr=getchar();
11     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
12     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
13     return ans*f;
14 }void write(int x){
15     if(x>9) write(x/10),putchar(x%10+'0');
16     else putchar(x+'0');
17 }int n,m,K,a[3005][3005],ans,Begin,ff,vis[3005][3005],fail[3005][3005],x,y,dx[]={0,1,0},dy[]={1,0,-1},ll[3005];
18 bool dfs(int x,int y){
19     if(ff) return 1;
20     if(x==n) return ff=1;
21     for(register int i=0;i<3;++i){
22         int fx=x+dx[i],fy=y+dy[i];
23         if(fy==m+1) fy=1;
24         if(fy==0) fy=m;
25         if(vis[fx][fy]) continue;
26         vis[fx][fy]=1;
27         if(dfs(fx,fy)) return 1;
28         vis[fx][fy]=0;
29     }return 0;
30 }inline bool check(int x,int y){
31     a[x][y]=1,ff=0;
32     for(int i=1;i<=m;i++) if(!ll[i]&&y!=i) return 1;
33     for(register int i=1;i<=m;i++){
34         memcpy(vis,a,sizeof(vis));
35         if(!vis[1][i]&&dfs(1,i)) return 1;
36     }a[x][y]=0;return 0;
37 }int main(){
38 //    freopen("3.in","r",stdin);
39     n=read(),m=read(),K=read();
40     for(register int i=1;i<=K;++i){
41         x=read(),y=read();
42         if(ans+1<m) {ll[y]=1,a[x][y]=1,++ans;continue;}
43         if(fail[x][y]) continue;
44         if(check(x,y)) ++ans,ll[y]=1;else fail[x][y]=1;
45     }cout<<ans;
46     return 0;
47 }

正解分析：

首先这是一个环...所以我们把它破环成链，像这个样子

　　我们把每次加入的点丢到并查集里面
　　然后再分析一下如果加入一个点之后就不能往下继续走的情况下：

　　如果当前点和它的“分身点”的连线在同一个集合（并查集维护）里那么横着的这条通道就被封锁了，就是说不存在一条道路使其能从上到下

　　不太好讲...看不懂的话看代码会容易理解一点

　　然后我这一节晚自习查了那么久的错，竟然是错在了check完了之后如果可以放就要把它填充起来，结果我手残在前面打了一个return 1;

[JZOJ3809]设备塔

全站热榜