【BZOJ2916】[Poi1997]Monochromatic Triangles

2015.08.17 20:24 Mon | 38次阅读 | 旧日oi | 固定链接 | 源码

Description

       空间中有n个点,任意3个点不共线。每两个点用红线或者蓝线连接,如果一个三角形的三边颜色相同,那么称为同色三角形。给你一组数据,计算同色三角形的总数。

Input

第一行是整数n, 3 <= n <= 1000,点的个数。
第二行是整数m, 0 <= m <= 250000,红线数目。
接下来的m行,每行两个数p和k,1 <= p < k <= n。表示一条红线的两个端点。

题解

分开处理,枚举每条红边,再遍历两个端点的相邻点,然后统计答案,然后建反图,再搞一遍。
我比rank倒第二慢10倍!

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 1000005
struct edge{
    int to,next;
}e[N];
int h[1005],tp;
void ae(int u,int v)
{
    e[++tp].to=v;e[tp].next=h[u];h[u]=tp;
}
int u[N],v[N],n,m,ans;
int vis[1005],mp[1005][1005];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) 
    {
        scanf("%d%d",&u[i],&v[i]);
        ae(u[i],v[i]);ae(v[i],u[i]);
        mp[u[i]][v[i]]=mp[v[i]][u[i]]=1;
    }
    for(int k=1;k<=m;k++)
    {
        for(int i=h[u[k]];e[i].to;i=e[i].next) vis[e[i].to]=k;
        for(int i=h[v[k]];e[i].to;i=e[i].next) 
        if(vis[e[i].to]==k) vis[e[i].to]=0,ans++;
    }
    memset(h,0,sizeof(h));tp=0;
    memset(vis,0,sizeof(vis));
    int cnt=0;
    for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)
    if(!mp[i][j]) 
    {
        ae(i,j);ae(j,i);
        u[++cnt]=i;v[cnt]=j;
    }
    for(int k=1;k<=cnt;k++)
    {
        for(int i=h[u[k]];e[i].to;i=e[i].next) vis[e[i].to]=k;
        for(int i=h[v[k]];e[i].to;i=e[i].next) 
        if(vis[e[i].to]==k) vis[e[i].to]=0,ans++;
    }
    cout<<ans/3<<endl;
}```