本文共 1515 字，大约阅读时间需要 5 分钟。
1、
2、题目大意： 有n个点，知道每个点的权值，现在要删除一条边，使得分成的两部分的差值最小，输出差值
简单的树形DP题，很快就把样例过了，一直wrong，后来才意识到0x7fffffff是整形的最大值，而题目中的数据已超出整形，最大值就不能用0x7fffffff
3、AC代码：
#include#include #include #include using namespace std;#define N 100005//注意超出整形的最大值，不能用0x7fffffff了#define INF 1000000000000000LLlong long val[N],sum;int tot;int w[N*2],next[N*2],head[N*2];long long cnt[N];long long ans,res;long long dp[N];void add_edge(int a,int b){ w[tot]=b; next[tot]=head[a]; head[a]=tot++;}void dfs(int u,int fa){ cnt[u]=val[u]; for(int i=head[u];i!=-1;i=next[i]) { int v=w[i]; if(v!=fa) { dfs(v,u); cnt[u]+=cnt[v]; if(cnt[v]-(sum-cnt[v])<0) ans=min(ans,(sum-cnt[v])-cnt[v]); else ans=min(cnt[v]-(sum-cnt[v]),ans); } } dp[u]=ans; res=min(dp[u],res);}int main(){ int n,m,a,b,cas=0; while(scanf("%d%d",&n,&m)!=EOF) { cas++; if(n==0 && m==0) break; sum=0; tot=0; memset(head,-1,sizeof(head)); memset(cnt,0,sizeof(cnt)); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%lld",&val[i]); sum+=val[i]; } for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); add_edge(a,b); add_edge(b,a); } ans=INF; res=INF; dfs(1,0); printf("Case %d: %lld\n",cas,res); } return 0;}/*7 61 4 2 1 2 1 11 22 73 74 66 25 7*/
转载地址：http://erddi.baihongyu.com/