网站建设万首先金手指12,wordpress聚合页面,动易 网站首页,免费海报制作appP2607 [ZJOI2008]骑士
题意#xff1a;
n个点n个边#xff0c;每个点都有权值#xff0c;相邻的点不能同时选择#xff0c;问如何选择能使得权值最大
题解#xff1a;
这个题很有P1352 没有上司的舞会这个题的感觉#xff0c;唯一的区别是那个题保证是树#xff0c;…P2607 [ZJOI2008]骑士
题意
n个点n个边每个点都有权值相邻的点不能同时选择问如何选择能使得权值最大
题解
这个题很有P1352 没有上司的舞会这个题的感觉唯一的区别是那个题保证是树而本题肯定不是树而是基环树 也就是本题中每一个连通块有且只有一个环所以我们找到这个环并剪短这样就形成一颗树断口的两个端点x和y我们认为分开 对于一棵树这不就是P1352 没有上司的舞会这个题吗
注意有可能存在很多连通块记得所有连通块的答案要累加
代码
#include cstdio
#include iostream
#include cstring
#define maxn 1000010
using namespace std;
int fun[maxn],a,b;
long long dp[maxn][2];
struct node
{int next,to,v;
}e[2000010];
int head[1000010],vis[maxn],n,s,tot,x1,x2,E;
void add(int x,int y)
{e[tot].toy;e[tot].nexthead[x];head[x]tot;
}
void find_circle(int x,int pre)
{vis[x]1;for (int ihead[x];~i;ie[i].next){if ((i^1)pre) continue;if (vis[e[i].to]){x1x;//断口的左侧 x2e[i].to;//断口另一侧 Ei;//断开的边 continue;}find_circle(e[i].to,i);}
}
void dfs(int x,int pre)
{dp[x][0]0;dp[x][1]fun[x];for (int ihead[x];~i;ie[i].next){if ((i^1)pre) continue;if (iE || (i^1)E)continue;dfs(e[i].to,i);dp[x][1]dp[e[i].to][0];dp[x][0]max(dp[e[i].to][1],dp[e[i].to][0]);}
}
int main()
{memset(head,-1,sizeof head);scanf(%d,n);for (int i1;in;i){scanf(%d%d,a,b);add(i,b);add(b,i);fun[i]a;}long long ans0;for (int i1;in;i){if (vis[i]) continue;find_circle(i,-2);dfs(x1,-1);long long tempdp[x1][0];dfs(x2,-1);tempmax(temp,dp[x2][0]);anstemp; }printf(%lld,ans);
}
