网站建设与网页设计期末考试,网站后台公告id修改,网站备案查询你,wordpress右侧居中正题
题目链接:https://www.luogu.com.cn/problem/CF1444C 题目大意
给出nnn个点mmm条边的一张图#xff0c;总共kkk个颜色#xff0c;每个点有一个颜色。
询问有多少无序颜色对(x,y)(x,y)(x,y)满足x≠yx\neq yxy且颜色为xxx或yyy的点构成的生成子图是一个二分图。 1≤…正题
题目链接:https://www.luogu.com.cn/problem/CF1444C 题目大意
给出nnn个点mmm条边的一张图总共kkk个颜色每个点有一个颜色。
询问有多少无序颜色对(x,y)(x,y)(x,y)满足x≠yx\neq yxy且颜色为xxx或yyy的点构成的生成子图是一个二分图。
1≤n,m,k≤5×1051\leq n,m,k\leq 5\times 10^51≤n,m,k≤5×105 解题思路
首先把单独颜色就有奇环的颜色给去掉。
然后会发现实际上我们不需要对于k×(k−1)2\frac{k\times (k-1)}{2}2k×(k−1)种情况都判断因为只有mmm条边我们只需要边连接的不同颜色判断即可这样的次数是O(m)O(m)O(m)级别的。
然后先连好同色的用个可撤销扩展域的并查集每种颜色对暴力判断即可。
时间复杂度O(mlogn)O(m\log n)O(mlogn) code
#includecstdio
#includecstring
#includealgorithm
#includemap
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N1e610;
struct edge{int x,y;pairint,int w;
}e[N];
struct cld{int x,y,fa,dep;
}cl[N];
int n,m,k,clt;bool flag,ban[N];
int c[N],ls[N],dep[N],fa[N];
bool cmp(edge x,edge y)
{return x.wy.w;}
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](cld){x,y,fa[y],dep[x]};fa[y]x;dep[x]max(dep[x],dep[y]1);
}
void remake(){while(clt){fa[cl[clt].y]cl[clt].fa;dep[cl[clt].x]cl[clt].dep;clt--;}return;
}
int main()
{scanf(%d%d%d,n,m,k);for(int i1;i2*n;i)fa[i]i,dep[i]1;for(int i1;in;i)scanf(%d,c[i]);for(int i1;im;i){scanf(%d%d,e[i].x,e[i].y);if(c[e[i].x]c[e[i].y]){unionn(e[i].x,e[i].yn);unionn(e[i].xn,e[i].y);if(find(e[i].x)find(e[i].y))k-!ban[c[e[i].x]],ban[c[e[i].x]]1;}e[i].wmp(c[e[i].x],c[e[i].y]);if(e[i].w.firste[i].w.second)swap(e[i].w.first,e[i].w.second);}sort(e1,e1m,cmp);long long ans1ll*k*(k-1)/2;for(int l1,r1;lm;lr1){while(e[r1].we[l].w)r;if(ban[e[l].w.first]||ban[e[l].w.second]||e[l].w.firste[l].w.second)continue;clt0;flag0;for(int il;ir;i){int xe[i].x,ye[i].y;if(find(x)find(y)){flag1;break;}unionn(x,yn);unionn(xn,y);}remake();ans-flag;}printf(%lld\n,ans);return 0;
}
