[生成树] AtCoder ARC 093E - Bichrome Spanning Tree

一开始看错题... 挺简单的吧,先求出任意一个最小生成树,思考在它基础上变化:

对于不在 \(MST\) 中的边,记 \(MaxEdge(x,y)\)\(MST\)\(x\)\(y\) 路径的最大边权

对于一条边 \(e=(x,y)\) ,比较 \(X\)\(w(MST)-MaxEdge(x,y)+w_e\) 的大小

即加入此边之后的 \(MST\) 是否超出 \(X\) 。把边分为 \(low, equal, upper\) \(3\) 类。

  • \(w(MST)>X\) ,答案显然为 \(0\)

  • \(w(MST) < X\) , 则 \(MST\)\(low\) 中的边都同色,\(equal\) 中至少一个和它们异色,\(upper\) 随意。

    答案为 \(2(2^{equal}-1)2^{upper}\)

  • \(w(MST) = X\) ,第一种情况是 \(MST\) 中的边都同色,答案同上

    还有就是 \(MST\) 中有不同色的,答案为 \((2^{n-1}-1)2^{m-(n-1)}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1005,maxe=4005,P=1e9+7;
int n,m;
LL pw[maxe],MST,W,ans;
struct Edge{
int x,y,w,flg;
Edge(int t1=0,int t2=0,int t3=0){ x=t1; y=t2; w=t3; flg=0; }
bool operator < (const Edge &A)const{ return w<A.w; }
} Es[maxe];
int fir[maxn],nxt[maxe],w[maxe],son[maxe],tot;
void add(int x,int y,int z){
son[++tot]=y; w[tot]=z; nxt[tot]=fir[x]; fir[x]=tot;
}
int fa[maxn];
int getfa(int x){ return fa[x]==x?x:fa[x]=getfa(fa[x]); }
void merge(int x,int y){
x=getfa(x); y=getfa(y);
if(x!=y) fa[x]=y;
}
void Kruskal(){
sort(Es+1,Es+1+m);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
if(getfa(Es[i].x)==getfa(Es[i].y)) continue;
MST+=Es[i].w; add(Es[i].x,Es[i].y,Es[i].w); add(Es[i].y,Es[i].x,Es[i].w);
merge(Es[i].x,Es[i].y); Es[i].flg=1;
}
}
int anc[maxn][11],_max[maxn][11],dep[maxn];
void dfs_info(int x,int pre,int w_pre){
anc[x][0]=pre; _max[x][0]=w_pre;
for(int i=1;i<=10;i++){
anc[x][i]=anc[anc[x][i-1]][i-1];
_max[x][i]=max(_max[x][i-1],_max[anc[x][i-1]][i-1]);
}
for(int j=fir[x];j;j=nxt[j])
if(son[j]!=pre) dep[son[j]]=dep[x]+1, dfs_info(son[j],x,w[j]);
}
int getMax(int x,int y){
int res=0;
if(dep[x]<dep[y]) swap(x,y);
for(int i=10;i>=0;i--)
if(dep[anc[x][i]]>=dep[y]) res=max(res,_max[x][i]), x=anc[x][i];
if(x==y) return res;
for(int i=10;i>=0;i--)
if(anc[x][i]!=anc[y][i]){
res=max(res,max(_max[x][i],_max[y][i]));
x=anc[x][i]; y=anc[y][i];
}
return max(res,max(_max[x][0],_max[y][0]));
}
int num_low,num_eq,num_upp;
int main(){
freopen("arc093_c.in","r",stdin);
freopen("arc093_c.out","w",stdout);
scanf("%d%d%lld",&n,&m,&W);
for(int i=1;i<=m;i++) scanf("%d%d%d",&Es[i].x,&Es[i].y,&Es[i].w);
Kruskal(); dfs_info(1,1,0);
if(MST>W) return puts("0"),0;
for(int i=1;i<=m;i++){
if(Es[i].flg) continue;
LL t=MST-getMax(Es[i].x,Es[i].y)+Es[i].w;
t==W?num_eq++:(t>W?num_upp++:num_low++);
}
pw[0]=1; for(int i=1;i<=2000;i++) pw[i]=pw[i-1]*2%P;
if(MST<W) ans=(pw[num_eq]-1)*pw[num_upp]%P*2%P;
else ans=(pw[n-1]-2)*pw[m-n+1]%P+(pw[num_eq]-1)*pw[num_upp]%P*2%P;
printf("%d\n",(ans%P+P)%P);
return 0;
}