题解 P2835 【刻录光盘】
学无止境
2018-08-08 01:11:32
用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;
}
```