題目

一個游樂場（無向圖），每個景點（點）都有一定的開心值（價值），一個點只能游玩一次。然后可以從任何一個點出發，求可以游玩的最多項目（連通分量）和可以獲得的最大價值。

輸入

5
3
4
5
8
10
5
1 2
1 3
2 5
3 4
4 5

輸出

5
30

---

解題思路

這道題有點坑

一個游樂設施對一個人只開放一次

也就是說他可以往回走只不過不能再玩一次這個項目而已，但是如果我們不封路的話就會死循環，所以我們可以把他可以到達的所有地方都加上，也就是我題目上的求連通分量了。

---

代碼

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int walk[201],w[201][201],a[201],mm,md,n,m,x,y,money,dep; void dfs(int x) {walk[x]=true;//封路dep+=1;//可以到達money+=a[x];//加上該價格for (int i=1;i<=n;i++){if (!walk[i] && w[x][i])//如果可以通行{w[x][i]=false;w[i][x]=false;//封閉路線dfs(i);//搜索}} } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}scanf("%d",&m);for (int i=1;i<=m;i++){scanf("%d%d",&x,&y);w[x][y]=true;w[y][x]=true;}//以上↑為輸入for (int i=1;i<=n;i++){dep=0;money=0;dfs(i);//搜索md=max(md,dep);mm=max(mm,money);}printf("%d\n%d",md,mm);//輸出 }

總結

以上是生活随笔為你收集整理的ssl1776-游乐场【图论,深搜】的全部內容，希望文章能夠幫你解決所遇到的問題。

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