BZOJ 3498: PA2009 Cakes 一类经典的三元环计数问题

首先引入一个最常见的经典三元环问题。

BZOJ 3498: PA2009 Cakes 一类经典的三元环计数问题

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
vector <int> g[maxn], low, high;
map <int, int> mp[maxn];
int n, m, in[maxn], vis[maxn]; int main()
{
scanf("%d %d", &n,&m);
for(int i=1; i<=m; i++){
int x,y;
scanf("%d %d", &x,&y);
g[x].push_back(y);
g[y].push_back(x);
mp[x][y] = 1;
mp[y][x] = 1;
in[x]++;
in[y]++;
}
for(int i=1; i<=n; i++){
if(in[i]<=sqrt(m)) low.push_back(i);
else high.push_back(i);
}
int ans = 0;
memset(vis, false, sizeof(vis));
for(int i=0; i<low.size(); i++){
int x = low[i];
vis[x] = 1;
for(int j=0; j<g[x].size(); j++){
int y = g[x][j];
if(vis[y]) continue;
for(int k=j+1; k<g[x].size(); k++){
int z = g[x][k];
if(vis[z]) continue;
if(mp[y].count(z)) ans++;
}
}
}
for(int i=0; i<high.size(); i++){
for(int j=i+1; j<high.size(); j++){
int x, y, z;
x = high[i];
y = high[j];
if(mp[x].count(y)==0) continue;
for(int k=j+1; k<high.size(); k++){
z = high[k];
if(mp[y].count(z)&&mp[x].count(z)) ans++;
}
}
}
printf("%d\n", ans);
return 0;
}

BZOJ 3948

BZOJ 3498: PA2009 Cakes 一类经典的三元环计数问题

//BZOJ 3498
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
typedef long long LL;
struct node{
int val,id;
node(){}
node(int val,int id):val(val),id(id){}
bool operator<(const node &rhs)const{
return val>rhs.val;
}
}a[maxn];
vector <int> G[maxn];
map <int, int> mp[maxn];
int Rank[maxn], out[maxn], linker[maxn];
int n, m; int main()
{
scanf("%d %d", &n,&m);
for(int i=1; i<=n; i++){
scanf("%d", &a[i].val);
a[i].id = i;
}
sort(a+1, a+n+1);
for(int i=1; i<=n; i++) Rank[a[i].id] = i;
for(int i=1; i<=m; i++){
int x, y;
scanf("%d %d", &x,&y);
if(Rank[x]<Rank[y]){
G[x].push_back(y), out[x]++, mp[x][y]=1;
}else{
G[y].push_back(x), out[y]++, mp[y][x]=1;
}
}
LL ans = 0;
for(int i=1; i<=n; i++){
int x = a[i].id, y;
for(int j=0; j<G[x].size(); j++){
linker[G[x][j]] = x;
}
for(int j=0; j<G[x].size(); j++){
y = G[x][j];
if(out[y]>sqrt(m)+1){
for(int k=0; k<G[x].size(); k++){
int z = G[x][k];
if(mp[y].count(z)) ans += a[i].val;
}
}else{
for(int k=0; k<G[y].size(); k++){
int z = G[y][k];
if(linker[z] == x) ans += a[i].val;
}
}
}
}
printf("%lld\n", ans);
return 0;
}
上一篇:mysql之 日志体系(错误日志、查询日志、二进制日志、事务日志、中继日志)


下一篇:高可用集群搭建系列(一) 实现方案