G 怎么网络流
  • 板块学术版
  • 楼主Unnamed114514
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/9/2 22:09
  • 上次更新2023/11/2 23:46:03
查看原帖
G 怎么网络流
556362
Unnamed114514楼主2023/9/2 22:09

RT,用圆方树过的,吃了 88 发罚时。

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,m,A,B,C,tot,cnt,dcc[N],t[N],dfn[N],low[N],fa[N],son[N],siz[N],dep[N],top[N];
bool flg[N];
vector<int> G1[N],G2[N];
stack<int> s;
void Tarjan(int u){
	low[u]=dfn[u]=++tot;
	s.push(u);
	for(auto v:G1[u]){
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]==low[v]){
				int tmp;
				++cnt;
				do{
					tmp=s.top();
					s.pop();
					G2[tmp].push_back(cnt);
					G2[cnt].push_back(tmp);
					dcc[tmp]=cnt;
				} while(tmp!=v);
				dcc[u]=cnt;
				G2[u].push_back(cnt);
				G2[cnt].push_back(u);
			}
		} else
			low[u]=min(low[u],dfn[v]);
	}
}
void init(int u,int fa){
	low[u]=dfn[u]=++tot;
	int num=0;
	for(auto v:G1[u]){
		if(!dfn[v]){
			init(v,u);
			++num;
			low[u]=min(low[u],low[v]);
			if(dfn[u]==low[v]){
				if(fa&&low[v]>=dfn[u])
					flg[u]=1;
			}
		} else
			low[u]=min(low[u],dfn[v]);
	}
	if(!fa&&num>=2)
		flg[u]=1;
}
void dfs1(int u){
	siz[u]=1;
	for(auto v:G2[u]){
		if(v==fa[u])
			continue;
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])
			son[u]=v;
	}
}
void dfs2(int u,int t){
	top[u]=t;
	if(son[u])
		dfs2(son[u],t);
	for(auto v:G2[u])
		if(v!=son[u]&&v!=fa[u])
			dfs2(v,v);
}
inline int LCA(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])
			swap(u,v);
		v=fa[top[v]];
	}
	if(dep[u]>dep[v])
		swap(u,v);
	return u;
}
inline int get(int u,int v){
	return dep[u]+dep[v]-(dep[LCA(u,v)]<<1);
}
int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m>>A>>B>>C;
	for(int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		G1[u].push_back(v);
		G1[v].push_back(u);
	}
	cnt=n;
	init(1,0);
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	Tarjan(1);
	dfs1(1);
	dfs2(1,1);
	if(!flg[A]){
		A=dcc[A];
		for(auto p:G2[A]){
			if(p==B){
				cout<<"Yes"<<endl;
				return 0;
			}
		}
	}
	if(!flg[C]){
		C=dcc[C];
		for(auto p:G2[C]){
			if(p==B){
				cout<<"Yes"<<endl;
				return 0;
			}
		}
	}
	if(!flg[B]) B=dcc[B];
	if(get(A,C)==get(A,B)+get(B,C))
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}
2023/9/2 22:09
加载中...