【BZOJ】【1529】 【POI2005】ska Piggy banks
2024-10-19 03:26:53
本来以为是tarjan缩点……但是64MB的空间根本不足以存下原图和缩点后的新图。所以呢……并查集= =
orz hzwer
MLE的tarjan:
/**************************************************************
Problem: 1529
User: Tunix
Language: C++
Result: Memory_Limit_Exceed
****************************************************************/ //BZOJ 1529
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
const int N=; void read(int &v){
v=;int sign=; char ch=getchar();
while(ch<'' || ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){v=v*+ch-''; ch=getchar();}
v*=sign;
}
/********************tamplate*******************/
int dfn[N],low[N],dfs_clock,SCC=,belong[N],n;
int head[N],to[N],next[N],cnt;
void ins(int x,int y){
to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt;
}
int t[N],ne[N],h[N];
void add(int x,int y){
t[++cnt]=y; ne[cnt]=h[x]; h[x]=cnt;
}
bool inst[N];
int st[N],top=;
void tarjan(int x){
int y;
dfn[x]=low[x]=++dfs_clock;
st[top++]=x;
inst[x]=;
for(int i=head[x];i;i=next[i]){
y=to[i];
if (!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if (inst[y]) low[x]=min(low[x],dfn[y]);
}
if (dfn[x]==low[x]){
++SCC;
for(y=;y!=x;){
y=st[--top];
inst[y]=;
belong[y]=SCC;
}
}
}
int in[N];
void rebuild(){
F(x,,n)
for(int i=head[x];i;i=next[i])
if (belong[x]!=belong[to[i]]){
add(belong[x],belong[to[i]]);
in[belong[to[i]]]++;
}
}
/***********************************************/ int main(){
#ifndef ONLINE_JUDGE
freopen("1529.in","r",stdin);
#endif
read(n);
int x;
F(i,,n){
read(x);
ins(x,i);
}
F(i,,n) if (!dfn[i]) tarjan(i);
rebuild();
int ans=;
F(i,,SCC) if(in[i]==) ans++;
printf("%d\n",ans);
return ;
}
并查集:
/**************************************************************
Problem: 1529
User: Tunix
Language: C++
Result: Accepted
Time:908 ms
Memory:4712 kb
****************************************************************/ //BZOJ 1529
#include<cstdio>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
const int N=; void read(int &v){
v=;int sign=; char ch=getchar();
while(ch<'' || ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){v=v*+ch-''; ch=getchar();}
v*=sign;
}
int fa[N],n;
int getfather(int x){
if (fa[x]!=x) fa[x]=getfather(fa[x]);
return fa[x];
}
int main(){
read(n);
int x;
F(i,,n) fa[i]=i;
F(i,,n){
read(x);
int f1=getfather(i),f2=getfather(x);
if (f1!=f2) fa[f1]=f2;
}
int ans=;
F(i,,n) if (fa[i]==i) ans++;
printf("%d\n",ans);
return ;
}
最新文章
- Git学习笔记与IntelliJ IDEA整合
- MySQL 5.7 Replication 相关新功能说明
- 【JSOI2007】【Bzoj1029】建筑抢修
- iOS滤镜实现之LOMO(美图秀秀经典LOMO)
- 1125mysqbinlog日志
- JAVA设计模式--工厂方法模式
- Bootstrap+angularjs+MVC3+分页技术+角色权限验证系统
- 【题解】【排列组合】【回溯】【Leetcode】Generate Parentheses
- twitter bootstrap 2.x 3.x区别
- 【转】ASP.NET MVC 入门教程列表
- RocksDB上锁机制
- 基于 EntityFramework、Autofac 的 UnitOfWork 框架(一)
- [九省联考2018]IIIDX
- windows 环境下mysql 重置密码解决方案
- Flip String to Monotone Increasing LT926
- 音乐app各部分笔记(二)
- MATLAB 图形着色
- Windows安装nginx服务
- Android高级控件(上)
- 学习node.js的C++扩展