[Solution] JZOJ-5806 简单的操作

题面

Description

从前有个包含n个点，m条边，无自环和重边的无向图。

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

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

Input

从文件merge.in中读入数据。

第一行两个正整数n;m，表示图的点数和边数。

接下来m行，每行两个正整数u;v，表示u和v之间有一条无向边

Output

输出到文件merge.out中。

如果能通过若干次合并操作使得原图成为一条链，输出链的最大长度，否则输出-1

Sample Input

Sample Output

【样例1输出】

3

【样例2输出】

-1

Data Constraint

对于30%的数据， n<=10

对于70%的数据， m<=2000

对于100%的数据， n<=1000,m<=1e5

分割线

解题思路

经过手动模拟，可以发现：当这个图中存在奇环的时候必然无解：因为三元环是肯定无解的（脚动模拟，不解释），所有的奇数元环都可以经过变换成为三元环，因此无解。

重点

不存在奇环的图是二分图（定义，自己去搜），因此搜一遍判二分图可以直接搜出无解的情况输出-1并返回

经过脚动模拟可以发现：每个联通块都可以缩成一条链，链长就是任意两点之间最短路的最大值。

我们继续经过脚动模拟可以发现：任意两个联通块之间相连得到的最大链长就是分别的最大链长之和

然后使用BFS搜一下每个联通块里的最短路中的最大值，然后累加就OK了

具体见Code

Code

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

#define ll long long

#define inf 0x3f3f3f3f

#define maxn 1005

using namespace std;

int n,m;

struct Edge{

	int t,nxt;

}edge[maxn*200];

int head[maxn],tot=0;

int fa[maxn];

int rot[maxn];

int len[maxn];

int book[maxn];

queue<int> q;

int gf(int x){return x==fa[x]?x:fa[x]=gf(fa[x]);}

void add(int st,int to){edge[tot].t=to;edge[tot].nxt=head[st];head[st]=tot;tot++;}

int gmax(int a,int b){return a>b?a:b;}

int check(int s){

	memset(book,-1,sizeof(book));

	while(q.size()) q.pop();

	book[s]=1;

	q.push(s);

	while(!q.empty()){

		int ni=q.front();

		q.pop();

		for(int i=head[ni];i!=-1;i=edge[i].nxt){

			int nt=edge[i].t;

			if(book[nt]==-1){

				book[nt]=1-book[ni];

				q.push(nt);continue;

			}

			else{

				if(book[nt]+book[ni]!=1)

					return 0;

			}

		}

	}

	return 1;

}

int sp(int s){

	while(q.size()) q.pop();

	memset(book,-1,sizeof(book));

	int ans=0;

	book[s]=0;

	q.push(s);

	while(!q.empty()){

		int ni=q.front();

		q.pop();ans=gmax(ans,book[ni]);

		for(int i=head[ni];i!=-1;i=edge[i].nxt){

			int nt=edge[i].t;

			if(book[nt]==-1){

				book[nt]=book[ni]+1;

				q.push(nt);

			}

		}

	}

	return ans;

}

int solve(int f){

	int ans=-1;

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

		if(gf(i)==f)

			ans=gmax(ans,sp(i));

	return ans;

}

int main(){

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

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

	memset(head,-1,sizeof(head));

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

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

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

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

		add(a,b);add(b,a);

		if(gf(a)!=gf(b))

			fa[gf(a)]=gf(b);

	}

	tot=0;

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

		 if(gf(i)==i){

		 	rot[tot]=i;

		 	tot++;

		 }

	for(int i=0;i<tot;i++)

		if(check(rot[i])==0){

			printf("-1\n");return 0;

		}

	int ans=0;

	for(int i=0;i<tot;i++)

		ans+=solve(rot[i]);

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

	return 0;

}

秒客网