网站开发自学难吗,网站免费推广策划方案,微信公众平台微网站怎么做,帮忙做宴会的网站题目链接
点击打开链接
题目解法
好神仙的题啊#xff01;#xff01;#xff01; 首先一个合法的选路径方案等价于没有偶环出现 我们先判掉和树边能组成偶环的非树边 然后考虑一个结论是#xff1a;如果有一条边被两个偶环都经过了一次#xff0c;那么这个方案不合法 …题目链接
点击打开链接
题目解法
好神仙的题啊 首先一个合法的选路径方案等价于没有偶环出现 我们先判掉和树边能组成偶环的非树边 然后考虑一个结论是如果有一条边被两个偶环都经过了一次那么这个方案不合法 为什么考虑把这两条路径的交去掉这两条路径的并剩下的是一个偶环
考虑把删边变为加边需要加上权值和最大的边使得方案合法 可以发现每个点的度数很小于是考虑状压 令 f u , S f_{u,S} fu,S 为在 u u u 的子树中 u u u 的儿子集合 S S S 不考虑在内的方案数 这样只需要枚举每一条 l c a ( x , y ) u lca(x,y)u lca(x,y)u 的非树边然后转移即可 时间复杂度 O ( 2 10 m ) O(2^{10}m) O(210m)
#include bits/stdc.h
using namespace std;
const int N1100,M5100;
int n,m,dp[N][110],depth[N],fa[N];
int e[N1],ne[N1],h[N],idx;
int id[N][N],rv[N][20];
struct Node{ int x,y,z;}E[M];
vectorNode qry[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
void add(int x,int y){ e[idx]y,ne[idx]h[x],h[x]idx;}
void dfs(int u){depth[u]depth[fa[u]]1;for(int ih[u];~i;ine[i]) if(e[i]!fa[u]) fa[e[i]]u,dfs(e[i]);
}
int get_lca(int x,int y){if(depth[x]depth[y]) swap(x,y);while(depth[y]depth[x]) yfa[y];while(x!y) xfa[x],yfa[y];return x;
}
void dfs2(int u){int cnt0;for(int ih[u];~i;ine[i]) if(e[i]!fa[u]){id[u][e[i]]1cnt,rv[u][cnt]e[i],cnt;dfs2(e[i]);}for(int S0;S1cnt;S)for(int i0;icnt;i) if(!(Si1)) dp[u][S]dp[rv[u][i]][0];for(Node t:qry[u]){int xt.x,yt.y,rest.z,exc0;if(x!u){resdp[x][0];while(fa[x]!u) resdp[fa[x]][id[fa[x]][x]],xfa[x];exc|id[fa[x]][x];}if(y!u){resdp[y][0];while(fa[y]!u) resdp[fa[y]][id[fa[y]][y]],yfa[y];exc|id[fa[y]][y];}for(int S0;S1cnt;S) if((S|exc)Sexc) dp[u][S]max(dp[u][S],dp[u][Sexc]res);}
}
int main(){nread(),mread();memset(h,-1,sizeof(h));int cnt0;for(int i1;im;i){int xread(),yread(),zread();if(!z) add(x,y),add(y,x);else E[cnt]{x,y,z};}dfs(1);int tot0;for(int i1;icnt;i){int lcaget_lca(E[i].x,E[i].y);totE[i].z;if(~(depth[E[i].x]depth[E[i].y]-2*depth[lca])1) qry[lca].push_back(E[i]);}dfs2(1);printf(%d\n,tot-dp[1][0]);fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
