题解 P2835 【刻录光盘】

学无止境

2018-08-08 01:11:32

Solution

用floyed预处理,加上一些剪枝,强行DFS,竟然AC了 **92ms** 看到各位大佬的题解都是tarjan或者并查集,没学过这些东西的蒟蒻我瑟瑟发抖 在这里我分享我的DFS做法,用另一种的方法达到的类似缩点的效果(不完全一样) 直接DFS想必大家都会,先floyed处理各个人之间的连通情况,按照人的顺序搜索,每个人无非就两种情况————给他光盘、不给他光盘。并且持续更新当前获得资料的人,当全部获得资料时更新最优答案。 上面的好简单有木有QwQ 然而不加任何优化只过了3个点[难过] 原因很简单,复杂度太大,重复计算太多。 既然这道题不是很好记忆化,那么就思考剪枝: ``` 一、搜到这个人的时候,如果他已经被之前的人分享了资料,那么跳过他不搜 (重要)二、floyed之后,如果有多个人与全局中**每一个人**的连通情况都相同,那么搜一个人就好,因为他们是等价的,多余的人就标记起来不进行搜索(详见代码中del[ ]数组) 三、搜索过程中,不要每次都遍历整个表判断两点是否相连,可以提前记录好每个点与那几个点连通,减小复杂度 ``` 发现,上面的第二条消去了很多消去了点,将多个点缩为一个,对于DFS,它起到了很大的作用(剪枝),这是 **#11 AC** 的关键 QaQ 上代码,注释个人感觉很详细了 **Code:** ``` #include<cstdio> #include<iostream> using namespace std; int n,w[210][210],a,s,exist[210],num[210],g[210][210],ans=1000,del[210]; void dfs(int k,int tot,int f)//将要搜第 k 个人,已经有 tot 个人拷到了资料,此时已经刻了 f 张光盘 { if(exist[k]||del[k])//exist[k]=1 说明之前已被添加,他不能使新的人获得资料,剪枝 { dfs(k+1,tot,f);//去掉del[k]=1的人不搜,剪枝(等价的人搜一个就好) return; } if(tot==n)//保存最优答案 { ans=min(ans,f); return; } if(k==n+1) return; //所有人都搜完了 dfs(k+1,tot,f);//第一种情况,不给第 k 个人光盘 for(register int i=1;i<=num[k];i++)//处理第二种情况,给他光盘,将与之相关的人全部标记,新的人获得资料就计数 { if(!exist[g[k][i]]) tot++; exist[g[k][i]]++; } dfs(k+1,tot,f+1);//搜索第二种情况 for(register int i=1;i<=num[k];i++)//回溯 exist[g[k][i]]--; } int main() { scanf("%d",&n); for(register int i=1;i<=n;i++)//读入数据 { scanf("%d",&a); while(a!=0) w[i][a]=1,scanf("%d",&a);//相连就标记为 1 } for(int k=1;k<=n;k++)//floyed求各个人之间的连通情况,若相互连通则可以互相拷贝资料 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) w[i][j]=(w[i][j]||(w[i][k]&&w[k][j])); for(int i=1;i<=n;i++) //自己获得光盘的话,自己就有了资料 w[i][i]=1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(w[i][j]) g[i][++num[i]]=j;//减小之后搜索的复杂度,记录好相连的人,避免遍历整个表 for(int i=1;i<n;i++)//这里也是为了剪枝,如果两个人与 1~n 中**每一个人**的连通情况都相同 for(int j=i+1;j<=n;j++)//那么这两个人搜索一个即可,因为他们等价 { bool flag=false; if(del[i]) continue; for(int k=1;k<=n;k++) if(w[i][k]!=w[j][k]) { flag=true; break; } if(!flag) del[j]=1;//标记不用搜的人 } dfs(1,0,0);//快乐dfs cout<<ans<<endl; return 0; } ```