大家好,又见面了,我是全栈君。
题意:求该死的菱形数目。直接枚举两端的点。平均意义每一个点连接20条边,用邻接表暴力计算中间节点数目,那么中间节点任选两个与两端可组成的菱形数目有r*(r-1)/2.
代码:
#include<iostream> #include<cstdio> #include<cmath> #include<map> #include<cstring> #include<algorithm> #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rev(i,a,b) for(int i=(a);i>=(b);i--) #define clr(a,x) memset(a,x,sizeof a) typedef long long LL; using namespace std; const int mod=1e9 +7; const int maxn=3005; const int maxm=30005; int first[maxn],nex[maxm],v[maxm],ecnt,g[maxn][maxn]; void add_(int a,int b) { v[ecnt]=b; nex[ecnt]=first[a]; first[a]=ecnt++; } int main() { int n,m,x,y; while(~scanf("%d%d",&n,&m)) { memset(first,-1,sizeof first);ecnt=0; memset(g,0,sizeof g); for(int i=0;i<m;i++) scanf("%d%d",&x,&y),add_(x,y),g[x][y]=1; int ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) if(i!=j){ int r=0; for(int e=first[i];~e;e=nex[e]) if(g[v[e]][j])r++; ans+=r*(r-1)/2; } } printf("%d\n",ans); } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115961.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...