1119: [POI2009]SLO
stupid_lulu
posted @ 2013年3月19日 16:32
in poi
, 1195 阅读
也不算什么难题。。求出所有的置换,再在每个置换中讨论,ans=min(用置换中最小值换所有元素的代价;有全局最小值换置换中最小元素,用全局最小元素换所有元素,再将最小元素换回来),详见代码。。
#include<cstdio> #include<cstring> typedef long long ll; bool can[1000001]; ll minc=~0u>>1,s=0,mins,sum,ans=0; int cost[1000001],g[1000001]; int n,a[1000001],b[1000001],w[1000001],fb[1000001]; ll min(ll a,ll b){return a<b? a:b;} void done(int i){ //printf("%d\n",i); s=0; g[++s]=i; mins=~0u>>1; can[i]=false; mins=min(mins,cost[i]); sum=cost[i]; int j=a[i]; while (j!=i){ g[++s]=j; can[j]=false; mins=min(mins,cost[j]); sum+=cost[j]; j=a[j]; } //printf("%d %d %d %d\n",s,sum,mins,minc); ans+=min(sum+(s-2)*mins,sum+minc*(s+1)+mins); } int main(){ scanf("%d",&n); memset(can,true,sizeof(can)); for (int i=1;i<=n;i++) scanf("%d",&w[i]); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) scanf("%d",&b[i]); for (int i=1;i<=n;i++) fb[b[i]]=i; for (int i=1;i<=n;i++) a[i]=fb[a[i]]; for (int i=1;i<=n;i++){ cost[fb[i]]=w[i]; minc=min(minc,w[i]); } //for (int i=1;i<=n;i++) printf("a[%d]=%d cost[%d]=%d\n",i,a[i],i,cost[i]); for (int i=1;i<=n;i++){ if (can[i]) done(i); } printf("%lld\n",ans); }