好的证明复杂度是：

对于度数大于根号的点，最多根号个。称为大点。

度数小于根号的点，称为小点。

对于小点，边怎么定向不关心。之后度数最多根号个

对于大点，和小点的边一定是被小点指过来，只可能保留指向大点的出边。之后度数最多根号个。

复杂度本质是考虑每个点会被二次枚举多少次。也就是入边个数。

入边个数总共是m，每个点度数小于根号m

所以总复杂度是msqrt(m)

 

 

挺暴力的做法，

依靠对三元环无向边的定向，使得暴力枚举的复杂度其实是O(msqrt(m))

一些挺复杂的图的东西有时候可以根据度数分块考虑来优化暴力

但是这个做法巧妙之处按照度数定向，是可以通过度数的大小证明复杂度。。

 

例题：

PA2009 Cakes

#include
       
        #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=100000+5;int n,m;int a[N];struct node{    int nxt,to;}e[250000+5];int hd[N],cnt;void add(int x,int y){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    hd[x]=cnt;}int du[N];int b[250000+5][2];ll ans=0;int vis[N];int main(){    rd(n);rd(m);    for(reg i=1;i<=n;++i) rd(a[i]);    for(reg i=1;i<=m;++i){        rd(b[i][0]);rd(b[i][1]);        ++du[b[i][0]];++du[b[i][1]];    }    for(reg i=1;i<=m;++i){        int x=b[i][0],y=b[i][1];        if(du[x]
        
       

 

bzoj5407 girls

大力容斥

 

 

 

 

附疑问：

有向图三元环计数比较好的做法？

不知。（可以bitset）

 

有时候，在DAG枚举路径转移的时候，重新定向可以暴力枚举前驱或者后继，复杂度就有了保证

---

upda：2019.5.6

四元环计数？一共有三种情况

度数小的往度数大的连边，编号相同小到大。DAG

一个环三种情况

枚举u，走原边到v，再走新边到w，如果u<w，那么ans+=cnt[w],++cnt[w]

三种情况都会恰好被计算一次