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].to=y;e[tot].next=head[x];head[x]=tot++; } void find_circle(int x,int pre) {vis[x]=1;for (int i=head[x];~i;i=e[i].next){if ((i^1)==pre) continue;if (vis[e[i].to]){x1=x;//斷口的左側 x2=e[i].to;//斷口另一側 E=i;//斷開的邊 continue;}find_circle(e[i].to,i);} } void dfs(int x,int pre) {dp[x][0]=0;dp[x][1]=fun[x];for (int i=head[x];~i;i=e[i].next){if ((i^1)==pre) continue;if (i==E || (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 i=1;i<=n;i++){scanf("%d%d",&a,&b);add(i,b);add(b,i);fun[i]=a;}long long ans=0;for (int i=1;i<=n;i++){if (vis[i]) continue;find_circle(i,-2);dfs(x1,-1);long long temp=dp[x1][0];dfs(x2,-1);temp=max(temp,dp[x2][0]);ans+=temp; }printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的P2607 [ZJOI2008]骑士的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。