CF1061E Politics E. Politics 解题报告

CF1061E Politics E. Politics

考虑利用树的性质，因为是子树问题，所以放到dfs序上。

只考虑一个树，问题是每个区间选恰好\(k\)个。因为区间其实是子树，所以区间要么包含，要么不交。

所以可以把区间拆开，拆开很多个互相独立的区间。

问题就变成了有若干个，从每个集合中选择\(k_i\)个数字，最大化权。

考虑两棵树的情况，每个点选择或者不选择，又恰好只有两颗树，考虑费用流

\(s\)连每个条件的虚点，流量为\(k_i\)，边权为\(0\)，这个虚点连可以选择的点集的每个点，流量\(1\)，边权\(0\)

然后另一个集合同理连\(t\)

点自己拆一下点就可以了。

Code:

#include <cstdio>

#include <cctype>

#include <cstring>

#include <vector>

#include <algorithm>

const int SIZE=1<<21;

char ibuf[SIZE],*iS,*iT;

//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)

#define gc() getchar()

template <class T>

void read(T &x)

{

	int f=0;x=0;char c=gc();

	while(!isdigit(c)) f|=c=='-',c=gc();

	while(isdigit(c)) x=x*10+c-'0',c=gc();

	if(f) x=-x;

}

const int N=2020,M=5010;

int n,m,q0,q1,s,t,x,y;

int head[N],to[M],Next[M],edge[M],cost[M],cnt=1;

void add(int u,int v,int w,int c)

{

	to[++cnt]=v,edge[cnt]=w,cost[cnt]=c,Next[cnt]=head[u],head[u]=cnt;

	to[++cnt]=u,edge[cnt]=0,cost[cnt]=-c,Next[cnt]=head[v],head[v]=cnt;

}

int q[N*N],pre[N],dis[N],l,r;

bool spfa()

{

	memset(dis,-0x3f,sizeof dis);

	dis[q[l=r=1]=s]=0;

	while(l<=r)

	{

		int now=q[l++];

		for(int v,i=head[now];i;i=Next[i])

			if(edge[i]&&dis[v=to[i]]<dis[now]+cost[i])

			{

				dis[v]=dis[now]+cost[i];

				pre[q[++r]=v]=i;

			}

	}

	return dis[t]!=dis[0];

}

int sta[N],tot,id[N],siz[N],ned[N],eu[N],ev[N],toki;

std::vector <int> E[N];

void dfs1(int now,int fa)

{

	sta[++tot]=now;

	for(int v,i=0;i<E[now].size();i++)

		if((v=E[now][i])!=fa)

			dfs1(v,now),siz[now]+=siz[v];

	if(id[now])

	{

	    if(ned[now]-siz[now]<0) toki=1;

		add(s,id[now],ned[now]-siz[now],0);

		siz[now]=ned[now];

		int k;

		do

		{

			k=sta[tot--];

			add(id[now],k,1,0);

		}while(k!=now);

	}

}

void dfs2(int now,int fa)

{

	sta[++tot]=now;

	for(int v,i=0;i<E[now].size();i++)

		if((v=E[now][i])!=fa)

			dfs2(v,now),siz[now]+=siz[v];

	if(id[now])

	{

	    if(ned[now]-siz[now]<0) toki=1;

		add(id[now],t,ned[now]-siz[now],0);

		siz[now]=ned[now];

		int k;

		do

		{

			k=sta[tot--];

			add(k+n,id[now],1,0);

		}while(k!=now);

	}

}

int main()

{

	read(n),read(x),read(y);

	for(int w,i=1;i<=n;i++) read(w),add(i,i+n,1,w);

	m=2*n,s=++m,t=++m;

	for(int u,v,i=1;i<n;i++) read(u),read(v),E[u].push_back(v),E[v].push_back(u);

	for(int i=1;i<n;i++) read(eu[i]),read(ev[i]);

	read(q0);

	int mx;

	for(int a,i=1;i<=q0;i++)

	{

		read(a),read(ned[a]);

		id[a]=++m;

		if(a==x) mx=ned[a];

	}

	dfs1(x,0);

	memset(ned,0,sizeof ned);

	memset(id,0,sizeof id);

	memset(siz,0,sizeof siz);

	for(int i=1;i<=n;i++) E[i].clear();

	for(int i=1;i<n;i++) E[eu[i]].push_back(ev[i]),E[ev[i]].push_back(eu[i]);

	read(q1);

	for(int a,i=1;i<=q1;i++)

	{

		read(a),read(ned[a]);

		id[a]=++m;

		if(a==y&&mx!=ned[a]) toki=1;

	}

	dfs2(y,0);

	if(toki)

    {

        puts("-1");

        return 0;

    }

	int flow=0,ans=0;

	while(spfa())

	{

		++flow;

		ans+=dis[t];

		int now=t;

		while(now!=s)

		{

			--edge[pre[now]];

			++edge[pre[now]^1];

			now=to[pre[now]^1];

		}

	}

	if(flow==mx) printf("%d\n",ans);

	else puts("-1");

	return 0;

}

2019.6.1

巴特西

CF1061E Politics E. Politics 解题报告

CF1061E Politics E. Politics

最新文章

热门文章