三元环是什么？
三元环是%5C%26E%3D(A%20B%2C%20B%20C%2C%20C%20A)&preview=true)
求无向图的三元环有两种方法：
做法1：
①统计每个点的度数 ②入度$sqrt(m)$的分为第二类 ③对于第一类，暴力每个点，然后暴力这个点的任意两条边，再判断这两条边的另一个端点是否连接
因为m条边最多每条边遍历一次，然后暴力的点的入度，所以复杂度约为
④对于第二类，直接暴力任意三个点，判断这三个点是否构成环，因为这一类点的个数不会超过$sqrt(m)个，所以复杂度约为$$O(sqrt(m)^3)=O(msqrt(m))$ ⑤判断两个点是否连接可以用set，map和Hash都行,根据具体情况而行
这种做法建的是双向边，常数很大
#include
using namespace std;
const int N=1e6+5;
int n,m,x,y,z,ans,du[N],vis[N];
vectora,b,g[N];
mapmp[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
du[x]++;
du[y]++;
mp[x][y]=1;
mp[y][x]=1;
}
for(int i=1;i<=n;i++)
if(du[i]<=sqrt(m))a.push_back(i);
else b.push_back(i);
for(int i=0;i<a.size();i++)
{
x=a[i];
vis[x]=true;
for(int j=0;j<g[x].size();j++)
{
y=g[x][j];
if(vis[j])continue;
for(int k=j+1;k<g[x].size();k++)
{
z=g[x][k];
if(!vis[z]&&mp[y].count(z))ans++;
}
}
}
for(int i=0;i<b.size();i++)
{
for(int j=i+1;j<b.size();j++)
{
x=b[i];y=b[j];
if(mp[x].count(y)==0)continue;
for(int k=j+1;k<b.size();k++)
{
z=b[k];
if(mp[x].count(z)&&mp[y].count(z))ans++;
}
}
}
cout<<ans;
return 0;
} 更优的做法2:
建有向边 复杂度为$O(msqrt(n))$ 对所有边按照两端点的度数定向，度数小的往度数大的走，度数相同则按编号(值)小到大走，这样定向后
可以保证是个有向无环图。
为什么呢，要想定向存在环，则这个环上的点度数必须相同，由于保证了编号从小到大走,所以是不可能存在
环的。
这样定向同时还保证了每个点的出度不超过$sqrt(n)$，乍一眼看觉得应该是$sqrt(m)$的，仔细一想确实比这个
低，不过不知道怎么证。
#include
#define P pair
using namespace std;
const int N=5e5+5;
vector >G[N];
int n,m,Sz,u,v,X[N],Y[N],pos[N],vis[N],du[N];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
Sz=sqrt(m);
for(int i=1;i<=n;i++)
{
vis[i]=du[i]=pos[i]=0;
G[i].clear();
}
for(int i=0;i<m;i++)
{
scanf("%d%d",&X[i],&Y[i]);
du[X[i]]++;
du[Y[i]]++;
}
for(int i=0;i<m;i++)
{
if(du[X[i]]<du[Y[i]])G[X[i]].push_back(make_pair(Y[i],i));
else if(du[Y[i]]<du[X[i]])G[Y[i]].push_back(P(X[i],i));
else{
if(X[i]<Y[i])G[X[i]].push_back(P(Y[i],i));
else G[Y[i]].push_back(P(X[i],i));
}
}
long long ans=0;
for(int i=0;i<m;i++)
{
u=X[i];v=Y[i];
for(int j=0;j<G[u].size();j++)
{
P xu=G[u][j];
int jia=xu.first;
pos[jia]=xu.second;
vis[jia]=i+1;
}
for(int j=0;j<G[v].size();j++)
{
P xu=G[v][j];
int jia=xu.first;
if(vis[jia]==i+1)ans++;
}
}
printf("%lld\n",ans);
}
return 0;
} 题目： Counting Stars
给一张n个点m条边的无向图，问有多少个
其中满足
&&
显然是由两个有公共边的三元环构成的
题解：
我们记录一下每条边能构成的三元环数，
为第i条边的三元环数
我们用做法二做这题：
#include
#define P pair
using namespace std;
const int N=5e5+5;
vector >G[N];
int n,m,Sz,u,v,X[N],Y[N],cnt[N],pos[N],vi[N],du[N];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
Sz=sqrt(m);
for(int i=1;i<=n;i++)
{
vi[i]=du[i]=pos[i]=0;
G[i].clear();
}
for(int i=0;i<m;i++)
{
scanf("%d%d",&X[i],&Y[i]);
du[X[i]]++;
du[Y[i]]++;
}
for(int i=0;i<m;i++)
{
cnt[i]=0;
if(du[X[i]]<du[Y[i]])G[X[i]].push_back(make_pair(Y[i],i));
else if(du[Y[i]]<du[X[i]])G[Y[i]].push_back(P(X[i],i));
else{
if(X[i]<Y[i])G[X[i]].push_back(P(Y[i],i));
else G[Y[i]].push_back(P(X[i],i));
}
}
long long ans=0;
for(int i=0;i<m;i++)
{
u=X[i];v=Y[i];
for(int j=0;j<G[u].size();j++)
{
P vp=G[u][j];
pos[vp.first]=vp.second;
vi[vp.first]=i+1;
}
for(int j=0;j<G[v].size();j++)
{
P vp=G[v][j];
int vv=vp.first;
if(vi[vv]==i+1)
{
cnt[i]++;
cnt[pos[vv]]++;
cnt[vp.second]++;
}
}
}
for(int i=0;i<m;i++)ans+=1ll*cnt[i]*(cnt[i]-1)/2;
printf("%lld\n",ans);
}
return 0;
} 题目: 3498: PA2009 Cakes
N个点m条边，每个点有一个点权a。
对于任意一个三元环(j，j，k)（i<j<k），它的贡献 为max(ai，aj，ak)
求所有三元环的贡献和。
N<100000，，m<250000。
题解：
按照值从大到小排序，用做法二找到环就把加上点i的值
#include
using namespace std;
const int N=1e6+5;
int n,m,rank[N],du[N],vis[N];
struct node{
int val,id;
}a[N];
vectorg[N];
mapmp[N];
char buf[1<<21],*p1=buf,*p2=buf;
inline int gc()
{
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int ret=0,f=0;
char c=gc();
while(!isdigit(c))
{
if(c=='-')f=1;
c=gc();
}
while(isdigit(c))
{
ret=ret*10+c-48;
c=gc();
}
if(f)return -ret;
return ret;
}
bool cmp(node a,node b)
{
return a.val>b.val;
}
int main()
{
freopen("xjh.in","r",stdin);
freopen("xjh.out","w",stdout);
n=read();m=read();
int size=sqrt(m);
for(int i=1;i<=n;i++)
{
a[i].val=read();
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)rank[a[i].id]=i;
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
if(rank[x]<rank[y])
{
g[x].push_back(y);
mp[x][y]=1;
du[x]++;
}
else{
g[y].push_back(x);
mp[y][x]=1;
du[y]++;
}
}
long long ans=0;
for(int i=1;i<=n;i++)
{
int x=a[i].id;
for(int j=0;j<g[x].size();j++)
vis[g[x][j]]=x;
for(int j=0;j<g[x].size();j++)
{
int y=g[x][j];
if(du[y]<=size)
{
for(int k=0;k<g[y].size();k++)
{
int z=g[y][k];
if(vis[z]==x)ans+=a[i].val;
}
}
else{
for(int k=0;k<g[x].size();k++)
{
int z=g[x][k];
if(mp[y].count(z))ans+=a[i].val;
}
}
}
}
cout<<ans;
} 题目:5407: girls
有一个图，你要选定三个点，保证三个点之间两两无互相连边，当点的时候，你获得的收益为
，求所有符合情况的收益和。
题解：
可以用容斥原理，即所有的情况−至少有一对有连边+至少有两对有连边−三对都有连边 。
1. 对于所有的情况，可以考虑每个点来算贡献
2. 对于至少有一对连边的情况，可以枚举一个点和它的连边，然后用前缀和计算处余下来的所有的点。
3. 对于至少有两对连边的情况，可以枚举中间那个于两个点都有连边的点，然后对于它连接的每一个点计算贡献
4. 对于至少有三对连边的情况，可以三元环怒搞
#include
using namespace std;
#define ll long long
const int N=1e6+5;
int n,m;
unsigned long long A,B,C,x,y,z,ans,xu[N],du[N],suma[N],sumb[N],sumc[N];
bool vis[N];
vectora,b,g[N];
mapmp[N];
signed main()
{
scanf("%d%d",&n,&m);
cin>>A>>B>>C;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
x++;y++;
du[x]++;du[y]++;
g[x].push_back(y);
g[y].push_back(x);
mp[x][y]=1;
mp[y][x]=1;
}
for(int i=1;i<=n;i++)sort(g[i].begin(),g[i].end());
for(int i=1;i<=n;i++)
{
ans+=A*(i-1)*((ll)(n-i-1)*(n-i)/2);
ans+=B*(i-1)*(i-1)*(n-i);
ans+=C*(i-1)*((ll)(i-1)*(i-2)/2);
}
for(int i=1;i<=n;i++)
{
suma[i]=suma[i-1]+(i-1)*A;
sumb[i]=sumb[i-1]+(i-1)*B;
sumc[i]=sumc[i-1]+(i-1)*C;
}
for(int i=1;i<=n;i++)
{
int siz=g[i].size()-1;
unsigned long long cnt0=0,cnt1=0;
for(int j=0;j<=siz;j++)
{
int v=g[i][j];
if(v<i)
{
cnt0++;
ans-=suma[v-1]+B*(v-1)*(v-1)+C*(i-1)*(v-1);
ans+=A*(v-1)*(siz-j)+B*(v-1)*j;
}
else{
cnt1++;
ans-=A*(i-1)*(n-v)+B*(v-1)*(n-v)+sumc[n]-sumc[v];
ans-=A*(i-1)*(v-i-1)+sumb[v-1]-sumb[i]+C*(v-1)*(v-i-1);
ans+=C*(v-1)*j+B*(v-1)*(siz-j);
}
}
ans+=A*(i-1)*(cnt1*(cnt1-1)/2)+B*(i-1)*cnt0*cnt1+C*(i-1)*cnt0*(cnt0-1)/2;
}
int size=sqrt(m);
for(int i=1;i<=n;i++)
if(du[i]<=size)a.push_back(i);
else b.push_back(i);
for(int i=0;i<a.size();i++)
{
x=a[i];
vis[x]=true;
for(int j=0;j<g[x].size();j++)
{
y=g[x][j];
if(vis[j])continue;
for(int k=j+1;k<g[x].size();k++)
{
z=g[x][k];
if(vis[z])continue;
if(mp[y].count(z))
{
xu[1]=x;xu[2]=y;xu[3]=z;
sort(xu+1,xu+3+1);
ans-=A*(xu[1]-1)+B*(xu[2]-1)+C*(xu[3]-1);
}
}
}
}
for(int i=0;i<b.size();i++)
{
for(int j=i+1;j<b.size();j++)
{
x=b[i];y=b[j];
if(mp[x].count(y)==0)continue;
for(int k=j+1;k<b.size();k++)
{
z=b[k];
if(mp[x].count(z)&&mp[y].count(z))
{
xu[1]=x;xu[2]=y;xu[3]=z;
sort(xu+1,xu+3+1);
ans-=A*(xu[1]-1)+B*(xu[2]-1)+C*(xu[3]-1);
}
}
}
}
cout<<ans;
return 0;
}
/*
4 3
2 3 4
0 1
1 2
2 0
*/ 有向图的三元环
有向图的三元环和无向图的不一样，一般是用bitset做。
时间复杂度：
题目:CF117C
一个tournament是一个没有自环的有向图，同时，每两个点之间有一条边连接。这就是说，对于两个点u，v（u≠v），有一条从u到v的边或一条从v到u的边。
给你一个tournament，请找出一个长度为3的环。
题解：
都已每个点都用bitset记录他的入点，出点。
#include
using namespace std;
const int N=5005;
int n,x;
bitsetxu,ru[N],chu[N];
inline int read()
{
int res=0;
char c;
c=getchar();
while(!isdigit(c))c=getchar();
res=c-48;
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
x=read();
if(x==1)
{
ru[i][j]=1;
chu[j][i]=1;
}
}
for(int i=n;i;i--)
for(int j=n;j;j--)
if(i!=j&&ru[i][j]==1)
{
xu=chu[i]&ru[j];
if(xu.count()==0)continue;
printf("%d %d %d",i,j,xu._Find_first());
return 0;
}
cout<<-1;
} 
京公网安备 11010502036488号