bzoj1808 [Ioi2007]training 训练路径

Description

马克(Mirko)和斯拉夫克(Slavko)正在为克罗地亚举办的每年一次的双人骑车马拉松赛而紧张训练。他们需要选择一条训练路径。他们国家有N个城市和M条道路。每条道路连接两个城市。这些道路中恰好有N-1条是铺设好的道路，其余道路是未经铺设的土路。幸运的是，每两个城市之间都存在一条由铺设好的道路组成的通路。换句话说，这N个城市和N-1条铺设好的道路构成一个树状结构。此外，每个城市最多是10条道路的端点。一条训练路径由某个城市开始，途经一些道路后在原来起始的城市结束。因为马克和斯拉夫克喜欢去看新城市，所以他们制定了一条规则：绝不中途穿越已经去过的城市，并且绝不在相同的道路上骑行两次（不管方向是否相同）。训练路径可以从任何一个城市开始，并且不需要访问所有城市。显然，坐在后座的骑行者更为轻松，因为坐在前面的可以为他挡风。为此，马克和斯拉夫克在每个城市都要调换位置。为了保证他们的训练强度相同，他们要选择一条具有偶数条道路的路径。马克和斯拉夫克的竞争者决定在某些未经铺设的土路上设置路障，使得他们两人不可能找到满足上述要求的训练路径。已知在每条土路上设置路障都有一个费用值（一个正整数），并且竞争者不能在铺设好的道路上设置路障。任务给定城市和道路网的描述，写一个程序计算出为了使得满足上述要求的训练路径不存在，而需要的设置路障的最小总费用。

Input

输入的第一行包含两个整数N和M，（2≤N≤1000，N-1≤M≤5000），分别表示城市和道路的个数。接下来的M行每行包含3个整数A, B和C（1≤A≤N, 1≤B≤N, 0≤C≤10 000）, 用来描述一条道路。A和B是不同的整数，表示由这条道路直接相连的两个城市。对于铺设好的道路C是0；对于土路，c是在该条路上设置路障所需的费用值。每个城市最多是10条道路的端点。任意两个城市都不会有多于一条直接相连的道路。

Output

输出包含一个整数，表示求出的最小总费用。

Sample Input

5 8
2 1 0
3 2 0
4 3 0
5 4 0
1 3 2
3 5 2
2 4 5
2 5 1

Sample Output

HINT

正解：状压$dp$。

这道题应该是去年某场考试考过的题，当时爆零了(似乎是因为没有小数据的暴力分。。

首先如果一条边的两个点在树上的路径长度为奇数，那么这条边肯定要删掉。

那么我们可以发现，这时存在偶环的充要条件就是一个环经过了任意两条非树边。

因为两个奇环通过公共边拼在一起，再把公共边挖掉，肯定是一个偶环。

所以这道题的限制就是不能出现这种情况，也就是说我们需要留下一棵仙人掌。

知道这个性质以后就不是那么难做了(虽然对于我来说还是很难

我们先把题意转化成用总边权减去最大留下的边权。

考虑一个条件，即每个点度数不超过$10$，这启发我们可以在树上维护儿子的状态。

于是考虑状压$dp$，设$f[i][S]$表示$i$这棵子树，不考虑状态$S$的集合的儿子(就是把这些儿子砍掉)的最大值。

我们考虑在$lca$处计算一条边的贡献，首先如果$lca$为$i$的所有边都不留，那么$f[i][S]=sum f[son][S]$。

然后我们依次考虑每一条边必须加的贡献，对于每一条边，设两个端点为$a,b$(如果有一个为$lca$就把这个点丢掉)。

那么我们的贡献就是$w+f[a]+f[b]$再加上所有$a$到$b$路径上的每个点(不包括$a,b,lca$)不考虑它在路径上的儿子的状态。

很显然，这条路径不能被其他非树边覆盖，所以我们就必须把这条路径上的树边都断开，把一个点的贡献加上的时候不能考虑路径上的其他点。

所以这道题我们就做完了，复杂度为$O(m*2^{10}+mn)$。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define N (2005)
 6 
 7 using namespace std;
 8 
 9 vector<int> h[N];
10 
11 struct E{ int u,v,w; }e[5005];
12 struct edge{ int nt,to; }g[N<<1];
13 
14 int f[N][N],st[N],sz[N],fa[N],son[N],top[N],tid[N],dep[N],head[N],n,m,num,sum,tot;
15 
16 il int gi(){
17   RG int x=0,q=1; RG char ch=getchar();
18   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
19   if (ch=='-') q=-1,ch=getchar();
20   while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
21   return q*x;
22 }
23 
24 il void insert(RG int from,RG int to){
25   g[++num]=(edge){head[from],to},head[from]=num; return;
26 }
27 
28 il void dfs1(RG int x,RG int p){
29   fa[x]=p,sz[x]=1,dep[x]=dep[p]+1;
30   for (RG int i=head[x],v;i;i=g[i].nt){
31     v=g[i].to; if (v==p) continue;
32     dfs1(v,x),sz[x]+=sz[v];
33     if (sz[son[x]]<=sz[v]) son[x]=v;
34   }
35   return;
36 }
37 
38 il void dfs2(RG int x,RG int p,RG int anc){
39   top[x]=anc; if (son[x]) dfs2(son[x],x,anc);
40   for (RG int i=head[x],v;i;i=g[i].nt){
41     v=g[i].to; if (v!=p && v!=son[x]) dfs2(v,x,v);
42   }
43   return;
44 }
45 
46 il int lca(RG int u,RG int v){
47   while (top[u]!=top[v]){
48     if (dep[top[u]]<dep[top[v]]) swap(u,v);
49     u=fa[top[u]];
50   }
51   return dep[u]<dep[v] ? u : v;
52 }
53 
54 il void dfs(RG int x,RG int p){
55   RG int tot=0,sum;
56   for (RG int i=head[x];i;i=g[i].nt) if (g[i].to!=p) dfs(g[i].to,x);
57   for (RG int i=head[x];i;i=g[i].nt) if (g[i].to!=p) tid[g[i].to]=1<<tot,st[tot++]=g[i].to;
58   for (RG int i=(1<<tot)-1;~i;--i){
59     sum=0; for (RG int j=0;j<tot;++j) if (!(i>>j&1)) sum+=f[st[j]][0]; f[x][i]=sum;
60   }
61   for (RG int i=0,a=0,b=0,id,S=h[x].size();i<S;++i,a=b=0){
62     id=h[x][i],sum=e[id].w;
63     if (e[id].u!=x) for (sum+=f[a=e[id].u][0];fa[a]!=x;a=fa[a]) sum+=f[fa[a]][tid[a]];
64     if (e[id].v!=x) for (sum+=f[b=e[id].v][0];fa[b]!=x;b=fa[b]) sum+=f[fa[b]][tid[b]];
65     for (RG int j=(1<<tot)-1;~j;--j)
66       if (!(j&tid[a]) && !(j&tid[b])) f[x][j]=max(f[x][j],sum+f[x][j|tid[a]|tid[b]]);
67   }
68   return;
69 }
70 
71 int main(){
72 #ifndef ONLINE_JUDGE
73   freopen("training.in","r",stdin);
74   freopen("training.out","w",stdout);
75 #endif
76   n=gi(),m=gi();
77   for (RG int i=1,u,v,w;i<=m;++i){
78     u=gi(),v=gi(),w=gi(),sum+=w;
79     if (w) e[++tot]=(E){u,v,w};
80     if (!w) insert(u,v),insert(v,u);
81   }
82   dfs1(1,0),dfs2(1,0,1);
83   for (RG int i=1,G;i<=tot;++i){
84     G=lca(e[i].u,e[i].v);
85     if (!((dep[e[i].u]+dep[e[i].v]-(dep[G]<<1))&1)) h[G].push_back(i);
86   }
87   dfs(1,0),cout<<sum-f[1][0]; return 0;
88 }