其实我并没有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;

代码：

 

 1 #include<cstdio>
 2 #include<queue>
 3 #include<iostream>
 4 #include<cstring>
 5 using namespace std;
 6 inline int read(){
 7     int ans=0,f=1;char chr=getchar();
 8     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
 9     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
10     return ans*f;
11 }int fa[18000001],n,m,k,a[3001][6001],tot,ans,fail[3001][6001],dx[8]={-1,-1,1,1,0,0,1,-1},dy[8]={-1,1,-1,1,1,-1,0,0};
12 inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
13 inline int work(int &y){if(y==0) y=m+m;if(y==m+m+1) y=1;}
14 inline bool check(int x,int y,int t){
15     for(register int i(0);i<8;++i){
16         int fx=x+dx[i],fy=y+dy[i]; work(fy);
17         if(fx<1||fx>n||!fail[fx][fy]) continue;
18         int t1=a[fx][fy];
19         for(register int j(0);j<8;++j){
20             int xx=x+dx[j],yy=y+m+dy[j];work(yy);
21             if(xx<1||xx>n||!fail[xx][yy]) continue;
22             int t2=a[xx][yy];
23             if(find(t1)==find(t2)) return 0;
24         }
25     }for(register int i(0);i<8;++i){//没错我就在这里打了return 1;
26         int fx=x+dx[i],fy=y+dy[i];work(fy);
27         if(fx<1||fx>n||!fail[fx][fy]) continue;
28         int t1=a[fx][fy];
29         int tt=find(t),tt1=find(t1);
30         if(tt!=tt1) fa[tt]=fa[tt1];
31         fy=(fy+m);work(fy);
32         if(!fail[fx][fy]) continue;
33         t1=a[fx][fy];
34         int ppp=y+m;work(ppp);
35         int t2=a[x][ppp];
36         tt=find(t1),tt1=find(t2);
37         if(tt!=tt1) fa[tt]=fa[tt1];
38     }return 1;
39 }signed main(){
40     n=read(),m=read(),k=read();
41     for(register int i(1);i<=n;++i)for(register int j(1);j<=m<<1;++j)a[i][j]=++tot,fa[tot]=tot;
42     while(k--){
43         int x=read(),y=read(),t=a[x][y];
44         if(check(x,y,t)) ++ans,fail[x][y]=fail[x][y+m]=1;
45     }printf("%d",ans);
46     return 0;
47 }