P8269 [USACO22OPEN] Visits S
首先，每頭牛牛都只有一個拜訪對象，所以如果考慮圖論建模的話，相當于每個點出度都是 1。這相當于圖是個基環樹森林（注意不只有一棵基環樹），而且每個基環樹都是內向基環樹。
而且我們注意到有個特殊點，建出來的圖是很多個環，就更加堅定了我們往基環樹那塊考慮的想法。我們把一個基環樹的圖畫出來：
（很像你媽媽的鑰匙串有木有）
然后轉換一下原題的題意。既然決定圖論建模了，那原題的 \(a_i\) 就相當于 \(i -> a_i\) 建邊，邊權是 \(v_i\)。至于排列，其實就是個行動順序表，問我們如何安排行動順序會讓最終貢獻最大。
對于不在環里的節點，顯然不斷讓入度為 0 的點行動是更優的。首先一個點出去拜訪以后就不可能回來，其次對于下圖的情況，先讓連向 \(v\) 的點拜訪 \(v\)，然后 \(v\) 再去拜訪別人，比先讓 \(v\) 拜訪別人，多了 \(w_1+w_2+\cdots+w_k\) 的貢獻。
所以對于環外的部分，直接貪心地進行拓撲排序，累加邊權即可。
這樣我們就只剩下基環樹森林里僅存的幾個環了。
對于一個環來說，顯然你是注定無法讓它們都能統計貢獻的。你可以自己在腦子里想象這些點逐個移動到它的拜訪點，然后你就會發現注定有一個點的拜訪點已經挪走了。
剛才那一通模擬后你還能得到，如果這個環有 \(m\) 條邊，那你一定可以統計 \(m-1\) 條邊的貢獻，而且這樣一定是比 \(m-2\) 條邊或者更往下的情況更優。那些情況一定是如下的圖所展示的：
也就是 1->2,2->3,4->5,3->4,5->1。那你一定不如 1->2,2->3,3->4,4->5,5->1 或是 4->5,5->1,1->2,2->3,3->4 優。
既然這樣，那就相當于我們要在這個環上舍棄一條邊。貪心一下，我們舍棄這個環上的最小邊。這棵基環樹的貢獻就是它邊權的總和減掉被舍棄的邊之邊權。
注意原圖里有多個基環樹，也會有多個環，要將它們被舍棄的邊求一個 sum，然后統一減掉。
代碼：
P8269
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<48){
if(c=='-') f=-1;
c=getchar();
}
while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int N=1e5+5;
const int inf=1e16;
int n,h[N],tot,in[N],p[N],W[N],vis[N],mi=inf;
queue<int> q;
struct Nahida{
int u,v,w,nxt;
}e[N];
inline void add(int u,int v,int w){
e[++tot]={u,v,w,h[u]};h[u]=tot;in[v]++;
}
inline void dfs(int u){
vis[u]=1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
mi=min(mi,e[i].w);
if(vis[v]) continue;
dfs(v);
}
}
signed main(){
n=read();
int sum=0;
for(int i=1;i<=n;i++){
int v=read(),w=read();
p[i]=v,W[i]=w;
sum+=W[i];
add(i,v,w);
}
for(int i=1;i<=n;i++){
if(!in[i]){
q.push(i);
}
}
int ans=0;
while(!q.empty()){
int u=q.front();q.pop();
int v=p[u];
if(in[v]){
in[v]--;
if(!in[v]){
q.push(v);
}
}
}
int misum=0;
for(int i=1;i<=n;i++){
if(in[i]&&!vis[i]){
mi=inf;
dfs(i);
misum+=mi;
}
}
ans=sum-misum;
printf("%lld",ans);
return 0;
}
浙公網安備 33010602011771號