# Soulist 的博客

—可惜当时年少

### 题解 P5292 【[HNOI2019]校园旅行】

posted on 2019-04-08 19:37:27 | under 图论 |

myy出的题真的好妙啊 $QAQ$

$HN-D2$ 全程没人切题欸。。。

while( !q.empty() ) {
Node u = q.front(); q.pop() ;
int Fr = u.from, To = u.to ;
for( int i = head[Fr]; i; i = e[i].to ) {
int v = e[i].to ;
for( int j = head[To]; j; j = e[j].to ) {
int v2 = e[j].to ;
if( w[v] != w[v2] || dis[v][v2] ) continue ;
dis[v][v2] = dis[v2][v] = 1, q.push((Node){ v, v2 }) ;
}
}
}


#include<bits/stdc++.h>
using namespace std;
char cc = getchar(); int cn = 0;
while(cc < '0' || cc > '9') cc = getchar();
while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
return cn;
}
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
const int M = 1e6 + 5 ;
const int N = 5000 + 5;
struct E {
int to, next ;
} e[M * 2];
struct S {
int from, to ;
} s[M * 2];
int n, m, Q, head[N], cnt, w[N], dis[N][N], fa[N][2], col[N], sd[N], book[N];
char ss[N] ;
queue< S> q ;
void add( int x, int y ) {
}
int abc( int x ) { //绝对值
return ( x > 0 ) ? x : -x ;
}
int find( int x, int node ) {
if( fa[x][node] == x ) return x ;
return fa[x][node] = find(fa[x][node], node) ;
}
void dfs( int x, int c ) {
col[x] = c ;
Next( i, x ) {
int v = e[i].to ;
if( !col[v] ) dfs( v, -c ) ;
else if( col[v] == col[x] ) sd[abc(c)] = 1 ;
}
}
void init() {
rep( i, 1, n ) if( !col[i] ) dfs( i, i ) ;  //二分图染色

rep( i, 1, m ) {
int Fr = s[i].from, To = s[i].to ;
if( w[Fr] != w[To] ) {
int u = find( Fr, 1 ), v = find( To, 1 ) ;
if( u == v ) continue ;
add( Fr, To ), fa[u][1] = v ;
}
else {
int u = find(Fr, 0), v = find(To, 0) ;
if( u == v ) continue ;
add( Fr, To ), fa[u][0] = v ;
q.push((S){ Fr, To }), dis[Fr][To] = dis[To][Fr] = 1 ;
}
}
rep( i, 1, n ) {
int cc = abc(col[i]) ;
if( sd[cc] && ( book[cc] == 0 ) ) add( cc, cc ), book[cc] = 1 ; //自环
}
}
void spfa() { //spfa求解两个点是否可达
while( !q.empty() ) {
S u = q.front(); q.pop() ;
int Fr = u.from, To = u.to ;
Next( i, Fr ) {
int v = e[i].to ;
Next( j, To ) {
int v2 = e[j].to ;
if( w[v] != w[v2] || dis[v][v2] ) continue ;
dis[v][v2] = dis[v2][v] = 1, q.push((S){v, v2}) ;
}
}
}
}
void output() { //输出文件
int x, y ;
rep( i, 1, Q ) {
if( dis[x][y] ) puts("YES") ;
else puts("NO") ;
}
}
signed main()
{
}