description
solution
点分治+最小割。
点分必选的重心,再在树上dfs判交,转化为最大权闭合子图。
可以做\(k\)棵树的情况。
code
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#define RG register
#define il inline
using namespace std;
typedef long long ll;
typedef double dd;
const int N=205;
const int M=20;
const int mod=1e9+7;
const int inf=2147483647;
il ll read(){
RG ll d=0,w=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')d=d*10+ch-48,ch=getchar();
return d*w;
}
int n,sum,rt,ans=-inf,val[N],ret;
int head[N],nxt[N<<1],to[N<<1],cnt;
il void add(int u,int v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
int S,T,dhead[N],dnxt[N<<1],dto[N<<1],dval[N<<1],dcnt;
il void addedge(int u,int v,int w){
dto[++dcnt]=v;
dnxt[dcnt]=dhead[u];
dval[dcnt]=w;
dhead[u]=dcnt;
dto[++dcnt]=u;
dnxt[dcnt]=dhead[v];
dval[dcnt]=0;
dhead[v]=dcnt;
}
queue<int>Q;int dep[N],cur[N];
il bool bfs(){
for(RG int i=1;i<=T;i++)dep[i]=0;
while(!Q.empty())Q.pop();
dep[S]=1;Q.push(S);
while(!Q.empty()){
RG int u=Q.front();Q.pop();
for(RG int i=dhead[u];i;i=dnxt[i]){
RG int v=dto[i];
if(!dep[v]&&dval[i]){
dep[v]=dep[u]+1;
Q.push(v);
}
}
}
return dep[T];
}
int dfs(int u,int t,int power){
if(u==t)return power;
for(RG int &i=cur[u];i;i=dnxt[i]){
RG int v=dto[i];
if(dep[v]==dep[u]+1&&dval[i]){
RG int d=0;
if(d=dfs(v,t,min(power,dval[i]))){
dval[i]-=d;
dval[i^1]+=d;
return d;
}
}
}
return 0;
}
il int Dinic(){
RG int ret=0,d;
while(bfs()){
for(RG int i=1;i<=T;i++)cur[i]=dhead[i];
while(d=dfs(S,T,inf))ret+=d;
}
return ret;
}
int sz[N],w[N],cover[N],tot,pd[N];bool vis[N];
void dfscover(int u,int fa){
cover[u]=tot;pd[u]=dhead[u]=0;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==fa||vis[v])continue;
dfscover(v,u);
}
}
void dfspd(int u,int fa){
RG int x=u>n?u-n:u;pd[x]++;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==fa)continue;
RG int y=v>n?v-n:v;
if(cover[y]==tot)dfspd(v,u);
}
}
void dfsadd(int u,int fa){
RG int x=u>n?u-n:u;if(u<=n&&val[u]>0)ret+=val[u];
if(u<=n&&val[x])
val[x]>0?addedge(S,x,val[x]):addedge(x,T,-val[x]);
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==fa)continue;
RG int y=v>n?v-n:v;
if(cover[y]==tot&&pd[y]==2){
addedge(y,x,inf);
dfsadd(v,u);
}
}
}
il void calc(int u){
tot++;dcnt=1;ret=0;
S=sum+1;T=sum+2;dhead[S]=dhead[T]=0;
dfscover(u,0);
dfspd(u,0);dfspd(u+n,0);
//addedge(S,u,inf);??????
dfsadd(u,0);dfsadd(u+n,0);
ans=max(ans,ret-Dinic());
}
void getrt(int u,int fa){
sz[u]=1;w[u]=0;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==fa||vis[v])continue;
getrt(v,u);sz[u]+=sz[v];
w[u]=max(w[u],sz[v]);
}
w[u]=max(w[u],sum-sz[u]);
if(w[rt]>w[u])rt=u;
}
void solve(int u){
calc(u);vis[u]=1;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(vis[v])continue;
sum=sz[v];rt=0;
getrt(v,0);
solve(rt);
}
}
int main()
{
n=read();
for(RG int i=1;i<=n;i++)val[i]=read();
for(RG int i=1,u,v;i<n;i++){
u=read()+1;v=read()+1;add(u,v);add(v,u);
}
for(RG int i=1,u,v;i<n;i++){
u=read()+1;v=read()+1;add(u+n,v+n);add(v+n,u+n);
}
w[0]=sum=n;rt=0;
getrt(1,0);
solve(rt);
printf("%d\n",ans);
return 0;
}
Question
写最小割的时候,如果使用
addedge(S,u,inf);
来强制重心必选
就会\(WA\)在最后一个数据点
如果不写这句话就\(A\)掉了
如果有\(dalao\)知道是为什么的话欢迎在下方的评论给出建议