题解 P1352 【没有上司的舞会】
shadowice1984
2017-09-23 20:36:42
邻接矩阵存图~
对于一个点，令d（i，j）表示他去或不去，所有子树的和；
那么，只需要依次加上所有点，即可完成状态转移。
另外，记忆话搜索需要从根开始。
所以需要搜一遍，找到校长。
上代码；
```cpp
#include<stdio.h>
#include<algorithm>
using namespace std;
int n;bool map[6000][6000];
int val[6000];int d[6000][2];
int mdfs(int x,int jud)//记忆话搜索
{
if(d[x][jud]!=-1)
{
return d[x][jud];
}
if(jud==0)//不去
{
d[x][jud]=0;//消掉-1的标记
for(int i=0;i<n;i++)
{
if(map[x][i])//查找邻接矩阵
d[x][jud]+=max(mdfs(i,0),mdfs(i,1));//子树和
}
}
else if(jud==1)//去
{
d[x][jud]=val[x];//加上权值
for(int i=0;i<n;i++)
{
if(map[x][i])
d[x][jud]+=mdfs(i,0);//下属只能不去
}
}
//printf("mdfs %d %d=%d\n",x,jud,d[x][jud]);调试语句
return d[x][jud];
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)//手动memset~
{
for(int j=0;j<2;j++)
{
d[i][j]=-1;
}
}
for(int i=0;i<n;i++)
{
scanf("%d",&val[i]);
}
for(int i=0;i<n-1;i++)
{
int u;int v;
scanf("%d%d",&u,&v);
map[v-1][u-1]=true;
}
int start=0;
for(int i=0;i<n;i++)//搜一遍图，找校长
{
for(int j=0;j<n;j++)
{
if(map[j][i])goto skip;
}
start=i;break;
skip:;
}
int res=max(mdfs(start,0),mdfs(start,1));//校长去与不去
printf("%d",res);
return 0;//拜拜程序
}
```