[HNOI2019]校园旅行(构造+生成树+动规)
2024-08-27 23:27:05
题目
做法
最朴素的做法就是点对扩展\(O(m^2)\)
发现\(n\)比较小,我们是否能从\(n\)下手减少边数呢?是肯定的
单独看一个颜色的联通块,如果是二分图,我们生产树和原来的效果相同
如果不是二分图,是会有一个环的,在树上随便圈一个自环和原来的效果相同
而看不同颜色的连边,一定是二分图,再生产树就好了
总边数是\(n\)级的,总复杂度\(O(n^2)\)
Code
#include<bits/stdc++.h>
#include<queue>
typedef int LL;
const LL maxn=5009,maxm=500009;
inline LL Read(){
LL x(0),f(1); char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<3)+(x<<1)+c-'0'; c=getchar();
}
return x*f;
}
LL f;
LL visit[maxn],col[maxn],a[maxn],fa[maxn];
LL n,m,q,top;
LL mark[maxn][maxn];
struct edge{
LL u,v;
}e[maxm];
LL Get_fa(LL x){
return fa[x]==x?x:fa[x]=Get_fa(fa[x]);
}
struct Mp{
struct node{
LL to,nxt;
}dis[maxm<<1];
LL num;
LL head[maxn];
inline void Add(LL u,LL v){
dis[++num]=(node){v,head[u]}; head[u]=num;
}
void Dfs1(LL u,LL c){
visit[u]=true; col[u]=c;
for(LL i=head[u];i;i=dis[i].nxt){
LL v(dis[i].to);
if(a[v]!=a[u]) continue;
if(visit[v]){
if(col[v]==col[u]) f=true;
continue;
}
LL fx(Get_fa(u)),fy(Get_fa(v));
if(fx!=fy){
fa[fx]=fy;
e[++top]=(edge){u,v};
}
Dfs1(v,3-c);
}
}
void Dfs2(LL u){
visit[u]=true;
for(LL i=head[u];i;i=dis[i].nxt){
LL v(dis[i].to);
if(a[v]==a[u] || visit[v]) continue;
LL fx(Get_fa(u)),fy(Get_fa(v));
if(fx!=fy){
e[++top]=(edge){u,v};
fa[fx]=fy;
}
Dfs2(v);
}
}
}G1,G2;
std::queue<edge> que;
inline void Build(){
for(LL i=1;i<=n;++i) fa[i]=i;
for(LL i=1;i<=n;++i){
if(!visit[i]){
f=false;
G1.Dfs1(i,1);
if(f) G2.Add(i,i);
}
}
memset(visit,false,sizeof(visit));
for(LL i=1;i<=n;++i) fa[i]=i;
for(LL i=1;i<=n;++i)
if(!visit[i])
G1.Dfs2(i);
for(LL i=1;i<=top;++i){
LL u(e[i].u),v(e[i].v);
G2.Add(u,v); G2.Add(v,u);
}
for(LL u=1;u<=n;++u){
que.push((edge){u,u}); mark[u][u]=true;
for(LL i=G2.head[u];i;i=G2.dis[i].nxt){
LL v(G2.dis[i].to);
if(a[v]==a[u]){
que.push((edge){v,u});
mark[v][u]=mark[u][v]=true;
}
}
}
while(que.size()){
edge tmp(que.front()); que.pop();
LL u(tmp.u),v(tmp.v);
for(LL i=G2.head[u];i;i=G2.dis[i].nxt){
LL v1(G2.dis[i].to);
for(LL j=G2.head[v];j;j=G2.dis[j].nxt){
LL v2(G2.dis[j].to);
if(a[v1]==a[v2]){
if(!mark[v1][v2]){
mark[v1][v2]=mark[v2][v1]=true;
que.push((edge){v1,v2});
}
}
}
}
}
}
char s[maxn];
int main(){
n=Read(),m=Read(),q=Read();
scanf(" %s",s+1);
for(LL i=1;i<=n;++i) a[i]=s[i]-'0';
while(m--){
LL u(Read()),v(Read());
G1.Add(u,v); G1.Add(v,u);
}
Build();
while(q--){
LL u(Read()),v(Read());
if(mark[u][v]) puts("YES");
else puts("NO");
}
return 0;
}
最新文章
- MFC编程入门之二十六(常用控件:滚动条控件ScrollBar)
- Highcharts使用指南
- 转载:JAVA中关于set()和get()方法的理解及使用
- Win7 DCOM 配置中我的电脑出现红色箭头并且无属性显示的解决方法
- zk label控件内容换行
- lua if
- ddl语句
- nginx之location配置
- 深入理解ThreadLocal(一)
- Authentication
- 3 D. Least Cost Bracket Sequence
- Scrapy爬虫框架第五讲(linux环境)【download middleware用法】
- Matlab调用遗传工具箱复现论文模型求解部分
- 2019年 十款Mac上必备的实用软件列表
- OSPF进程号的意义及多进程OSPF
- java调用高德地图api实现通过ip定位访问者的城市
- VRS待解决的问题——原因及解决方案
- 拖拽控件java版
- jquery基于form-data文件上传
- mapreduce设置setMapOutputKeyClass与setMapOutputValueClass原因
热门文章
- windows安装oracle11g第二部
- Android实现“退出确认”对话框
- LeetCode 笔记系列16.1 Minimum Window Substring [从O(N*M), O(NlogM)到O(N),人生就是一场不停的战斗]
- 160525、高并发之mysql主从复制(linux)
- 160517、nginx负载均衡详解
- 160415、sql语句sort排序,sort为空的在后面
- HDU 5701 中位数计数 百度之星初赛
- MSSQL移除字符串两边的指定字符
- 服务器端Session和客户端Session(和Cookie区别)2
- python学习笔记(六)— 模块