BZOJ1119 [POI2009]SLO

时间：2023-06-02 15:37:00 optex激光位移传感器cd3

一看问题就像置换一样。……找到循环节，然后假设循环节的长度是l，如果只在循环中交换，每个数字必须至少计入一次成本，总共有2*(l-1)答案中包含了个数，显然除了每个数至少剩下一次l-最小的答案是最好的两次

然而，这可能不是这个循环中最好的。我们可以强行拉一个不在循环中的数字，所以我们必须让所有数字中最小的和循环中最小的交换，拉所有数字中最小的，然后让所有数字中最小的都包含在答案中l-两次，然后在这个数字和循环节中更换最小的

对每个循环节把这两种方法取min，加入答案

#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAXN 1000010 #define MAXM 1010 #define INF 1000000000 #define MOD 1000000007 #define eps 1e-8 #define ll long long int n; int a[MAXN],b[MAXN],w[MAXN]; int p[MAXN]; bool vis[MAXN]; ll ans; int MN=INF; int main(){  int i;  scanf("%d",&n);  for(i=1;i<=n;i  ){   scanf("%d",&w[i]);   MN=min(MN,w[i]);  }  for(i=1;i<=n;i  ){   scanf("%d",&a[i]);   p[a[i]]=i;  }  for(i=1;i<=n;i  ){   scanf("%d",&b[i]);  }  for(i=1;i<=n;i  ){   if(!vis[i]&&a[i]!vis[i]&&a[i]!=b[i]){    int x=i;    int mn=INF;    int siz=0;    ll sum=0;    while(!vis[x]){     vis[x]=1;     sum =w[a[x]];     siz  ;     if(w[a[x]]<=mn){      mn=w[a[x]];     }     x=p[b[x]];    }    ans =min(sum (ll)mn*(siz-2),sum mn (ll)MN*(siz 1));   }  }  printf("%lld\n",ans);  return 0; }  /*  */

锐单商城拥有海量元器件数据手册、IC替代型号，打造电子元器件IC百科大全！

BZOJ1119 [POI2009]SLO

相关文章