AtCoder AGC004F Namori (图论)

题目链接

https://atcoder.jp/contests/agc004/tasks/agc004_f

题解

神仙题。。

首先考虑树的情况，树是二分图，因此假设我们对二分图进行黑白染色，那么操作就变成了，每次选择两个不同色的点来取反。然后再把黑色视作标记，那么问题就变成了，初始一些点上有标记，每次可以把标记沿着边移动到一个没标记的点，要把标记全部移动到和原来不同的位置上，求最小代价！

然后这个问题的做法就是，首先如果两种颜色个数不同就无解，否则考虑一个下界，对于每一条边而言，它至少要运送标记的次数等于其一端子树内黑白点个数差的绝对值。对所有的边求和就是答案的下界，而我们也能构造出来一种达到这个下界的方案，构造详见官方题解。

然后考虑基环树。当环是奇环和偶环时，其作用不同，因此需要分类讨论。

当环是偶环时，非树边的作用是多了一条运送标记的边。假设这条边运送了\(x\)个标记（可正可负），那么其所影响的是环上的点，需要最小化的是一个\(\sum |x-a_i|\)的形式，直接取中位数即可。

当环是奇环时，非树边的作用是可以给两个端点的标记同时\(+1\)或\(-1\). 显然\(+1\)和\(-1\)都出现是不优的，由于操作可逆可以假设是\(+1\) (否则交换初始状态和终止状态)。在这种情况下，若两种颜色个数奇偶性不同就无解，否则执行这种操作的次数\(x\)是确定的（因为初始和终止时两种颜色点数确定）。那么就可以认为给这两个端点分别加了\(x\)个标记，然后再执行树的算法即可。

时间复杂度\(O(N)\)或\(O(N\log N)\).

代码

#include<bits/stdc++.h>

#define llong long long

using namespace std;

const int N = 1e5;

struct Edge

{

	int nxt,v;

} e[(N<<1)+3];

int fe[N+3];

int fa[N+3];

bool vis[N+3];

int dep[N+3];

int a[N+3];

int s[N+3];

vector<int> vec;

int n,m,en,au,av,sum;

llong ans;

int absl(int x) {return x<0?-x:x;}

void addedge(int u,int v)

{

	en++; e[en].v = v;

	e[en].nxt = fe[u]; fe[u] = en;

}

void dfs(int u,int prv)

{

	a[u] = dep[u]&1?-1:1; sum += a[u]; s[u] = a[u];

	vis[u] = true;

	for(int i=fe[u]; i; i=e[i].nxt)

	{

		int v = e[i].v;

		if(v==prv) continue;

		if(vis[v])

		{

			au = u,av = v;

		}

		else

		{

			dep[v] = dep[u]+1;

			fa[v] = u;

			dfs(v,u);

			s[u] += s[v];

		}

	}

}

void dfs2(int u,int prv)

{

	s[u] = a[u];

	vis[u] = true;

	for(int i=fe[u]; i; i=e[i].nxt)

	{

		int v = e[i].v;

		if(v==prv) continue;

		if(vis[v])

		{

			au = u,av = v;

		}

		else

		{

			dep[v] = dep[u]+1;

			dfs2(v,u);

			s[u] += s[v];

		}

	}

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1; i<=m; i++)

	{

		int u,v; scanf("%d%d",&u,&v);

		addedge(u,v); addedge(v,u);

	}

	sum = 0; dep[1] = 0; dfs(1,0);

	if(m==n-1)

	{

		if(sum) {puts("-1");}

		else

		{

			ans = 0ll;

			for(int i=1; i<=n; i++)

			{

				ans += absl(s[i]);

			}

			printf("%lld\n",ans);

		}

	}

	else if(m==n)

	{

		if(dep[au]>dep[av]) swap(au,av);

		if((dep[au]^dep[av])&1)

		{

			if(sum) {puts("-1");}

			else

			{

				vec.clear();

				int v = av;

				while(dep[v]>dep[au])

				{

					vec.push_back(-s[v]);

					v = fa[v];

				}

				sort(vec.begin(),vec.end());

				int x = vec[vec.size()>>1];

				a[au] -= x; a[av] += x;

				for(int i=1; i<=n; i++) vis[i] = 0;

				dfs2(1,0);

				ans = absl(x);

				for(int i=1; i<=n; i++)

					{

					ans += absl(s[i]);

				}

				printf("%lld\n",ans);

			}

		}

		else

		{

			if(absl(sum)&1) {puts("-1");}

			else

			{

				if(sum>0)

				{

					for(int i=1; i<=n; i++) s[i] = -s[i],a[i] = -a[i];

					sum = -sum;

				}

				int x = (-sum)>>1;

				a[au] += x; a[av] += x;

				for(int i=1; i<=n; i++) vis[i] = 0;

				dfs2(1,0);

				ans = x;

				for(int i=1; i<=n; i++)

				{

					ans += absl(s[i]);

				}

				printf("%lld\n",ans);

			}

		}

	}

	for(int i=1; i<=n; i++) fe[i] = vis[i] = fa[i] = 0;

	for(int i=1; i<=en; i++) e[i].v = e[i].nxt = 0;

	en = 0;

	return 0;

}

巴特西

AtCoder AGC004F Namori (图论)

题目链接

题解

代码

最新文章

热门文章