求注意到和此题类似的题
查看原帖
求注意到和此题类似的题
1308728
xsmfollower楼主2024/3/20 16:04

如果“注意,某个士兵在一个结点上时,与该结点相连的所有边将都可以被瞭望到。”改成“注意,某个士兵在一个结点上时,该结点与该结点有边相连的所有点将都可以被瞭望到。”怎么做?

这份代码会 WA:

#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
const int N=1510; int n,a[N],dp[N][2]; vector<int>e[N];
void dfs(int u,int fa) {
  dp[u][1]=a[u];
  if(e[u].size()==0) dp[u][0]=0x7f7f7f7f;
  for(auto i:e[u]) {
    if(i==fa) continue;
    dfs(i,u);
    dp[u][0]+=dp[i][1];
    dp[u][1]+=min(dp[i][0],dp[i][1]);
  }
}
int main() {
  scanf("%d",&n);
  for(int i=1;i<=n;i++) {
    int u,v,k; scanf("%d",&u),scanf("%d %d",&a[u],&k);
    while(k--) scanf("%d",&v),e[u].push_back(v),e[v].push_back(u);
  }
  return dfs(1,0),printf("%d",min(dp[1][0],dp[1][1])),0;
}
2024/3/20 16:04
加载中...