BZOJ2916: [Poi1997]Monochromatic Triangles【三元环】

2916: [Poi1997]Monochromatic Triangles

【题目描述】

传送门

【题解】

这题第一眼就是三元环,交了一发发现跑的比他们慢多了,结果这题不需要三元环,直接计算就可以了。

代码如下

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=1005,MAXE=250005;
int n,m,K,Ans,D[MAXN];bool vis[MAXN][MAXN];
struct xcw{
    int tot,lnk[MAXN],nxt[MAXE<<1],son[MAXE<<1];
    void clean(){memset(lnk,0,sizeof(lnk));tot=0;}
    void Add(int x,int y){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;}
}E;
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=ret*10+ch-48;
    return f?ret:-ret;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i){
        int x=read(),y=read();vis[x][y]=vis[y][x]=1;
    }
    for(int i=1;i<=n;++i)
    for(int j=n;j>=i+1;--j) if(vis[i][j]) E.Add(i,j),E.Add(j,i),D[i]++,D[j]++;
    K=sqrt(m);
    for(int i=1;i<=n;++i)
    for(int j=E.lnk[i];j;j=E.nxt[j])
    if(E.son[j]>i){
        int x=i,y=E.son[j];
        if(D[x]>K){
            for(int k=E.lnk[y];k;k=E.nxt[k])
            if(vis[x][E.son[k]]&&E.son[k]>y) Ans++;
        }else{
            for(int k=E.nxt[j];k;k=E.nxt[k])
            if(vis[y][E.son[k]]&&E.son[k]>y) Ans++;
        }
    }

    E.clean();memset(D,0,sizeof(D));
    for(int i=1;i<=n;++i)
    for(int j=n;j>=i+1;--j) if(!vis[i][j]) E.Add(i,j),E.Add(j,i),D[i]++,D[j]++;
    K=sqrt(n*(n-1)/2-m);
    for(int i=1;i<=n;i++)
    for(int j=E.lnk[i];j;j=E.nxt[j])
    if(E.son[j]>i){
        int x=i,y=E.son[j];
        if(D[x]>K){
            for(int k=E.lnk[y];k;k=E.nxt[k])
            if(!vis[x][E.son[k]]&&E.son[k]>y) Ans++;
        }else{
            for(int k=E.nxt[j];k;k=E.nxt[k])
            if(!vis[y][E.son[k]]&&E.son[k]>y) Ans++;
        }
    }

    printf("%d\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部