ps和vscode做网站,综合性门户网站有哪些,建立公司网站的目的,网络广告一般是怎么收费正题
题目链接:https://www.luogu.com.cn/problem/CF603E 题目大意
开始时有nnn个点#xff0c;没有边。
依次加入mmm条带权的边#xff0c;每次加入后询问是否存在一个边集#xff0c;满足每个点的度数均为奇数#xff0c;求使得这个边集的最大权值最小。 1≤n≤105,1≤…正题
题目链接:https://www.luogu.com.cn/problem/CF603E 题目大意
开始时有nnn个点没有边。
依次加入mmm条带权的边每次加入后询问是否存在一个边集满足每个点的度数均为奇数求使得这个边集的最大权值最小。
1≤n≤105,1≤m≤3×1051\leq n\leq 10^5,1\leq m\leq 3\times 10^51≤n≤105,1≤m≤3×105 解题思路
首先考虑存在这个边集的条件可以证明存在满足条件的边集的充要条件是联通块的大小都是偶数。 必要性对于一个联通块因为每条边都会贡献偶数个度数而如果这个连通块是奇数个点那么如果合法的总度数就是 奇数×奇数奇数 显然不可能是偶数所以不存在这种情况。 充分性如果存在一个点的度数为奇数那么这个联通快里也至少有一个点的度数是奇数我们顺路删掉这两个点路径上的边就可以调整到合法情况。
而我们能连边就连边肯定是最优的因为不存在一种连边会使得奇数连通块数变多。
然后考虑用CDQ分治解决这题注意到答案肯定是单调不升的我们的流程是记录目前区间[l,r][l,r][l,r]的答案区间{L,R}\{L,R\}{L,R}。
先计算出ansmidans_{mid}ansmid那么此时我们就可以分为[l,mid−1]{ansmid,R}[l,mid-1]\{ans_{mid},R\}[l,mid−1]{ansmid,R}和[mid1,r]{L,ansmid}[mid1,r]\{L,ans_{mid}\}[mid1,r]{L,ansmid}
此时两个区间都被分开这提示我们暴力枚举这些区间就是正常分治的复杂度。
那么做法就很显然了我们算出ansmidans_{mid}ansmid后左右两边递归处理用可撤销并查集处理。
时间复杂度O(mlogmlogn)O(m\log m\log n)O(mlogmlogn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N3e510;
struct node{int x,y,w,id;
}a[N],b[N];
struct clnode{int x,y,siz,dep;
}cl[N];
int n,m,sum,clt,fa[N],siz[N],dep[N];
int ans[N],rk[N];
int find(int x)
{return (fa[x]x)?x:find(fa[x]);}
void unionn(int x,int y){xfind(x);yfind(y);if(xy)return;if(dep[x]dep[y])swap(x,y);cl[clt](clnode){x,y,siz[y],dep[y]};sum-(siz[x]1)(siz[y]1);fa[x]y;siz[y]siz[x];dep[y]max(dep[y],dep[x]1);
}
void clearto(int d){while(cltd){int xcl[clt].x,ycl[clt].y;siz[y]cl[clt].siz;dep[y]cl[clt].dep;sum(siz[x]1)(siz[y]1);fa[x]x;clt--;}return;
}
void cdq(int l,int r,int L,int R){if(lr)return;int mid(lr)1,nowclt;for(int il;imid;i)if(rk[i]L)unionn(a[i].x,a[i].y);int mowclt;for(int iL;iR;i){if(b[i].idmid)unionn(b[i].x,b[i].y);if(!sum){ans[mid]i;break;}}if(!ans[mid]){clearto(mow);cdq(mid1,r,L,R);return;}clearto(mow);cdq(mid1,r,L,ans[mid]);clearto(now);for(int iL;ians[mid];i)if(b[i].idl)unionn(b[i].x,b[i].y);cdq(l,mid-1,ans[mid],R);clearto(now);return;
}
bool cmp(node x,node y)
{return x.wy.w;}
int main()
{scanf(%d%d,n,m);sumn/2;if(n1){for(int i1;im;i)puts(-1);return 0;}for(int i1;in;i)fa[i]i,siz[i]1;for(int i1;im;i){scanf(%d%d%d,a[i].x,a[i].y,a[i].w);a[i].idi;b[i]a[i];}sort(b1,b1m,cmp);for(int i1;im;i)rk[b[i].id]i;cdq(1,m,1,m);for(int i1;im;i)if(!ans[i])puts(-1);else printf(%d\n,b[ans[i]].w);return 0;
}
