POJ 3140 Contestants Division「建议收藏」

全栈程序员-站长 • 2022年1月23日上午11:00 • 未分类 • 阅读 51

大家好，又见面了，我是全栈君。

题目大意：

给出一棵树。求去掉一条边之后两棵子树节点权值和作差的最小值。

解题思路：

这不知道怎么用树形DP做，仅仅是个DFS就过了。还手残了一次。

思路详细看代码。

以下是代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <map>
#include <queue>
using namespace std;

int min(int a,int b)
{
    if(a>b)a=b;
    return a;
}
int max(int a,int b)
{
    if(a<b)a=b;
    return a;
}
struct node
{
    int to,next;
} edge[100005*2];
int n,m,cnt,head[100005];
long long weight[100005],min1,sum;
const long long inf = 100000000000000ll;
bool vis[100005];
void addedge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
bool chack(int src)
{
    int t=head[src];
    while(t!=-1)
    {
        if(!vis[edge[t].to])return true;
        t=edge[t].next;
    }
    return false;
}
long long llaabs(long long num)
{
    if(num<0)num=-num;
    return num;
}
long long dfs(int src)
{
    long long ans=weight[src],temp;
    vis[src]=true;
    if(chack(src))
    {
        int t=head[src];
        while(t!=-1)
        {
            if(!vis[edge[t].to])
            {
                temp=dfs(edge[t].to);
                min1=min(min1,llaabs(sum-temp-temp));
                ans+=temp;
            }
            t=edge[t].next;
        }
    }
    return ans;
}
int main()
{
    int case1=1;
    while(scanf("%d%d",&n,&m),n||m)
    {
        cnt=0;
        int u,v;
        min1=inf;
        sum=0;
        memset(vis,false,sizeof(vis));
        memset(head,-1,sizeof(head));
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&weight[i]);
            sum+=weight[i];
        }
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v);
        }
        dfs(1);
        printf("Case %d: %lld\n",case1++,min1);
    }
    return 0;
}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116301.html原文链接：https://javaforall.net