提高A组模拟简单的操作

wjh15101051's space

卧薪尝胆，厚积薄发。

提高A组模拟简单的操作

Date: Mon Aug 13 11:22:38 CST 2018

In Category: NoCategory

Description：

对于两个没有直接连边的点 $u,v$ ，可以将它们合并。删除 $u,v$ 及所有以它们作为端点的边，然后加入一个新点 $x$ ，将它与所有在原图中与 $u$ 或 $v$ 有直接连边的点连边。

判断是否能通过若干次合并操作使得原图成为一条链，如果能，求出这条链的最大长度。

$1\le n \le 2000$

Solution：

首先发现三元环是一定不合法的，进而又发现合并一个奇环中的两个点最后一定会产生一个偶环和一个小一点的奇环，所以只要有奇环这个图就是不合法的，所以判断只要二分图染色就可以了，求链长可以 $O(N^2)$ 暴力 $BFS$ 求最短路并枚举点对，所有联通块的最长链之和就是答案。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 2010

#define MAXM 100010

struct edge

{

	int to,nxt;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

bool col[MAXN];

bool vis[MAXN];

bool dfs(int k)

{

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])

		{

			if(col[e[i].to] ^ col[k])continue;

			else return false;

		}

		col[e[i].to] = col[k] ^ 1;

		if(!dfs(e[i].to))return false;

	}

	return true;

}

int dis[MAXN][MAXN];

void bfs(int p)

{

	queue<int> q;

	dis[p][p] = 0;

	q.push(p);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(dis[p][e[i].to] > dis[p][k] + 1)

			{

				dis[p][e[i].to] = dis[p][k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return;

}

int mark[MAXN],cnt = 0;

void paint(int k)

{

	mark[k] = cnt;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!mark[e[i].to])paint(e[i].to);

	}

	return;

}

int ans = 0;

int res[MAXN];

int main()

{

	freopen("merge.in","r",stdin);

	freopen("merge.out","w",stdout);

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

	int a,b;

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

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	col[1] = false;

	if(!dfs(1))

	{

		puts("-1");

		return 0;

	}

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

	memset(mark,0,sizeof(mark));

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

	{

		if(!mark[i])

		{

			++cnt;

			paint(i);

		}

	}

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

	{

		bfs(i);

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

		{

			if(mark[i] == mark[j])res[mark[i]] = max(res[mark[i]],dis[i][j]);

		}

	}

	for(int i = 1;i <= cnt;++i)ans += res[i];

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}

In tag: 图论-二分图

wjh15101051