php网站修改主页内容,怎么做网站浏览量分析,四川建设网官网入口,山东建设监理协会网站无法登录正题
题目链接:https://www.luogu.com.cn/problem/P7323 题目大意
给出nnn个点的一张有向图。每个边(u,v,w)(u,v,w)(u,v,w)表示u−vu-vu−v有一个类型www的左括号边#xff0c;v−uv-uv−u有一个类型www的右括号边。
求图中有多少点对满足它们之间…正题
题目链接:https://www.luogu.com.cn/problem/P7323 题目大意
给出nnn个点的一张有向图。每个边(u,v,w)(u,v,w)(u,v,w)表示u−vu-vu−v有一个类型www的左括号边v−uv-uv−u有一个类型www的右括号边。
求图中有多少点对满足它们之间有一条合法的括号序列路径
1≤n≤3×105,1≤m≤6×105,1≤k≤n1\leq n\leq 3\times 10^5,1\leq m\leq 6\times 10^5,1\leq k\leq n1≤n≤3×105,1≤m≤6×105,1≤k≤n 解题思路
一个显然的结论是如果两个点之间有合法路径那么连一条边的话那么最后出来的是一个团。
因为f(u,v)1⇒f(v,u)1f(u,v)1\Rightarrow f(v,u)1f(u,v)1⇒f(v,u)1路径翻转f(u,v)f(v,z)1⇒f(u,z)1f(u,v)f(v,z)1\Rightarrow f(u,z)1f(u,v)f(v,z)1⇒f(u,z)1路径拼接。
考虑怎么求出这些团。假设我们现在有一个团xxx它连接向团外有两条类型一样的边那么就代表我们可以把这两条边连接的节点或者团合并入这个团中。
然后合并的时候我们因为又要处理类型一样的边所以我们用启发式合并枚举小的那个暴力丢进大的里面就好了。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n)用线段树合并可以做到O(nlogn)O(n\log n)O(nlogn)也许 code
#includecstdio
#includecstring
#includequeue
#includemap
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N3e510;
int n,m,k,fa[N],cnt[N];
long long ans;
queuepairint,int q;
mapint,int G[N];
int find(int x)
{return (fa[x]x)?x:(fa[x]find(fa[x]));}
mapint,int::iterator it;
int main()
{scanf(%d%d%d,n,m,k);for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);swap(x,y);if(G[x][w])q.push(mp(G[x][w],y));else G[x][w]y;}for(int i1;in;i)fa[i]i;while(!q.empty()){int xq.front().first,yq.front().second;xfind(x);yfind(y);q.pop();if(xy)continue;if(G[x].size()G[y].size())swap(x,y);for(itG[y].begin();it!G[y].end();it){int wit-first,zit-second;if(G[x][w])q.push(mp(G[x][w],z));else G[x][w]z;}fa[y]x;}for(int i1;in;i)cnt[find(i)];for(int i1;in;i)ans1ll*cnt[i]*(cnt[i]-1)/2ll;printf(%lld\n,ans);return 0;
}
