BZOJ 3498: PA2009 Cakes

Description

\(n\)个点\(m\)条边,求所有三元环,一个三元环的贡献为三个点中权值最大的点.\(n\leqslant 1\times 10^5,n\leqslant 2.5\times 10^5\)

Solution

分类讨论.

只从权值大的点连向权值小的点,因为可能权值相同,顺序需要确定下来.

枚举所有边.

如果一个点的度数小于等于\(\sqrt m\)那么枚举所有的点,看看他和另一个点有没有连边,直接用map存一下...

如果度数大于\(\sqrt m\)那么枚举另一个点的所有相邻的点,如果另一个点度数大于\(\sqrt m\),那么这种情况最多有\(\sqrt m\)个...

总复杂度\(O(m\sqrt m)\)

Code

/**************************************************************
    Problem: 3498
    User: BeiYu
    Language: C++
    Result: Accepted
    Time:5376 ms
    Memory:18248 kb
****************************************************************/
 
#include 
using namespace std;
 
#define uor(i,j,k) for(int i=j;i<=(int)k;i++)
#define uep(i,j,k) for(int i=j;i<(int)k;i++) 
 
typedef long long ll;
const int N = 100050;
inline int in(int x=0,char s=getchar()) { while(s>'9'||s<'0')s=getchar();
    while(s>='0'&&s<='9')x=x*10+s-'0',s=getchar();return x; }
 
int n,m,B;ll ans=0;
int a[N],de[N],du[N],id[N],rk[N];
vector g[N];
map mp[N];
 
int cmp(const int &x,const int &y) { return a[x]B) uep(k,0,g[u].size()) ans+=mp[v][g[u][k]]?a[u]:0;
            else uep(k,0,g[v].size()) ans+=de[g[v][k]]==i?a[u]:0;
            mp[u][v]=1;
        }
    }return printf("%lld\n",ans),0;
}