网站建设费用取得专票会计分录,网站通常用什么编程做,西昌规划和建设局网站,宁波软件开发公司排名problem
洛谷链接
题意#xff1a;给定 mmm 条形如 (u,v)(u,v)(u,v) 的限制#xff0c;要求 au,ava_u,a_vau,av 的相对大小关系与 bu,bvb_u,b_vbu,bv 相同。
且尽可能减少 aibia_ib_iaibi 的数量#xff0c;输出 a,ba,ba,b 两个排列。
solution
我们考虑将…problem
洛谷链接
题意给定 mmm 条形如 (u,v)(u,v)(u,v) 的限制要求 au,ava_u,a_vau,av 的相对大小关系与 bu,bvb_u,b_vbu,bv 相同。
且尽可能减少 aibia_ib_iaibi 的数量输出 a,ba,ba,b 两个排列。
solution
我们考虑将每条 (u,v)(u,v)(u,v) 限制转化成图 GGG 中的一条边。
如果某个点 iii 的边数 n−1n-1n−1则一定有 aibia_ib_iaibi。nnn 为当前剩余点的数量
边数等于点数减一这说明点 iii 与其它所有点都有一定的要求假设要求 bibkb_ib_kbibk 的 kkk 有 xxx 个则 aiak′a_ia_kaiak′ 的 k′kk′ 也等于 xxx。
这种确定的点直接按死不参与后面的讨论了。
那么到这里就剩下了一堆边数 n−1n-1n−1 的点了。
反转边的定义GˉE−G\bar{G}E-GGˉE−G如果 (u,v)(u,v)(u,v) 在 Gˉ\bar{G}Gˉ 为一条边当且仅当 (u,v)(u,v)(u,v) 原来是没有限制的。
这些点都是没有满边的所以一定会跟至少一个其它点连边的。
Gˉ\bar{G}Gˉ 形成的是一个生成树森林没有必要多连边形成图独立是传递的所以 Gˉ\bar{G}Gˉ 是多样的。
现在连边的两个点之间的选择是互不干涉的。
考虑一个特殊的情况——两层的菊花图。有一个非常简单的构造。
假设菊花图的根为 uuu所有叶子依次为 v1,v2,...,vxv_1,v_2,...,v_xv1,v2,...,vx。
对于 aaa 序列aul,av1l1,...,avx−1lx−1,avxlxa_ul,a_{v_1}l1,...,a_{v_{x-1}}lx-1,a_{v_x}lxaul,av1l1,...,avx−1lx−1,avxlx。
对于 bbb 序列bul1,bv1l2,...,bvx−1lx,bxvlb_ul1,b_{v_1}l2,...,b_{v_{x-1}}lx,b_{x_v}lbul1,bv1l2,...,bvx−1lx,bxvl。
用同样的数字区间 [l,lx][l,lx][l,lx] 填写了 a,ba,ba,b 同样的点集且打了个等差 111。
这样子内部反正是没有限制不用管数字间的大小也没有产生多余的 aibia_ib_iaibi 情况数。
而与外部部分因为都是用的连续段数字相对关系也是满足的。
例如有个点 ttt 与内部点有相对大小关系的限制内部用的是 [l,lx][l,lx][l,lx] ttt 所在点无论是 [l′,l)/(lx,r′][l,l)/(lx,r][l′,l)/(lx,r′]a,ba,ba,b 都是一致的。要么都小于最小值要么都大于最大值。
将 Gˉ\bar{G}Gˉ 中一些边断掉是不会出错的因为这反而相当于外加了一些限制。
所以我们可以就将 Gˉ\bar{G}Gˉ 直接断成若干个两层菊花图。
换言之最后的答案最少个数可以通过调整构造变成最开始确定的点的数量。
有很多种裂成不同菊花图的方法下面是官方做法
枚举未分配的节点 uuu。 如果 uuu 有临边点 vvv 未分配将 uuu 和所有未分配的 vvv 一起构成一个新的菊花图并以 uuu 为根。 否则说明 uuu 的所有邻居均已有过分配的菊花图。随便选一个邻居 vvv。 如果 vvv 所在的菊花图至少有 333 个点那么就可以把 vvv 割裂出来使得 u,vu,vu,v 成为新的菊花图。 注意vvv 此时不可能是其所在菊花图的根如果是那么 uuu 早就隶属与 vvv 为根的那个菊花图了。 否则说明 vvv 所在的菊花图只有两个点将 uuu 加入那个菊花图并将那个菊花图转变为以 vvv 为根即可。
Gˉ\bar{G}Gˉ 中可存在的边很多n2n^2n2 级别的但不一定是全都必须出现的。怎么快速求出想要的生成树
用两个 set 维护已出现在 Gˉ\bar{G}Gˉ 中的点和还未出现的点在 dfs-tree 的时候顺便加边构出生成树的边。
时间复杂度O((nm)logn)O((nm)\log n)O((nm)logn)。
code
#include bits/stdc.h
using namespace std;
#define maxn 500005
set pair int, int graph;
set int id, G[maxn], R[maxn];
int id1[maxn], id2[maxn], deg[maxn];void dfs( int u ) {id.erase( u );int v 0;while( 1 ) {auto it id.upper_bound( v );if( it id.end() ) break;v *it;if( G[u].find( v ) ! G[u].end() ) continue;R[u].insert( v );R[v].insert( u );dfs( v );}
}int main() {int T, n, m;scanf( %d, T );while( T -- ) {scanf( %d %d, n, m );for( int i 1;i n;i ) G[i].clear(), R[i].clear();id.clear(); for( int i 1;i n;i ) id.insert( i );for( int i 1, u, v;i m;i ) {scanf( %d %d, u, v );G[u].insert( v );G[v].insert( u );}while( id.size() ) dfs( * id.begin() );int num n;for( int i 1;i n;i ) {deg[i] R[i].size();if( deg[i] ) graph.insert( make_pair( deg[i], i ) );else id1[i] id2[i] num --;}int l 0, r 0, u;while( graph.size() ) {u graph.begin() - second;u *R[u].begin();graph.erase( make_pair( deg[u], u ) );vector int scc;for( int v : R[u] ) {graph.erase( make_pair( deg[v], v ) );if( deg[v] 1 ) scc.push_back( v );else graph.insert( make_pair( -- deg[v], v ) ), R[v].erase( u );}id1[u] l; for( int i : scc ) id1[i] l, id2[i] r; id2[u] r;}for( int i 1;i n;i ) printf( %d , id1[i] ); puts();for( int i 1;i n;i ) printf( %d , id2[i] ); puts();}return 0;
}
