【BZOJ1016】【JSOI2008】最小生成树计数

这题做法好玄妙啊。。

直接上结论：对于每一种权值的所有边，其在最小生成树中的作用是固定的

也就是先求一遍最小生成树，然后对于每一种权值的边，记录他们对于最小生成树的贡献。那么对于从小到大枚举所有权值的边，枚举这一种权值中所有边选/不选，判断贡献是否与一开始的最小生成树中的相同。然后乘起来就可以了。

听说还可以用基尔霍夫矩阵。。去学了一下这个东西好像还挺好懂。。

好玄妙啊。。

// <1016.cpp> - 05/18/16 19:16:01
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=110,MAXM=1010;
const int INF=1e9;
const int MOD=31011;
struct edge{
    int a,b,c;
    bool operator <(const edge y) const{return c<y.c;}
}e[MAXM];
struct block{
    int l,r,v;
}b[MAXM];
int tot;
int f[MAXN];
int gf(int x){return x==f[x]?x:gf(f[x]);}
int num;
void dfs(int x,int now,int k){
     if(now==b[x].r+1){
         if(k==b[x].v)num++;
         return;
     }
     int fa=gf(e[now].a),fb=gf(e[now].b);
     if(fa!=fb){
         f[fa]=fb;
         dfs(x,now+1,k+1);
         f[fa]=fa;f[fb]=fb;
     }
     dfs(x,now+1,k);
}
int main(){
    int n=gi(),m=gi();
    for(int i=1;i<=m;i++)e[i].a=gi(),e[i].b=gi(),e[i].c=gi();
    sort(e+1,e+m+1);
    for(int i=1;i<=n;i++)f[i]=i;
    int cnt=0;
    for(int i=1;i<=m;i++){
        if(e[i].c!=e[i-1].c){b[tot].r=i-1;b[++tot].l=i;}
        int fa=gf(e[i].a),fb=gf(e[i].b);
        if(fa!=fb){f[fa]=fb;b[tot].v++;cnt++;}
    }
    b[tot].r=m;
    if(cnt!=n-1){putchar('0');return 0;}
    for(int i=1;i<=n;i++)f[i]=i;
    int ans=1;
    for(int i=1;i<=cnt;i++){
        num=0;
        dfs(i,b[i].l,0);
        ans=ans*num%MOD;
        for(int j=b[i].l;j<=b[i].r;j++){
            int fa=gf(e[j].a),fb=gf(e[j].b);
            if(fa!=fb)f[fa]=fb;
        }
    }
    printf("%d",ans);
    return 0;
}

// <1016.cpp> - 05/18/16 19:16:01

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=110,MAXM=1010;

const int INF=1e9;

const int MOD=31011;

struct edge{

int a,b,c;

bool operator <(const edge y) const{return c<y.c;}

}e[MAXM];

struct block{

int l,r,v;

}b[MAXM];

int tot;

int f[MAXN];

int gf(int x){return x==f[x]?x:gf(f[x]);}

int num;

void dfs(int x,int now,int k){

if(now==b[x].r+1){

if(k==b[x].v)num++;

return;

}

int fa=gf(e[now].a),fb=gf(e[now].b);

if(fa!=fb){

f[fa]=fb;

dfs(x,now+1,k+1);

f[fa]=fa;f[fb]=fb;

}

dfs(x,now+1,k);

}

int main(){

int n=gi(),m=gi();

for(int i=1;i<=m;i++)e[i].a=gi(),e[i].b=gi(),e[i].c=gi();

sort(e+1,e+m+1);

for(int i=1;i<=n;i++)f[i]=i;

int cnt=0;

for(int i=1;i<=m;i++){

if(e[i].c!=e[i-1].c){b[tot].r=i-1;b[++tot].l=i;}

int fa=gf(e[i].a),fb=gf(e[i].b);

if(fa!=fb){f[fa]=fb;b[tot].v++;cnt++;}

}

b[tot].r=m;

if(cnt!=n-1){putchar('0');return 0;}

for(int i=1;i<=n;i++)f[i]=i;

int ans=1;

for(int i=1;i<=cnt;i++){

num=0;

dfs(i,b[i].l,0);

ans=ans*num%MOD;

for(int j=b[i].l;j<=b[i].r;j++){

int fa=gf(e[j].a),fb=gf(e[j].b);

if(fa!=fb)f[fa]=fb;

}

printf("%d",ans);

return 0;

}

说点什么