題目鏈接

http://codeforces.com/problemset/problem/1027/D

這道題目的入手點(diǎn)就是圖的特點(diǎn)。圖的輸入形式是 第 i 個(gè)點(diǎn)的后繼是a[ i ]，且只有一個(gè),a[ i ]的范圍是從1到n。所以圖中一定存在環(huán)，并且環(huán)和環(huán)之間不可能公用一條邊（如果共用一條邊，那么某個(gè)點(diǎn)會(huì)有兩個(gè)后繼）。

因此這道題目就是用dfs找環(huán)，然后通過(guò)回溯求出環(huán)上定點(diǎn)的權(quán)值最小值。

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<string> #include<vector> #define DEBUG(x) cout<<#x<<" = "<<x<<endl using namespace std; const int MAXN=2e5+10; int N; vector<int>G[MAXN]; int cost[MAXN]; int vis[MAXN]; int cv=-1; int mc; int csum=0; void dfs(int u) {if(vis[u]==1){cv=u;mc=cost[u];return;}vis[u]=1;for(int i=0;i<G[u].size() ;i++ ){int v=G[u][i];dfs(v);}if(cv!=-1){if(cv==u){csum+=mc;cv=-1;}else mc=min(mc,cost[u]);} } int main() { // freopen("in.txt","r",stdin);scanf("%d",&N);for(int i=1;i<=N ;i++ ){scanf("%d",&cost[i]);}for(int i=1;i<=N ;i++ ){int e;scanf("%d",&e);G[i].push_back(e);}for(int u=1;u<=N ;u++ ){if(vis[u]==0){dfs(u);cv=-1;}}printf("%d\n",csum); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/MalcolmMeng/p/9528045.html

總結(jié)

以上是生活随笔為你收集整理的codeforces1027D的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。