Run
题意:
给出一张图(点数为n,边数为m)的一个生成树和一些非树边。
每条非树边有一个代价w，表示炸毁这条边需要付出的代价。
求炸毁一些非树边使得图中不存在偶环所付出的最小代价。
特别地，生成树上点的度数不超过10.
数据范围:n<=1000,m<=4000
分析:
首先如果一条非树边跨越了树上奇数条边，则这条边必须炸毁。
剩下的边，如果任意两条边所跨越的树上路径有公共边，则会存在偶环。
考虑到每个节点的儿子最多只有10个，我们可以考虑状压dp.
令f[x][s]表示以x为根的子树,只考虑集合s中儿子时能保留的边的最大权值。
令g[x][i]表示以x为根的子树,不考虑x的第i个儿子时能保留的边的最大权值。
每条非树边，只在它的端点的lca处考虑影响。
为了让路径不重复，则该非树边所覆盖的路径都不能被选。
暴力从一个端点到lca统计不考虑路径上的边时的最大权值。
再与该非树边没有覆盖的部分一起更新答案。
复杂度O(n*210+n*m)
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 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 | #include <vector>#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;#define g() getchar()template<class Q>void Scan(Q&x){ char c;int f=1; while(c=g(),c<48||c>57)if(c=='-')f=-1; for(x=0;c>47&&c<58;c=g())x=10*x+c-48; x*=f;}#define Max(x,y) if(x<y)x=y#define Min(x,y) if(x>y)x=y #define pb push_back#define rep(i,a,b) for(int i=a;i<b;++i)const int MAXN=1005;const int MAXS=1<<10;int n,m;struct edge{ int t,n; edge(int t=0,int n=0):t(t),n(n){}}e[MAXN<<1];int head[MAXN],tot;inline void AddEdge(int s,int t){ e[++tot]=edge(t,head[s]),head[s]=tot; e[++tot]=edge(s,head[t]),head[t]=tot;}int p[MAXN],dep[MAXN];vector<int>ch[MAXN],qy[MAXN];void dfs(int x){ for(int i=head[x],y;i;i=e[i].n) if((y=e[i].t)!=p[x]){ p[y]=x; dep[y]=dep[x]+1; ch[x].pb(y); dfs(y); }}inline int lca(int x,int y){ if(dep[x]>dep[y])swap(x,y); while(dep[y]>dep[x])y=p[y]; while(p[x]!=p[y])x=p[x],y=p[y]; return x==y?x:p[x];}struct edge1{ int u,v,w; inline void scan(){ Scan(u),Scan(v),Scan(w); }}tmp[MAXN*5];int ans;inline void Init(){ Scan(n),Scan(m); rep(i,1,m+1){ tmp[i].scan(); ans+=tmp[i].w; if(!tmp[i].w){ AddEdge(tmp[i].u,tmp[i].v); } } dfs(1); rep(i,1,m+1){ if(!tmp[i].w)continue; int u=tmp[i].u,v=tmp[i].v; int Lca=lca(u,v); if((dep[u]+dep[v]-dep[Lca]*2)&1)continue; qy[Lca].pb(i); }}int dp[MAXN];int f[MAXN][MAXS],g[MAXN][10];inline int swim(int x,int par,int&res){ int ban=-1; while(x!=par){ if(~ban)res+=g[x][ban]; else res+=dp[x]; int s=ch[p[x]].size(); rep(i,0,s) if(x==ch[p[x]][i]){ ban=i; break; } x=p[x]; } return ban;}void tree_dp(int x){ for(int i=head[x],y;i;i=e[i].n) if((y=e[i].t)!=p[x])tree_dp(y); int s=ch[x].size(); int maxs=1<<s; rep(set,0,maxs){ int res=0; rep(i,0,s) if(set>>i&1){ res+=dp[ch[x][i]]; } Max(f[x][set],res); } int c=qy[x].size(); rep(i,0,c){ int u=tmp[qy[x][i]].u; int v=tmp[qy[x][i]].v; int res=tmp[qy[x][i]].w; int bu=max(0,1<<swim(u,x,res)); int bv=max(0,1<<swim(v,x,res)); rep(set,0,maxs){ if(bu&&(set&bu)==bu||bv&&(set&bv)==bv) continue; int ns=set^bu^bv; Max(f[x][ns],res+f[x][set]); } } rep(set,0,maxs){ rep(i,0,s) if(!(set>>i&1)){ Max(g[x][i],f[x][set]); } Max(dp[x],f[x][set]); }}inline void Solve(){ tree_dp(1); ans-=dp[1]; printf("%d\n",ans);}int main(){ freopen("run.in","r",stdin); freopen("run.out","w",stdout); Init(); Solve(); return 0;} |
