首页 > 其他 > 详细

bzoj2916: [Poi1997]Monochromatic Triangles 思路

时间:2019-08-24 21:21:22      阅读:99      评论:0      收藏:0      [点我收藏+]

bzoj2916: [Poi1997]Monochromatic Triangles

链接

bzoj

思路

总方案\(C_{n}^{3}-异色三角形\)
异色三角形有个特点。
会出现两个点有两条不同色的边。
然后统计就行了。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int _=5e3+7;
int n,m,a[_];
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;++i) {
        scanf("%d%d",&u,&v);
        a[u]++,a[v]++;
    }
    ll tot=0,ans=1LL*n*(n-1)*(n-2)/6;
    for(int i=1;i<=n;++i) tot+=(n-a[i]-1)*a[i];
    ans-=tot/2;
    cout<<ans<<"\n";
    return 0;
}

bzoj2916: [Poi1997]Monochromatic Triangles 思路

原文:https://www.cnblogs.com/dsrdsr/p/11405972.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!