這道題也是各種折騰人......
題解可以參考這篇
稍微說一下我自己在看完題解後想不通的點。
剛開始我實在想不通：為什麼總複雜度不是狀態數*邊數呢？(O(2^10 * n * m))
如果我們按照常用的記憶化搜索，對於每個狀態dp[i][j]都把所有的邊嘗試一遍的話確實會退化成這樣子的。
所以在這邊加了點巧思，讓複雜度不會爛成那樣子。
關鍵點之一：每個lca為自己的邊（也就是可以拿來轉移的邊)會覆蓋到1 or 2條自己邊，其中1條邊的情況對應到「自己是這條邊的其中一個點」。
關鍵點之二：對於所有dp[i][j]，若有dp[i][x]可轉移到dp[i][j]，那麼必有bitcnt(j)>bitcnt(x)。
這裡bitcnt(x)指x在二進位下1的數量。
想通了第二點之後，我們就可以遞增二進位下1的數量來計算dp了。
剩下的細節還是很多的。
例如因為我們需要查詢要拿來轉移的邊會覆蓋到哪些不能刪除的邊（本來的樹邊），我開了一個map用來紀錄兩個點之間的邊編號關係（聽起來好饒舌=口=)，在處理邊的時候會用上。
lca的部份用的是倍增算法，主要是因為我比較熟這個，當然換成offline的Tarjan也是可以的。
精華點在於dp和getcost的部份，多說無益，不妨直接閱讀XD。
#include<cstdio> #include<cstdlib> #include<vector> #include<map> using namespace std; inline int cntbit(int x) { x=((x&0xAAAAAAAA)>>1)+(x&0x55555555); x=((x&0xCCCCCCCC)>>2)+(x&0x33333333); x=((x&0xF0F0F0F0)>>4)+(x&0x0F0F0F0F); x=((x&0xFF00FF00)>>8)+(x&0x00FF00FF); x=((x&0xFFFF0000)>>16)+(x&0x0000FFFF); return x; } const int maxn=1000+5; const int maxlog=10+2; const int maxdeg=10+2; int N,M; struct Edge {int from,to,w;}; vector<Edge> edges; vector<int> G[maxn],Glca[maxn]; int anc[maxn][maxlog],dep[maxn]; int LCA(int a,int b) { if(dep[a]>dep[b]) swap(a,b); for(int log=maxlog-1;log>=0;log--) if(anc[b][log]!=-1 && dep[anc[b][log]]>=dep[a]) b=anc[b][log]; if(a==b) return a; for(int log=maxlog-1;log>=0;log--) if(anc[a][log]!=-1 && anc[b][log]!=-1 && anc[a][log]!=anc[b][log]) a=anc[a][log],b=anc[b][log]; return anc[a][0]; } map<int,int> id[maxn]; void dfs(int now,int fa,int depth) { anc[now][0]=fa;dep[now]=depth; for(int i=0;i<G[now].size();i++) { Edge& e=edges[G[now][i]]; int to=e.from==now?e.to:e.from; id[now][to]=i; if(to==fa || e.w!=0) continue; dfs(to,now,depth+1); } } void preprocess() { dfs(0,-1,0); for(int log=1;log<maxlog;log++) for(int i=0;i<N;i++) if(anc[i][log-1]!=-1) anc[i][log]=anc[anc[i][log-1]][log-1]; for(int i=0;i<edges.size();i++) { Edge& e=edges[i]; if(e.w==0) continue; int lca=LCA(edges[i].from,edges[i].to); Glca[lca].push_back(i); } } int d[maxn][(1<<maxdeg)]; int getcost(int start,int end,int& cover,int& cnt,bool cycle) { cnt++; int ret=0,now=end,fa=start; for(;;) { if(cycle && now==end) ret+=d[now][(1<<G[now].size())-1-(1<<id[now][anc[now][0]])]; else ret+=d[now][(1<<G[now].size())-1-(1<<id[now][fa])-(1<<id[now][anc[now][0]])]; if(anc[now][0]==start) cover=id[start][now]; cnt++; fa=now;now=anc[now][0]; if(now==start) return ret; } } void dp(int now,int fa) { for(int i=0;i<G[now].size();i++) { Edge& e=edges[G[now][i]]; int to=e.from==now?e.to:e.from; if(e.w!=0 || to==fa) continue; dp(to,now); } for(int i=0;i<Glca[now].size();i++) { Edge& e=edges[Glca[now][i]]; int edge1,edge2,cnt=0; if(e.from == now || e.to==now) // cover one tree edge,one back edge { int to=e.from==now?e.to:e.from; edge1=id[now][to]; int cost=getcost(now,to,edge2,cnt,0)+e.w; if(cnt%2==0) continue; d[now][(1<<edge1)|(1<<edge2)]=max(d[now][(1<<edge1)|(1<<edge2)],cost); } else // cover two tree edge { int to1=e.from,to2=e.to; int cost=getcost(now,to1,edge1,cnt,1)+getcost(now,to2,edge2,cnt,1)+e.w;cnt--; if(cnt%2==0) continue; d[now][(1<<edge1)|(1<<edge2)]=max(d[now][(1<<edge1)|(1<<edge2)],cost); } } int all=G[now].size(); vector<int> toadd; for(int i=0;i<(1<<all);i++) if(d[now][i]) toadd.push_back(i); vector<vector<int> > bitnum; bitnum.resize(all+1); for(int i=0;i<(1<<all);i++) bitnum[cntbit(i)].push_back(i); for(int bitcnt=0;bitcnt<all;bitcnt++) for(int i=0;i<bitnum[bitcnt].size();i++) { int x=bitnum[bitcnt][i]; for(int j=0;j<all;j++) if(!(x&(1<<j))) { Edge& e=edges[G[now][j]]; int to=e.from==now?e.to:e.from; if(to==fa || e.w!=0) continue; d[now][x|(1<<j)]=max(d[now][x|(1<<j)],d[now][x]+d[to][(1<<G[to].size())-1]); } for(int j=0;j<toadd.size();j++) if(!(x&toadd[j])) d[now][x|toadd[j]]=max(d[now][x|toadd[j]],d[now][x]+d[now][toadd[j]]); } vector<vector<int> > ().swap(bitnum); vector<int> ().swap(toadd); } int main() { int ans=0; scanf("%d%d",&N,&M); for(int i=0,a,b,c;i<M;i++) { scanf("%d%d%d",&a,&b,&c);a--,b--; ans+=c; edges.push_back((Edge){a,b,c}); G[a].push_back(edges.size()-1); G[b].push_back(edges.size()-1); } preprocess(); dp(0,-1); printf("%d\n",ans-d[0][(1<<G[0].size())-1]); }
沒有留言:
張貼留言