正題

評(píng)測(cè)記錄：https://www.luogu.org/recordnew/lists?uid=52918&pid=P3651

---

題目大意

有n個(gè)點(diǎn)，有n條有向邊，改變每一個(gè)點(diǎn)的出邊需要價(jià)值不同，求最小價(jià)值使所以邊的頭尾都可以相互到達(dá)。

---

解題思路

首先我們可以找出所以的環(huán)，然后將環(huán)外的點(diǎn)加入他連接的環(huán)，最后枚舉每個(gè)環(huán)的斷開(kāi)點(diǎn)，找到最優(yōu)的一個(gè)地方斷開(kāi)。

---

code

#include<cstdio> #include<algorithm> #define N 100010 #define ll long long using namespace std; int n,l[N],c[N],mark[N]; ll ans,max1[N],max2[N]; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&l[i],&c[i]);}for(int i=1;i<=n;i++)//找環(huán){if(mark[i]!=0) continue;int j=i;while(mark[j]==0){mark[j]=i;j=l[j];}if(mark[j]==i){int num=0;while(mark[j]!=-1){mark[j]=-1;j=l[j];num++;}//標(biāo)記環(huán)if(num==n){printf("0");return 0;}//特判}}for(int i=1;i<=n;i++){ans+=c[i];max1[l[i]]=max(max1[l[i]],(ll)c[i]);if(mark[i]!=-1)max2[l[i]]=max(max2[l[i]],(ll)c[i]);}for(int i=1;i<=n;i++) ans-=max1[i];//計(jì)算環(huán)外價(jià)值for(int i=1;i<=n;i++){if (mark[i]!=-1) continue;int j=i;ll m=10000000000ll;while(mark[j]==-1){m=min(m,max1[j]-max2[j]);//最小的地方斷開(kāi)mark[j]=-2;j=l[j];}ans+=m;}//計(jì)算斷開(kāi)價(jià)值printf("%lld",ans); }

總結(jié)

以上是生活随笔為你收集整理的P3651-展翅翱翔之时【贪心,环套树】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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