[JSOI2008]最小生成树计数 【分组思想】【暴力并差集】【DFS】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1016
【算法分析】
假设我们使用的是kruskal算法，那么就很容易弄出来了。
首先先把边按权排序，然后等权的分成同一组。
易知如果是最小生成树的话，那么在经历过前K组以后。
无论前面是怎么搞的，连通性都应该是一致的~
那么就可以分段搞。
而且每一组里互不干涉。
最后利用分步乘法原理就可以得解。
至于每一步怎么求，那么就需要注意到题目的一个猥琐的小角落有这么一句话：注意：具有相同权值的边不会超过10条。
然后由于这个条件，于是就可以暴力DFS求每一步。最终得出解。
【其它】
1Y。另外那个并差集有点小假。。。回溯的时候，我直接弄个数组Copy过去保存，最终依然是15MSAC。
另外要注意可能会有没有生成树的情况。
【CODE】
#include #include #include #define Copy(a,b) memcpy(a+1,b+1,sizeof(int)*n)
const int mod=31011;
struct edge{int x,y,w;}g[1005];
int n,m,ans;
int f[105],tf[105];
int cmp(const void *A,const void *B){return ((edge*)A)->w-((edge*)B)->w;}

void init(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].w);
}

int gf(int k){
if (f[k]==k) return k;
return f[k]=gf(f[k]);
}

int tgf(int k){
if (tf[k]==k) return k;
return tf[k]=tgf(tf[k]);
}

int tmpf[25][105],cnt,dep,done;
void dfs(int i,int ed,int total){
if (done==total){cnt++; return;}
if (i>ed) return;
if (tgf(g[i].x)!=tgf(g[i].y)){
Copy(tmpf[dep],tf);
tf[tf[g[i].x]]=tf[g[i].y];
dep++;
done++;
dfs(i+1,ed,total);
dep–;
done–;
Copy(tf,tmpf[dep]);
}
dep++;
dfs(i+1,ed,total);
dep–;
}

void solve(){
int i,j,k,p=n,total;
ans=1;
for (i=1;i<=n;i++) f[i]=tf[i]=i;
for (i=1;i<=m;i=j+1){
for (j=i;j total=0;
for (k=i;k<=j;k++)
if (gf(g[k].x)!=gf(g[k].y)){
f[f[g[k].x]]=f[g[k].y];
total++;
}
p-=total;
cnt=dep=done=0;
dfs(i,j,total);
Copy(tf,f);
ans=ans*cnt%mod;
}
if (p!=1) printf("0n");
else printf("%dn",ans);
}

int main(){
init();
qsort(g+1,m,sizeof(edge),cmp);
solve();
return 0;
}