北京手机专业网站建设公司,房产局官网查询系统,百度一下首页官网下载,sae wordpress 上传正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1325 题目大意
两棵树。要求选出一组权值和最大的点使得这两个点集在两棵树上都是连通的。 解题思路
我们枚举一个中间点iii#xff0c;然后从这个点开始扩展连通块。那么如果这个点作为根的话#x…正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1325 题目大意
两棵树。要求选出一组权值和最大的点使得这两个点集在两棵树上都是连通的。 解题思路
我们枚举一个中间点iii然后从这个点开始扩展连通块。那么如果这个点作为根的话选择一个点之前就有选择它的父节点这个一个要求然后用最大权闭合图求解即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N55,inf2147483647/3;
struct node{int to,next,w;
};
int n,val[N],ans,s,t;
queueint q;
struct Net_Flow{node a[N*200];int tot,ls[N],dep[N];void init(){memset(ls,0,sizeof(ls));tot1;}void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;return;}bool bfs(){memset(dep,0,sizeof(dep));dep[s]1;while(!q.empty())q.pop();q.push(s);while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[y]||!a[i].w)continue;dep[y]dep[x]1;if(yt)return 1;q.push(y);}}return 0;}int dinic(int x,int flow){if(xt)return flow;int rest0,k;for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[x]1!dep[y]||!a[i].w)continue;rest(kdinic(y,min(a[i].w,flow-rest)));a[i].w-k;a[i^1].wk;if(restflow)return flow;}if(!rest)dep[x]0;return rest;}int get_ans(){int ans0;while(bfs())ansdinic(s,inf);return ans;}
}nf;
struct Graph{node a[N*2];int tot,ls[N];void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;}void dfs(int x,int fa){for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;nf.addl(y,x,inf);dfs(y,x);}}
}G1,G2;
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,val[i]); for(int i1;in;i){int x,y;scanf(%d%d,x,y);x;y;G1.addl(x,y);G1.addl(y,x);}for(int i1;in;i){int x,y;scanf(%d%d,x,y);x;y;G2.addl(x,y);G2.addl(y,x);}sn1;ts1;for(int i1;in;i){nf.init();G1.dfs(i,i);G2.dfs(i,i);int sum0;for(int i1;in;i)if(val[i]0)nf.addl(s,i,val[i]),sumval[i];else nf.addl(i,t,-val[i]);sum-nf.get_ans();ansmax(ans,sum);}printf(%d,ans);
}
