Cptraser/ 三月 9, 2019/ 2019.3/ 0 comments

题目大意

给定两棵树,求两树最大联通子集点权和。(n\leq 100

Solution

考虑枚举根并指定这个点一定要选,那么如果要选i点必然要选它的父亲,而由于题目限制,选了i就必须选择i^{'}
那么就对于每个点向其父亲连边,并向另一棵树里的相同节点连边。
最后跑最大权闭合子图即可。

#include <bits/stdc++.h>
using namespace std;

char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;int y=1;x=0;for(;!isdigit(c=tc())&&c!='-';);for(c=='-'?y=-1:x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);x*=y;}

const int Maxn=3e2+5,inf=1e9;

int T,N,A[Maxn],x,y,Ans;
vector<int>f[Maxn],g[Maxn];

void Clear(void){
    for(int i=1;i<=N;i++)f[i].clear(),g[i].clear(),A[i]=0;
    Ans=x=y=N=0;
}

int Ed,St;
int head[Maxn],nxt[Maxn*10],to[Maxn*10],cap[Maxn*10],Cnt;
inline void Add(int x,int y,int tf){
    nxt[++Cnt]=head[x],to[head[x]=Cnt]=y,cap[Cnt]=tf;
    nxt[++Cnt]=head[y],to[head[y]=Cnt]=x,cap[Cnt]=0;
}
void dfs1(int x,int fa){
    if(fa)Add(x,fa,inf);
    for(int i=0;i<f[x].size();i++)if(f[x][i]^fa){
        dfs1(f[x][i],x);
    }
}
void dfs2(int x,int fa){
    if(fa)Add(x+N,fa+N,inf);
    for(int i=0;i<g[x].size();i++)if(g[x][i]^fa){
        dfs2(g[x][i],x);
    }
}

queue<int>Que;
int dep[Maxn];
bool bfs(){
    memset(dep,0,sizeof dep);
    Que.push(St);dep[St]=1;
    while (Que.size()){
        int x=Que.front();Que.pop();
        for (int i=head[x];i;i=nxt[i]){
            if (dep[to[i]]||!cap[i]) continue;
            dep[to[i]]=dep[x]+1;Que.push(to[i]);
        }
    }
    return dep[Ed]>0;
}
int dfs(int x,int exp){
    int Sum=0;
    if (x==Ed) return exp;
    for (int i=head[x];i;i=nxt[i]){
        if (dep[x]+1!=dep[to[i]]||!cap[i]||Sum>=exp) continue;
        int Min=dfs(to[i],min(exp-Sum,cap[i]));
        if (!Min){dep[to[i]]=-1;continue;}
        cap[i]-=Min;cap[i^1]+=Min;Sum+=Min;
    }
    return Sum;
}

void Solve(int root){
    memset(cap,0,sizeof cap);
    memset(head,0,sizeof head),Cnt=1;
    dfs1(root,0),dfs2(root,0);int tot=0;St=N*2+1,Ed=N*2+2;
    for(int i=1;i<=N;i++)Add(i,i+N,inf),Add(i+N,i,inf);
    for(int i=1;i<=N;i++)if(A[i]>=0)Add(St,i,A[i]),tot+=A[i];else Add(i,Ed,-A[i]);
    int tp=0;while (bfs()) tp+=dfs(St,inf);
    Ans=max(Ans,tot-tp);
}

int main()
{
    freopen("theory.in","r",stdin);
    freopen("theory.out","w",stdout);
    for(read(T);T;T--){
        read(N);for(int i=1;i<=N;i++)read(A[i]);
        for(int i=1;i<N;i++)read(x),read(y),f[x].push_back(y),f[y].push_back(x);
        for(int i=1;i<N;i++)read(x),read(y),g[x].push_back(y),g[y].push_back(x);
        for(int i=1;i<=N;i++)Solve(i);
        printf("%d\n",Ans);Clear();
    }
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*