[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
【样例1输入】
5 4
1 2
2 3
3 4
3 5
【样例2输入】
4 6
1 2
2 3
1 3
3 4
2 4
1 4
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;
}