[ICPC2021 Nanjing R] Ancient Magic Circle in Teyvat
设 \(f_x\) 表示钦定至少有 \(x\) 条边的四元子图个数,由容斥我们有一条边都没有的子图个数是 \(f_0-f_1+f_2-f_3+f_4-f_5+f_6\),而所有边都有的个数就是 \(f_6\)。作差之后只需要求 \(f_0,f_1,f_2,f_3,f_4,f_5\)。
子图计数只要不是数 \(K_4\),其它所有的四元图都是好做的,把你会的三元环、四元环、\(K_4\) 少一条边的计数方法全用上就可以了。
#include <cstdio>
#include <vector>
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=x*10+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=100003,M=200003;
typedef long long ll;
typedef __int128 lll;
int n,m;lll res;
void write(lll x){if(x>9) write(x/10);putchar((x%10)^48);}
lll C4(int x){return (lll)x*(x-1)*(x-2)*(x-3)/24;}
lll C3(int x){return (lll)x*(x-1)*(x-2)/6;}
lll C2(int x){return (lll)x*(x-1)>>1;}
int eu[M],ev[M],d[N];
vector<int> adj[N],vec[N],ec[N];
int vis[N],ps[N];
inline bool cmp(int x,int y){
if(d[x]!=d[y]) return d[x]>d[y];
return x<y;
}
int main(){
n=read();m=read();
for(int i=1;i<=m;++i){
eu[i]=read();ev[i]=read();
adj[eu[i]].emplace_back(ev[i]);
adj[ev[i]].emplace_back(eu[i]);
}
for(int i=1;i<=n;++i) d[i]=adj[i].size();
for(int i=1;i<=m;++i)
if(cmp(eu[i],ev[i])) vec[eu[i]].emplace_back(ev[i]);
else vec[ev[i]].emplace_back(eu[i]);
for(int i=1;i<=n;++i) ec[i].resize(vec[i].size());
res=C4(n)-m*C2(n-2);
lll tmp=0;
for(int i=1;i<=m;++i){
tmp+=(lll)(d[eu[i]]+d[ev[i]]-2)*(n-4);
res-=(lll)(d[eu[i]]-1)*(d[ev[i]]-1);
}
res+=C2(m)+(tmp>>1);
for(int x=1;x<=n;++x){
res-=C3(d[x]);
int id=0;
for(int y:vec[x]) vis[y]=x,ps[y]=id++;
id=0;
for(int y:vec[x]){
int nid=0;
for(int z:vec[y]){
if(vis[z]==x){
res+=d[x]+d[y]+d[z]-n;
res-=ec[x][id]++;
res-=ec[x][ps[z]]++;
res-=ec[y][nid]++;
}
++nid;
}
++id;
}
}
for(int x=1;x<=n;++x){
for(int y:vec[x])
for(int z:adj[y]) vis[z]=0;
for(int y:vec[x])
for(int z:adj[y]) if(cmp(x,z)) res+=vis[z]++;
}
if(res<0) res=-res;
write(res);putchar('\n');
return 0;
}
[GDCPC2023] Classic Problem
套路题,离散化之后 Boruvka 一下就行了。
我为啥这玩意需要写拍才能调出来啊?
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
typedef long long ll;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=x*10+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=100003,M=400013;
const int INF=0x3f3f3f3f;
int n,m;ll res;
int eu[N],ev[N],ew[N];
int buc[M],rk;
vector<pii> vec[M];
vector<int> arr[M];
int f[M],dir[M],mn[M];
int rt(int x){
if(f[x]==x) return x;
return f[x]=rt(f[x]);
}
int dis(int x,int y){
if(x>y) swap(x,y);
return buc[y-1]+1-buc[x];
}
int pre[M],suf[M],cur[M];
void solve(){
n=read();m=read();rk=0;res=0;
for(int i=1;i<=m;++i){
buc[++rk]=eu[i]=read();if(eu[i]>1) buc[++rk]=eu[i]-1;
buc[++rk]=ev[i]=read();if(ev[i]>1) buc[++rk]=ev[i]-1;
ew[i]=read();
}
buc[++rk]=n;
sort(buc+1,buc+rk+1);rk=unique(buc+1,buc+rk+1)-buc-1;
n=rk;
for(int i=1;i<=n;++i) vec[i].clear(),f[i]=i,res+=buc[i]-buc[i-1]-1;
for(int i=1;i<=m;++i){
eu[i]=lower_bound(buc+1,buc+n+1,eu[i])-buc;
ev[i]=lower_bound(buc+1,buc+n+1,ev[i])-buc;
vec[eu[i]].emplace_back(ev[i],ew[i]);
vec[ev[i]].emplace_back(eu[i],ew[i]);
}
int cnt=n-1;
while(cnt){
for(int i=1;i<=n;++i) arr[rt(i)].emplace_back(i),cur[i]=-1;
for(int i=1;i<=n;++i){
dir[i]=-1;mn[i]=INF;
if(f[i]==i){
int sz=arr[i].size();
for(int t=0;t<sz;++t){
int x=arr[i][t];
if(t&&arr[i][t-1]==x-1) pre[x]=pre[x-1];
else pre[x]=x-1;
}
for(int t=sz-1;~t;--t){
int x=arr[i][t];
if(t+1<sz&&arr[i][t+1]==x+1) suf[x]=suf[x+1];
else suf[x]=x+1;
}
for(int x:arr[i]){
for(auto [y,w]:vec[x]){
if(rt(y)!=i&&w<mn[i]) dir[i]=y,mn[i]=w;
cur[y]=x;
}
int t;
t=x-1;
while(t){
if(cur[t]==x){--t;continue;}
if(rt(t)==i){t=pre[t];continue;}
if(dis(x,t)<mn[i]) mn[i]=dis(x,t),dir[i]=t;
break;
}
t=x+1;
while(t<=n){
if(cur[t]==x){++t;continue;}
if(rt(t)==i){t=suf[t];continue;}
if(dis(x,t)<mn[i]) mn[i]=dis(x,t),dir[i]=t;
break;
}
}
}
}
for(int i=1;i<=n;++i){
arr[i].clear();
if((~dir[i])&&rt(i)!=rt(dir[i])) f[rt(i)]=rt(dir[i]),res+=mn[i],--cnt;
}
}
printf("%lld\n",res);
}
int main(){
int tc=read();
while(tc--) solve();
return 0;
}
标签:return,速通,int,Solution,read,lll,buc,杂题,rk
From: https://www.cnblogs.com/yyyyxh/p/18351460/problemsset1