电报
题目大意
n个点，每个点出度均为1的有向图。
你可以将j->k改成j->l，代价为c[j]。
求最小代价，使得有向图变成一个环。
贪心
我们把问题描述成删去若干条边，删除每条边都有代价，最小代价使得每个联通块都是一条链（这样才能连成环）。
假如一个点有k个入度，至少k-1个要被删掉。
对于树的情况贪心保留最大代价的入边。
环上至少一条边要删去，再讨论一下即可。
注意特判初始所有点连成一个环的情况。
#include<cstdio>
#include<algorithm>
#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\n");return 0;}}fo(i,1,n) add2(belong[i],i);fo(wdc,1,tot) work(wdc);printf("%lld\n",ans);
}
电报
题目大意
n个点，每个点出度均为1的有向图。
你可以将j->k改成j->l，代价为c[j]。
求最小代价，使得有向图变成一个环。
贪心
我们把问题描述成删去若干条边，删除每条边都有代价，最小代价使得每个联通块都是一条链（这样才能连成环）。
假如一个点有k个入度，至少k-1个要被删掉。
对于树的情况贪心保留最大代价的入边。
环上至少一条边要删去，再讨论一下即可。
注意特判初始所有点连成一个环的情况。
#include<cstdio>
#include<algorithm>
#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\n");return 0;}}fo(i,1,n) add2(belong[i],i);fo(wdc,1,tot) work(wdc);printf("%lld\n",ans);
}