addedge(u,v);
}
dfs(0,-1);
printf("$%d\n",dp[0][0]);
}
return 0;
}
手写栈的版本
[cpp]
//#pragma comment(linker,"/STACK:1024000000,1024000000")
#include
#include
#include
#include
#define N 100010
using namespace std;
struct Edge{
int v,next;
}edge[N*2];
int head[N];
int n,cnt;
int dp[N][2];
void init(){
memset(head,-1,sizeof(head));
memset(dp,0,sizeof(dp));
cnt=0;
}
void addedge(int u,int v){
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].v=u;
edge[cnt].next=head[v];
head[v]=cnt++;
}
void dfs(){
stack
sta.push(make_pair(0, -1)); //*******
bool vis[N];
memset(vis,0,sizeof(vis));
while (!sta.empty()){ //*******
int u = sta.top().first, fa = sta.top().second; //*******
if(vis[u]==0){ //*******
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(v==fa)continue;
sta.push(make_pair(v, u)); //*******
}
vis[u]=1; //*******
}
if (u != sta.top().first) //*******
continue;
sta.pop(); //*******
int sum=0;
int ans1=0,ans2=0;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(v==fa)continue;
sum++;
ans1+=dp[v][0];
ans2+=dp[v][1];
}
if(sum==0){
dp[u][0]=0;
dp[u][1]=100;
continue ;
}
dp[u][0]=ans2;
if(sum==1) dp[u][0]=min(dp[u][0],ans1+100);
else if(sum==2) dp[u][0]=min(dp[u][0],ans1+175);
else dp[u][0]=min(dp[u][0],ans1+500); //all cover
int a[N],j=0;
if(sum>1){
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(v==fa)continue;
a[j++]=dp[v][0]-dp[v][1];
}
sort(a,a+j);
dp[u][0]=min(dp[u][0],ans2+a[0]+100); //cover 1
if(sum>2)
dp[u][0]=min(dp[u][0],ans2+a[0]+a[1]+175); //cover 2
}
if(fa==-1)continue;
dp[u][1]=ans2+100;
if(sum==1) dp[u][1]=min(dp[u][1],ans1+175);
else dp[u][1]=min(dp[u][1],ans1+500); //all cover
if(sum>1){
dp[u][1]=min(dp[u][1],ans2+a[0]+175);
}
}
}
int main(){
int t,T,u,v,i;
scanf("%d",&T);
for(t=1;t<=T;t++){
scanf("%d",&n);
init();
for(i=0;i
addedge(u,v);
}
dfs();
printf("$%d\n",dp[0][0]);
}
return 0;
}