做网站一定要用cms吗,iis5.1 发布网站,软件开发网站,做地暖工程的网站文章目录Portalparity[NOI2001] 食物链程序自动分析UVA11987 Almost Union-Find[SDOI2008] 洞穴勘测Portal
source
百度翻译简直就是个鬼…(((m -__-)m
离线
将边和询问按权值排序#xff0c;指针#xff0c;将所有权值不超过当前询问iii的边全加进去
答案路径自然是不连…
文章目录Portalparity[NOI2001] 食物链程序自动分析UVA11987 Almost Union-Find[SDOI2008] 洞穴勘测Portal
source
百度翻译简直就是个鬼…(((m -__-)m
离线
将边和询问按权值排序指针将所有权值不超过当前询问iii的边全加进去
答案路径自然是不连通的两点sizsizsiz之积
原本就联通的新加边不产生贡献
#include cstdio
#include iostream
#include algorithm
using namespace std;
#define maxn 10005
#define maxm 50005
#define int long long
struct node {int u, v, w;
}edge[maxm];
pair int, int query[maxn];
int n, m, Q, cnt;
int f[maxn], siz[maxn], ans[maxn];void makeset() {for( int i 1;i n;i ) f[i] i, siz[i] 1;
}int find( int x ) {return x f[x] ? x : f[x] find( f[x] );
}void merge( int u, int v ) {u find( u ), v find( v );if( u v ) return;else {f[v] u;cnt siz[u] * siz[v];siz[u] siz[v];}
}signed main() {while( ~ scanf( %lld %lld %lld, n, m, Q ) ) {cnt 0;for( int i 1;i m;i )scanf( %lld %lld %lld, edge[i].u, edge[i].v, edge[i].w );sort( edge 1, edge m 1, []( node x, node y ) { return x.w y.w; } );for( int i 1;i Q;i ) {scanf( %lld, query[i].first );query[i].second i;}sort( query 1, query Q 1 );makeset();int j 1;for( int i 1;i Q;i ) {while( j m edge[j].w query[i].first ) merge( edge[j].u, edge[j].v ), j ;ans[query[i].second] cnt;}for( int i 1;i Q;i )printf( %lld\n, ans[i] );}return 0;
}parity
source
一般判断是否矛盾的并查集肯定是带权并查集
将区间[l,r][l,r][l,r]的奇偶当作r→l−1r\rightarrow l-1r→l−1的权值
判断矛盾首先l−1,rl-1,rl−1,r要在同一个并查集然后看之间的权值是否与当前条件的奇偶矛盾
#include cstdio
#include algorithm
using namespace std;
#define maxn 10005
struct node {int l, r;char opt[10];
}query[maxn];
int n, m;
int x[maxn], f[maxn], sum[maxn];void makeset() {for( int i 0;i n;i )f[i] i, sum[i] 0;
}int find( int x ) {if( x f[x] ) return x;else {int fa find( f[x] );sum[x] ( sum[x] sum[f[x]] ) % 2;return f[x] fa;}
}int main() {next :while( scanf( %d, n ) ~ n ) {scanf( %d, m );n 0;for( int i 1;i m;i ) {scanf( %d %d %s, query[i].l, query[i].r, query[i].opt );x[ n] query[i].l;x[ n] query[i].r;}sort( x 1, x n 1 );n unique( x 1, x n 1 ) - x - 1;makeset();for( int i 1;i m;i ) {int l lower_bound( x 1, x n 1, query[i].l ) - x;int r lower_bound( x 1, x n 1, query[i].r ) - x;int t query[i].opt[0] o;if( l r ) swap( l, r );l --;int u find( l ), v find( r );if( u ^ v ) {f[v] u;sum[v] ( -sum[r] sum[l] t 2 ) % 2;}elseif( t )if( sum[l] sum[r] ) {printf( %d\n, i - 1 );goto next;} else;elseif( sum[l] ! sum[r] ) {printf( %d\n, i - 1 );goto next;} else;}printf( %d\n, m );}return 0;
}[NOI2001] 食物链
source
法一建虚点
因为题目的食物链是个三元环天然有我是 我的天敌的天敌 的天敌
用ininin集合表示iii能吃的i2ni2ni2n表示iii能被吃的
大力情况枚举讨论
#include cstdio
#define maxn 150005
int f[maxn];
int n, m, ans;void makeset() {for( int i 1;i n * 3;i )f[i] i;
}int find( int x ) {return x f[x] ? x : f[x] find( f[x] );
}void merge( int u, int v ) {u find( u ), v find( v );f[v] u;
}
/*
i: itself
in:i can eat them
i2*n:they can eat i
*/
int main() {scanf( %d %d, n, m );makeset();for( int i 1, d, x, y;i m;i ) {scanf( %d %d %d, d, x, y );if( x n || y n ) ans ;elseif( d 1 ) {if( find( x ) find( y n ) or find( x n ) find( y ) or find( x ) find( y n * 2 ) or find( x n * 2 ) find( y ) ) ans ;else merge( x, y ), merge( x n, y n ), merge( x n * 2, y n * 2 );}else {if( x y ) ans ;else if( find( x ) find( y ) or find( x ) find( y n ) or find( x n * 2 ) find( y ) )ans ;elsemerge( x, y n * 2 ), merge( x n, y ), merge( x n * 2, y n );}}printf( %d\n, ans );return 0;
}法二带权并查集 不在同一个并查集的u,vu,vu,v两点连向自己祖先的权值为sumu,sumvsum_u,sum_vsumu,sumv
如果现在将u,vu,vu,v合并并且是vvv合并到uuu那么就是fv→fuf_v\rightarrow f_ufv→fu
权值显然为valfv−sumvsumuwval_{f_v}-sum_vsum_uwvalfv−sumvsumuw 路径压缩的时候权值更新需要以前的直系父亲权值即可
回归本题将同类看作边权为000吃关系看成边权为111在(mod3)\pmod 3(mod3)意义下做
#include cstdio
#define maxn 50005
int n, k, ans;
int f[maxn], sum[maxn];void makeset() {for( int i 1;i n;i ) f[i] i;
}int find( int x ) {if( x f[x] ) return x;else {int fa f[x];f[x] find( f[x] );sum[x] ( sum[x] sum[fa] ) % 3;return f[x];}
}int main() {scanf( %d %d, n, k );makeset();for( int i 1, d, x, y;i k;i ) {scanf( %d %d %d, d, x, y );if( x n || y n ) ans ;else {int fx find( x ), fy find( y );if( d 1 )if( fx fy sum[x] ! sum[y] ) ans ;else if( fx ^ fy ) f[fx] fy, sum[fx] ( -sum[x] sum[y] 3 ) % 3;else;else {if( x y ) ans ;else if( fx fy )if( ( sum[x] - sum[y] 3 ) % 3 ! 1 ) ans ;else;else f[fx] fy, sum[fx] ( -sum[x] sum[y] 4 ) % 3;}}}printf( %d\n, ans );return 0;
}程序自动分析
source
离散先一股脑把所有相等的并查集到一起最后判断不等的两个数是否在同一个集合即可
luogu上面好几篇都是错的对拍直接挂掉这用脚造的数据诶
#include cstdio
#include algorithm
using namespace std;
#define maxn 4000005
struct node {int u, v, e;
}lim[maxn];
int T, n;
int f[maxn], x[maxn];void makeset() {for( int i 1;i ( n 2 );i ) f[i] i;
}int find( int x ) {return f[x] x ? x : f[x] find( f[x] );
}void merge( int u, int v ) {u find( u ), v find( v );f[v] u;
}int main() {scanf( %d, T );next :while( T -- ) {scanf( %d, n );makeset();int cnt 0;for( int i 1;i n;i ) {scanf( %d %d %d, lim[i].u, lim[i].v, lim[i].e );x[ cnt] lim[i].u, x[ cnt] lim[i].v;}sort( x 1, x cnt 1 );cnt unique( x 1, x cnt 1 ) - x - 1;for( int i 1;i n;i ) {int u lim[i].u, v lim[i].v, e lim[i].e;u lower_bound( x 1, x cnt 1, u ) - x;v lower_bound( x 1, x cnt 1, v ) - x;if( e ) merge( u, v );}for( int i 1;i n;i ) {int u lim[i].u, v lim[i].v, e lim[i].e;u lower_bound( x 1, x cnt 1, u ) - x;v lower_bound( x 1, x cnt 1, v ) - x;if( ! e find( u ) find( v ) ) {printf( NO\n );goto next;}}printf( YES\n );}return 0;
}UVA11987 Almost Union-Find
source
可删除并查集
建虚点
相当于套个盒子然后父子关系就是盒子上面的互相指代但是数就可以不存在盒子存在) #include cstdio
#define maxn 200005
int n, m;
int f[maxn], sum[maxn], siz[maxn];void makeset() {for( int i n 1;i ( n 1 );i ) f[i] i, sum[i] i - n, siz[i] 1;for( int i 1;i n;i ) f[i] i n;
}int find( int x ) {return x f[x] ? x : f[x] find( f[x] );
}int main() {while( ~ scanf( %d %d, n, m ) ) {makeset();for( int i 1, opt, p, q, u, v;i m;i ) {scanf( %d %d, opt, p );switch ( opt ) {case 1 : {scanf( %d, q );u find( p ), v find( q );if( u v ) continue; else;f[v] u, siz[u] siz[v], sum[u] sum[v];siz[v] sum[v] 0;break;}case 2 : {scanf( %d, q );u find( p ), v find( q );if( u v ) continue; else;f[p] v;sum[v] p, sum[u] - p;siz[u] --, siz[v] ;break;}case 3 : {u find( p );printf( %d %d\n, siz[u], sum[u] );break;}}}}return 0;
}[SDOI2008] 洞穴勘测
source
线段树可撤销并查集
每条边存在的时间是一个区间丢在线段树上最多logn\log nlogn个标记
然后dfs遍历到每个叶子节点判断这个iii是否有询问挂在上面再判断此刻已有边中两点是否联通
第一次经过点num\rm numnum就把挂在上面的边操作加入并查集先后顺序记录操作的边
等dfs回溯再次经过该点的时候就倒着把这些边的操作反着做从而起到抵消边的效果
#include map
#include cstdio
#include vector
#include iostream
using namespace std;
#define maxn 200005
#define Pair pair int, int
struct node {int u, v, w;node(){}node( int U, int V, int W ) {u U, v V, w W;}
}query[maxn];
vector Pair E[maxn 2];
map Pair, int mp;
int n, m, top;
int f[maxn], siz[maxn], ans[maxn];
Pair sta[maxn];void makeset() {for( int i 1;i n;i ) f[i] i, siz[i] 1;
}int find( int x ) {return x f[x] ? x : find( f[x] );
}void insert( int num, int l, int r, int L, int R, Pair t ) {if( r L or R l ) return;if( L l and r R ) {E[num].push_back( t );return;}int mid ( l r ) 1;insert( num 1, l, mid, L, R, t );insert( num 1 | 1, mid 1, r, L, R, t );
}void merge( int u, int v ) {u find( u ), v find( v );if( u ^ v ) {if( siz[u] siz[v] ) swap( u, v );sta[ top] make_pair( u, v );siz[u] siz[v], siz[v] ;f[v] u;}
}void Delete( int last ) {while( top last ) {Pair t sta[top --];siz[t.second] --;siz[t.first] - siz[t.second];f[t.second] t.second;}
}void dfs( int num, int l, int r ) {int now top;for( auto edge : E[num] )merge( edge.first, edge.second );if( l r ) {if( query[l].w ) {if( find( query[l].u ) find( query[l].v ) ) ans[l] 1;elseans[l] -1;}}else {int mid ( l r ) 1;dfs( num 1, l, mid );dfs( num 1 | 1, mid 1, r );}Delete( now );
}int main() {scanf( %d %d, n, m );makeset();char opt[10]; int u, v;for( int i 1;i m;i ) {scanf( %s %d %d, opt, u, v );if( u v ) swap( u, v );Pair t make_pair( u, v );switch ( opt[0] ) {case C : {mp[t] i;break;}case D : {insert( 1, 1, m, mp[t], i, t );mp.erase( t );break;}case Q : {query[i] node( u, v, 1 );break;}}}for( map Pair, int :: iterator it mp.begin();it ! mp.end();it )insert( 1, 1, m, it - second, m, it - first );dfs( 1, 1, m );for( int i 1;i m;i )if( ! ans[i] ) continue;else puts( ans[i] 0 ? Yes : No );return 0;
}#include cstdio
#include iostream
using namespace std;
#define maxn 300005
#define LL long long
struct node {int f, flag, son[2], sum, val;
}tree[maxn];
int n, m;
int st[maxn];void reverse ( int x ) {swap ( tree[x].son[0], tree[x].son[1] );tree[x].flag ^ 1;
}void update ( int x ) {tree[x].sum tree[tree[x].son[0]].sum tree[tree[x].son[1]].sum tree[x].val;
}void pushdown ( int x ) {if ( tree[x].flag ) {if ( tree[x].son[0] )reverse ( tree[x].son[0] );if ( tree[x].son[1] )reverse ( tree[x].son[1] );tree[x].flag 0;}
}bool isroot ( int x ) {return tree[tree[x].f].son[0] x || tree[tree[x].f].son[1] x;
}void rotate ( int x ) { int fa tree[x].f; int Gfa tree[fa].f;int k ( tree[fa].son[1] x );if ( isroot ( fa ) )tree[Gfa].son[tree[Gfa].son[1] fa] x;tree[x].f Gfa; tree[fa].son[k] tree[x].son[k ^ 1];if ( tree[x].son[k ^ 1] )tree[tree[x].son[k ^ 1]].f fa;tree[x].son[k ^ 1] fa;tree[fa].f x;update ( fa );update ( x );
}void splay ( int x ) {int Top 0, y x;st[ Top] y;while ( isroot ( y ) )st[ Top] y tree[y].f;while ( Top )pushdown ( st[Top -- ] );while ( isroot ( x ) ) {int fa tree[x].f, Gfa tree[fa].f;if ( isroot ( fa ) )( ( tree[Gfa].son[0] fa ) ^ ( tree[fa].son[0] x ) ) ? rotate ( x ) : rotate ( fa );rotate ( x );}
}void access ( int x ) {for ( int son 0;x;son x, x tree[x].f ) {splay ( x );tree[x].son[1] son;update ( x );}
}void MakeRoot ( int x ) {access ( x );splay ( x );reverse ( x );
}int FindRoot ( int x ) {access ( x );splay ( x );while ( tree[x].son[0] ) {pushdown ( x );x tree[x].son[0];}splay ( x );return x;
}void split ( int x, int y ) { MakeRoot ( x );access ( y );splay ( y );
}bool link ( int x, int y ) {MakeRoot ( x );if ( FindRoot ( y ) x )return 0;tree[x].f y;return 1;
}void cut ( int x, int y ) { MakeRoot ( x );if ( FindRoot ( y ) ! x || tree[y].f ! x || tree[y].son[0] )return;tree[y].f tree[x].son[1] 0;update ( x );
}int main() {scanf ( %d %d, n, m );int x, y;char opt[15];for ( int i 1;i m;i ) {scanf ( %s %d %d, opt, x, y );switch ( opt[0] ) {case Q : {MakeRoot ( x );if ( FindRoot ( y ) x )printf ( Yes\n );elseprintf ( No\n );break;}case C : link ( x, y ); break;case D : cut ( x, y ); break;}}return 0;
}
