一道国家集训队好几年前的互测题, 现场似乎被当做送分题? 我是在XYM屠历年集训队题目的时候发现自己碰巧会做?

想我这样的菜鸡, 肯定只是碰巧好吧。 而且看我的常数那么大, 一定是人傻QWQ

题目链接

题目大意

给出一颗\(n\)个节点的树,要给每一条边染一个\(1\)~\((n-1)\)的颜色,染颜色\(i\)的代价为\(i\),要求同一个节点连出的所有边所染颜色都互不相同,求一个为整棵树染色的方案,使得代价之和尽量小。

解题报告

先考虑设计状态, 令\(f[x][i]\)表示与\(x\)相连的边不能染\(i\)这个颜色, \(x\)的子树中的最小代价。

考虑从子节点向父亲节点进行转移, 那么可以枚举父亲节点与爷爷节点的边的颜色,然后是把\(1\)~\((n-1)\)这些颜色分配给儿子节点, 每个颜色只能使用一次, 颜色本身和颜色对应每个儿子有各自的代价, 这个转移是相当复杂的。

但仔细想一下哈, 这么强的限制竟然极其类似二分图的最大权匹配, 所以可以使用费用流或者KM这类的进行转移。

具体的, \(S\)向每种颜色\(i\)连流量\(1\), 费用\(i\)的边, 每种颜色向每个儿子\(y\)连流量\(1\), 费用\(f[y][i]\)的边, 每个儿子向\(T\)连流量\(1\), 费用\(0\)的边。

然后这个题就在时限内解决了。。

后记: 写代码的时候大脑一热, 从网上找了一个zkw费用流的板子膜敲了一遍, 发现各种慢慢慢。。 以后还是老老实实spfa费用流(单增广)吧。

代码

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
#define rep(i,b) for(int i=0,nn=int(b);i<nn;++i)
#define REP(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define VEP(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
const int N=200;
const int inf=1000000000;
struct edge {
int nxt,to; edge(int nxt=0,int to=0)
:nxt(nxt),to(to) {}
} e[N<<1];
int n, f[N][N],tot,hed[N],da[N];
inline void add(int x,int y) {
e[++tot]=edge(hed[x],y),hed[x]=tot;
}
namespace cst {
struct edge {
int nxt,to,f,c; edge() {nxt=to=f=c=0;}
edge(int nxt,int to,int f,int c)
:nxt(nxt),to(to),f(f),c(c){}
} e[N*N*4];
int S,T,tot,hed[N*2],d[N*2],cst,piS;
deque<int> q; bool v[N*20];
void clean() {
REP(i,0,tot) e[i]=edge();
REP(i,0,N+N) hed[i]=0;
tot=1,cst=0,piS=0;
}
void add(int x,int y,int f,int c) {
e[++tot]=edge(hed[x],y,f,c), hed[x]=tot;
e[++tot]=edge(hed[y],x,0,-c), hed[y]=tot;
}
bool label() {
REP(i,S,T) d[i]=inf; d[T]=0,q.push_back(T);
int x,y,dt;
while (q.size()) { x=q.front(); q.pop_front();
for (int i=hed[x];i;i=e[i].nxt)
if (y=e[i].to,e[i^1].f&&(dt=d[x]-e[i].c)<d[y])
d[y]=dt, d[y]<=(q.size()?d[q.front()]:0)
? q.push_front(y): q.push_back(y);
}
REP(i,S,T) for(int j=hed[i];j;j=e[j].nxt)
e[j].c+=d[e[j].to]-d[i];
piS+=d[S];
return d[S]<inf;
}
bool dfs(int x,int lm) { int l=lm,y,f;
v[x]=1;
if (x==T) return cst+=lm*piS,lm;
for (int i=hed[x];i;i=e[i].nxt)
if(y=e[i].to, e[i].f&&!v[y]&&!e[i].c) {
f=dfs(y,e[i].f<l?e[i].f:l),e[i].f-=f,e[i^1].f+=f;
l-=f; if (!l) return lm;
}
return lm-l;
}
int mcmf() {
while (label()) do
REP(i,S,T) v[i]=0;
while (dfs(S,inf));
return cst;
}
}
void who_s_your_daddy(int x,int fa) {
da[x]=fa; int y; for(int i=hed[x];i;i=e[i].nxt)
if (y=e[i].to, y!=fa) who_s_your_daddy(y,x);
}
int dfs(int x, int ba) {
if (f[x][ba]!=-1) return f[x][ba];
int y,ct=0;
for (int i=hed[x];i;i=e[i].nxt)
if (y=e[i].to, y!=da[x]) { ++ct;
for (int j=1;j<n;++j) if (j!=ba) dfs(y,j);
}
if (ct==0) return f[x][ba]=0;
cst::clean();
cst::S=0,cst::T=n+ct; REP(i,1,n-1)
if (i!=ba) cst::add(cst::S,i,1,i);
ct=n-1; for (int i=hed[x];i;i=e[i].nxt)
if (y=e[i].to, y!=da[x]) { ++ct;
for (int j=1; j<n; ++j) if (j!=ba)
cst::add(j,ct,1,f[y][j]);
cst::add(ct,cst::T,1,0);
}
f[x][ba]=cst::mcmf();
return f[x][ba];
}
int main() {
scanf("%d",&n);
memset(f,-1,sizeof(f));
rep(i,n-1) { int x, y; scanf("%d%d",&x,&y);
add(x,y), add(y,x);
}
who_s_your_daddy(1,0);
printf("%d\n",dfs(1,n));
return 0;
}

留言