[Solution] JZOJ-5806 简单的操作

[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;
}
上一篇:Ngrok 内网穿透神器(转载)


下一篇:PHP语法(二):数据类型、运算符和函数