首页 > 代码库 > Bzoj1529/POI2005 ska Piggy banks
Bzoj1529/POI2005 ska Piggy banks
题目：ska Piggy banks
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1529
题目描述：Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.
分析：
（1）算法一：如果存钱罐i有存钱罐j的钥匙，就建一条（i->j）的有向边。然后就是缩点重构图后统计入度为0的连通块个数。最后就是华丽丽的Memory_Limit_Exceed了。
（2）算法二：如果存钱罐i的钥匙在存钱罐j里，就建一条（i->j）的有向边。然后就是缩点重构图后统计出度为0的连通块个数。由于所有点的出度均为1（即只有一条出边），可以用一个数组来保存每个点的出边，这样可以比建邻接表保存图节省空间。结果Accept。
（3）算法三：观察算法二建的图，分析该图的每一个子图，发现每一个子图有且只有一个环（圈），缩点后，这个环（圈）出度为0。问题转化为求一张图有几个连通块。考虑并查集。结果Accept。
代码：
这题IO量比较大，可以考虑读入优化，但我比较懒，不想写。
算法一：不想码。
算法二：
1 #include <cstdio> 2 #include <algorithm> 3 int To[1000005]; 4 int TarjanTime,Dfn[1000005],Low[1000005],Stack[1000005]; 5 int Col[1000005],Out[1000005]; 6 void Tarjan(int v){ 7 Dfn[v]=Low[v]=++TarjanTime; 8 Stack[++Stack[0]]=v; 9 int u=To[v];10 if(!Dfn[u]){11 Tarjan(u);Low[v]=std::min(Low[v],Low[u]);12 }else if(!Col[u])Low[v]=std::min(Low[v],Dfn[u]);13 if(Dfn[v]==Low[v]){14 ++Col[0];15 for(;;){16 u=Stack[Stack[0]--];17 Col[u]=Col[0];18 if(u==v)break;19 }20 }21 }22 int main(){23 //freopen("in.txt","r",stdin);24 //freopen("out.txt","w",stdout);25 int n,ans;26 scanf("%d",&n);27 for(int i=1;i<=n;++i)scanf("%d",&To[i]);28 for(int i=1;i<=n;++i)29 if(!Dfn[i])Tarjan(i);30 for(int i=1;i<=n;++i)31 if(Col[i]!=Col[To[i]])32 ++Out[Col[i]];33 for(int i=1;i<=Col[0];++i)34 if(!Out[i])++ans;35 printf("%d",ans);36 //fclose(stdin);fclose(stdout);37 return 0;38 }39
算法三：
1 #include <cstdio> 2 int Set[1000005]; 3 int GetSet(int x){return Set[x]==x?x:Set[x]=GetSet(Set[x]);} 4 int main(){ 5 //freopen("in.txt","r",stdin); 6 //freopen("out.txt","w",stdout); 7 int n,ans=0; 8 scanf("%d",&n); 9 for(int i=1;i<=n;++i)Set[i]=i;10 for(int i=1,to;i<=n;++i){11 scanf("%d",&to);12 Set[GetSet(i)]=GetSet(to);13 }14 for(int i=1;i<=n;++i)15 ans+=(Set[i]==i);16 printf("%d",ans);17 //fclose(stdin);fclose(stdout);18 return 0;19 }
Bzoj1529/POI2005 ska Piggy banks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。