Description
有 \(n\) 个人 , \(m\) 对人有冲突 , 你要从这 \(n\) 个人中选出三个人成为一组 , 使得同一组的人不存在一对有冲突
题面
Solution
容斥
答案=总方案-至少有一个与 \(i\) 相连的+至少有 \(2\) 个与 \(i\) 相连的-\(i,j,k\) 都互相连接的方案数
前面三种都比较好求,讨论一下 \(i,j,k\) 的偏序关系就行了
关于第三种情况,需要 \(O(m^2)\) 枚举 , 只需要枚举度数较小的两个,最大的那个直接判断是否与前面两个相连就好了
这样做最坏复杂度是 \(O(n*\sqrt{n})\) 的 ,\(CF\) 的 \(Tutorial\) 有证明.
#include<bits/stdc++.h>
using namespace std;
template<class T>void gi(T &x){
int f;char c;
for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;
}
typedef unsigned long long ll;
const int N=2e5+10;
int n,m,head[N],nxt[N*4],to[N*4],num=0,Head[N],b[N],a[N];
ll s[N],ss[N],A,B,C,ans=0,in[N];
inline void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}
inline void Link(int x,int y){nxt[++num]=Head[x];to[num]=y;Head[x]=num;}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
int x,y;
cin>>n>>m>>A>>B>>C;
for(int i=1;i<=m;i++)gi(x),gi(y),link(x,y),link(y,x),in[x]++,in[y]++;
for(int i=0,u;i<n;i++)
for(int j=head[i];j;j=nxt[j])
if(in[u=to[j]]>in[i]|| (in[u]==in[i] && u>i))Link(i,u);
//+0
for(int i=0;i<n;i++){
s[i]=s[i-1]+i*A;
ss[i]=ss[i-1]+s[i-1]+B*i*i;
ans+=ss[i-1]+1ll*i*(i-1)/2*C*i;
}
for(int i=0;i<n;i++){
m=0;
for(int j=head[i];j;j=nxt[j])b[a[++m]=to[j]]=i+1;
sort(a+1,a+m+1);s[m+1]=0;
//-1
for(int j=1;j<=m && a[j]<i;j++){
ans-=(a[j]*A+i*B)*(n-i-1)+1ll*(i+n)*(n-i-1)/2*C;
ans-=(a[j]*A+i*C)*(i-a[j]-1)+1ll*(a[j]+i)*(i-a[j]-1)/2*B;
ans-=(a[j]*B+i*C)*a[j]+1ll*a[j]*(a[j]-1)/2*A;
}
//+2
for(int j=1;j<=m && a[j]<i;j++){
s[j]=s[j-1]+a[j];
ans+=s[j-1]*A+(j-1)*(a[j]*B+C*i);
}
for(int j=m;j>=1 && a[j]>i;j--){
s[j]=s[j+1]+a[j];
ans+=s[j+1]*C+(m-j)*(a[j]*B+A*i);
}
for(int j=1;j<m;j++)
if(a[j]<i && a[j+1]>i)ans+=s[j]*A*(m-j)+i*B*j*(m-j)+s[j+1]*C*j;
//-3
for(int j=Head[i];j;j=nxt[j])
for(int k=Head[to[j]];k;k=nxt[k]){
if(b[to[k]]!=i+1)continue;
int c[3]={i,to[j],to[k]};
sort(c,c+3);
ans-=A*c[0]+B*c[1]+C*c[2];
}
}
cout<<ans<<endl;
return 0;
}