注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SGU320 好题,偏不用BFS  

2012-08-24 16:27:49|  分类: SGU300系列 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
看了yy的题解
其实本题真正的模型是——割点。
所以其实不用上什么BFS
直接Tarjan搞定
最近写2-SAT写熟了,所以一遍AC(事先看错题了不算)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cstdlib>
#include<set>
using namespace std;

const int MAX=500+10;

char a[MAX][MAX];
int g[MAX][MAX],lab[MAX][MAX],sum[MAX*MAX],cnt,n,m,K;
int walk[4][2]={1,0,0,-1,-1,0,0,1};

void paint(int x,int y)
{
lab[x][y]=cnt;
++sum[cnt];
int nx,ny,i;
for(i=0;i<4;++i)
{
nx=x+walk[i][0],ny=y+walk[i][1];
if(g[nx][ny]==g[x][y] && !lab[nx][ny])
paint(nx,ny);
}
}

set<int> l[MAX*MAX];

void add(int x,int y)
{
if(l[x].find(y)!=l[x].end())return;
l[x].insert(y);
l[y].insert(x);
}

int dfn[MAX*MAX],low[MAX*MAX],instack[MAX*MAX],st[MAX*MAX],color[MAX*MAX],fa[MAX*MAX],top;

int dfs(int u)
{
dfn[u]=low[u]=++top;
st[++st[0]]=u;instack[u]=1;
set<int>::iterator it;
for(it=l[u].begin();it!=l[u].end();++it)
if(!dfn[*it])
{
fa[*it]=u;
low[u]=min(low[u],dfs(*it));
}else if(instack[*it])
low[u]=min(dfn[*it],low[u]);
if(dfn[u]==low[u])
{
do
{
instack[st[st[0]]]=0;
--st[0];
}while(st[st[0]+1]!=u);
}
return low[u];
}

void get(int u)
{
if(color[u])return;
color[u]=1;
set<int>::iterator it;
for(it=l[u].begin();it!=l[u].end();++it)
if(fa[*it]==u)get(*it);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
scanf("%d %d %d",&n,&m,&K);
int i,j,k,nx,ny;
for(i=1;i<=n;++i)
scanf("%s",a[i]+1);
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
g[i][j]=a[i][j]-'0';
for(i=0;i<=n+1;++i)g[i][0]=g[i][m+1]=10;
for(i=0;i<=m+1;++i)g[0][i]=g[n+1][i]=10;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
if(!lab[i][j])
{
++cnt;
paint(i,j);
}
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
for(k=0;k<4;++k)
{
nx=i+walk[k][0],ny=j+walk[k][1];
if(lab[nx][ny]!=lab[i][j])
add(lab[nx][ny],lab[i][j]);
}
dfs(0);
for(i=1;i<=cnt;++i)
if(sum[i]>=K)
{
set<int>::iterator it;
for(it=l[i].begin();it!=l[i].end();++it)
if(fa[*it]==i && low[*it]>=dfn[i])
get(*it);
}
int ans=0;
for(i=1;i<=cnt;++i)
if(sum[i]>=K || color[i])
ans+=sum[i];
printf("%d\n",ans);
}



  评论这张
 
阅读(232)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018