- 小胖守皇宫
- 2015-11-19 07:57:50 @
#include <iostream>
#include <ctime>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <iomanip>
#include <stack>
using namespace std;
const int inf =1431655;
int dp[1505][2];
int cnt=0,head[3005];
bool mark[3005];
int m,n;
bool sign[1505];
int a[1505];
struct star{
int next,to;
}edge[3005];
void Init(){
memset(head,-1,sizeof(head));
memset(edge,0,sizeof(edge));
memset(dp,0,sizeof(dp));
memset(mark,0,sizeof(mark));
memset(sign,0,sizeof(sign));
}
void save(int u,int v){
edge[cnt].next=head[u];
edge[cnt].to=v;
head[u]=cnt++;
}
void dfs(int root,int father){
dp[root][0]=inf;
for(int i=head[root];~i;i=edge[i].next){
if(edge[i].next==-1&&i==head[root]){
mark[root]=1;
dp[root][0]=0;
sign[father]=1;
if(dp[father][0]==inf)dp[father][0]=0;
}
if(edge[i].to!=father){
dfs(edge[i].to,root);
if(!mark[edge[i].to]&&!sign[root])dp[root][0]=min(dp[edge[i].to][1],dp[root][0]);
else if(mark[edge[i].to]){
dp[root][0]+=dp[edge[i].to][1];
}
else {
dp[root][0]+=min(dp[edge[i].to][0],dp[edge[i].to][1]);
}
dp[root][1]+=min(dp[edge[i].to][0],dp[edge[i].to][1]);//选择当前节点的树其最小代价为子树选或者不选
}
}
dp[root][1]+=a[root];
}
int main (){
Init();
cin>>n;
for(int i=1;i<=n;i++){
int cost,u,count;
cin>>u>>cost>>count;
a[u]=cost;
for(int j=1;j<=count;j++){
int v;
cin>>v;
save(u,v);save(v,u);
}
}
dfs(1,1);
return 0;
}
1 条评论
-
fcoaxt LV 8 @ 2015-11-22 22:33:10
哇排版
- 1