でんしん
6731 ワード
テーマの大意
n個の点、各点の出度はいずれも1の有向図である.j->kをj->lに変更し、c[j]の代価を払うことができます.最小の代価を求めて、有向図を1つのリングにします.
欲張る
問題をいくつかのエッジを削除し、各エッジを削除するのに代価があり、最小の代価は各連結ブロックがチェーンであるように記述します(このようにしてループを接続することができます).一つの点にk個の入度があれば、少なくともk-1個は削除される.木の場合、最大の代価を残す入辺に貪欲だ.環の上の少なくとも1つの辺は削除して、もう一度討論すればいいです.特判初期のすべての点が1つのリングにつながっている場合に注意してください.
n個の点、各点の出度はいずれも1の有向図である.j->kをj->lに変更し、c[j]の代価を払うことができます.最小の代価を求めて、有向図を1つのリングにします.
欲張る
問題をいくつかのエッジを削除し、各エッジを削除するのに代価があり、最小の代価は各連結ブロックがチェーンであるように記述します(このようにしてループを接続することができます).一つの点にk個の入度があれば、少なくともk-1個は削除される.木の場合、最大の代価を残す入辺に貪欲だ.環の上の少なくとも1つの辺は削除して、もう一度討論すればいいです.特判初期のすべての点が1つのリングにつながっている場合に注意してください.
#include
#include
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxn=100000+10,inf=2000000000;
int a[maxn],b[maxn],c[maxn],g[maxn],p[maxn],belong[maxn];
int h[maxn],go[maxn],nxt[maxn];
int h2[maxn],g2[maxn],n2[maxn];
ll f[maxn];
bool pd[maxn],bz[maxn];
int i,j,k,l,t,n,m,tot,top,cnt,wdc,mi;
ll ans,sum,num;
bool czy;
int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
void add(int x,int y){
go[++tot]=y;
nxt[tot]=h[x];
h[x]=tot;
}
void add2(int x,int y){
g2[++cnt]=y;
n2[cnt]=h2[x];
h2[x]=cnt;
}
void dfs(int x){
if (pd[a[x]]){
belong[x]=++tot;
bz[x]=1;
wdc=a[x];
return;
}
if (belong[a[x]]){
belong[x]=belong[a[x]];
return;
}
pd[x]=1;
dfs(a[x]);
belong[x]=belong[a[x]];
if (wdc) bz[x]=1;
if (x==wdc) wdc=0;
pd[x]=0;
}
void dg(int x){
int t=h[x],mx=0;
ll l=0;
while (t){
dg(go[t]);
mx=max(mx,c[go[t]]);
l+=(ll)c[go[t]];
t=nxt[t];
}
ans+=(ll)l-mx;
}
void work(int x){
top=0;
t=h2[x];
while (t){
p[++top]=g2[t];
t=n2[t];
}
fo(i,1,top)
if (!bz[p[i]]&&bz[a[p[i]]]){
dg(p[i]);
f[a[p[i]]]+=(ll)c[p[i]];
g[a[p[i]]]=max(g[a[p[i]]],c[p[i]]);
}
fo(i,1,top)
if (bz[p[i]]) b[a[p[i]]]=c[p[i]];
mi=inf;
fo(i,1,top)
if (bz[p[i]]) mi=min(mi,c[p[i]]);
sum=0;
fo(i,1,top)
if (bz[p[i]]) sum+=f[p[i]];
num=sum+mi;
sum=0;
fo(i,1,top)
if (bz[p[i]]) sum+=min(f[p[i]],f[p[i]]-g[p[i]]+(ll)b[p[i]]);
fo(i,1,top)
if (bz[p[i]]){
sum-=min(f[p[i]],f[p[i]]-g[p[i]]+(ll)b[p[i]]);
num=min(num,sum+f[p[i]]-g[p[i]]+(ll)b[p[i]]);
sum+=min(f[p[i]],f[p[i]]-g[p[i]]+(ll)b[p[i]]);
}
ans+=num;
}
int main(){
freopen("telegraph.in","r",stdin);freopen("telegraph.out","w",stdout);
n=read();
fo(i,1,n){
a[i]=read();c[i]=read();
add(a[i],i);
}
tot=0;
fo(i,1,n)
if (!belong[i]){
wdc=0;
dfs(i);
}
if (tot==1){
czy=1;
fo(i,1,n)
if (!bz[i]){
czy=0;
break;
}
if (czy){
printf("0
");
return 0;
}
}
fo(i,1,n) add2(belong[i],i);
fo(wdc,1,tot) work(wdc);
printf("%lld
",ans);
}