昆山设计网站公司,成都建设局网站首页,中国信用网站建设的重要性,罗湖附近公司做网站建设哪家好Tree Ext 这道题相当于把3道题合了起来。
要求修复的边中恰好有 k 条白边#xff1a; 五颜六色的幻想乡(附拉格朗日插值法求多项式系数 ) bzoj2654 tree(WQS二分 新科技get)
是最小生成树计数而非生成树计数#xff1a; BZOJ1016」[JSOI2008] 最小生成树计数
具体可以看看…Tree Ext 这道题相当于把3道题合了起来。
要求修复的边中恰好有 k 条白边 五颜六色的幻想乡(附拉格朗日插值法求多项式系数 ) bzoj2654 tree(WQS二分 新科技get)
是最小生成树计数而非生成树计数 BZOJ1016」[JSOI2008] 最小生成树计数
具体可以看看这篇博客代码中的注释也解释得较清楚
#includebits/stdc.h
#define int long long
using namespace std;
const int mod1e97;
const int N105;
const int M10005;
int n,m,k,l,r;
int tot,fa[N],pa[N],id[N],num[N];
int x[N],y[N],res[N],coef[N],ans[N];
struct edge{int u,v,w,c;
}e[M];
bool cmp(edge a,edge b){if(a.wb.w) return a.cb.c;return a.wb.w;
}
int find(int u){if(fa[u]u) return u;return fa[u]find(fa[u]);
}
int get(int u){if(pa[u]u) return u;return pa[u]get(pa[u]);
}
int power(int a,int b){a%mod;int res1;while(b){if(b1) resres*a%mod;b1;aa*a%mod;}return res;
}
bool check(int mid){for(int i1;im;i)if(!e[i].c) e[i].wmid;sort(e1,em1,cmp);for(int i1;in;i) fa[i]i;int cnt0;for(int i1,j0;jn-1;i){int ufind(e[i].u),vfind(e[i].v);if(u!v){fa[v]u;j;if(!e[i].c) cnt;}}for(int i1;im;i)if(!e[i].c) e[i].w-mid;return cntk;
}
int solve(int l,int r,int x){//矩阵树定理:加入这批边中的部分边,构造已有连通块(看成点)的生成树 static int mat[N][N];memset(mat,0,sizeof(mat));for(int il;ir;i){int uid[e[i].u],vid[e[i].v];if(uv) continue;if(e[i].c)mat[u][u],mat[v][v],mat[u][v]--,mat[v][u]--;else//白边权值为x mat[u][u]x,mat[v][v]x,mat[u][v]-x,mat[v][u]-x;}memcpy(pa,fa,sizeof(fa));for(int i2;itot;i){//可能相同边权的边全部连了之后,各个连通块仍不连通,所以要提前在他们之间连一些黑边,不影响答案int uget(num[i]),vget(num[i-1]);if(u!v){pa[v]u;mat[i][i],mat[i-1][i-1],mat[i][i-1]--,mat[i-1][i]--;}}for(int i1;itot;i)for(int j1;jtot;j)mat[i][j](mat[i][j]%modmod)%mod;int res1;for(int i1;itot;i){for(int ji1;jtot;j){if(mat[j][i]){int tmat[i][i]*power(mat[j][i],mod-2)%mod,tmp;for(int ki;ktot;k){tmp(mat[i][k]-mat[j][k]*t%modmod)%mod;mat[i][k]mat[j][k];mat[j][k]tmp;}res-res;}}}if(res-1) resmod;for(int i1;itot;i) resres*mat[i][i]%mod;return res;
}
void lagerange(){static int a[N],b[N],c[N];memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));memset(res,0,sizeof(res));a[0]1;for(int i0;itot;i){b[0]0;for(int j1;ji1;j) b[j]a[j-1];for(int j0;ji;j) b[j](b[j]-x[i]*a[j]%modmod)%mod;for(int j0;ji1;j) a[j]b[j];}for(int i0;itot;i){for(int j0;jtot1;j) b[j]a[j];for(int jtot1;j1;j--){c[j-1]b[j];b[j-1](b[j-1]1LL*b[j]*x[i]%mod)%mod;}int tmp1;for(int j0;jtot;j)if(j!i) tmptmp*(x[i]-x[j]mod)%mod;tmpy[i]*power(tmp,mod-2)%mod;for(int j0;jtot;j){c[j]c[j]*tmp%mod;res[j](res[j]c[j])%mod;}}
}
signed main(){scanf(%lld%lld%lld,n,m,k);for(int i1;im;i)scanf(%lld%lld%lld%lld,e[i].u,e[i].v,e[i].w,e[i].c);l-1e9-1,r1e91;//二分找出一个合适的值x,使得所有白边边权均加上x后最小生成树中恰有k条白边 while(lr){int mid(lr1)/2;if(check(mid)) lmid;else rmid-1;}for(int i1;im;i)if(!e[i].c) e[i].wl;sort(e1,em1,cmp);for(int i1;in;i) fa[i]i;ans[0]1;for(l1;lm;lr1){rl;while(rme[l].we[r1].w) r;bool flagfalse;for(int il;ir;i){if(find(e[i].u)!find(e[i].v)){flagtrue;break;}}if(!flag) continue;memset(id,0,sizeof(id));tot0;//注意fa没有重置,即之前加的边构成的连通块还在 for(int il;ir;i){//考虑一批有相同权值的边 int ufind(e[i].u),vfind(e[i].v);e[i].uu;e[i].vv;//缩点 if(u!v){if(!id[u]){id[u]tot;num[tot]u;//这一批边关联的连通块数量1 }if(!id[v]){id[v]tot;num[tot]v;//这一批边关联的连通块数量1 }}}for(int il;ir;i){int ufind(e[i].u),vfind(e[i].v);if(u!v) fa[v]u;}for(int i0;itot;i){//把白边边权看成未知数x,基尔霍夫矩阵的行列式为关于x的多项式 //代入不同的x,分别求出对应的y,通过插值求出多项式的各项系数 x[i]i1;y[i]solve(l,r,i1);}lagerange();memset(coef,0,sizeof(coef));for(int i0;in;i){//乘法原理,把这一次加边的结果与之前的乘起来 for(int j0;ijn;j){coef[ij]ans[i]*res[j]%mod;coef[ij]%mod;}}memcpy(ans,coef,sizeof(coef));}for(int i2;in;i){if(find(i)!find(1)){puts(0);return 0;}}printf(%lld\n,ans[k]);return 0;
}
