POJ 3270 Cow Sorting 置换群
[cpp]
/*Template*/
/*Poj 3270 Cow Sorting */
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
using namespace std;
const double EPS = 1e-8;
const int MAXN = 10005;
const int INF = 1<<30;
const int MOD = 99991;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
//typedef long long LL;
typedef __int64 LL;
int 易做图(int a,int b){return b?易做图(b,a%b):a;}
int n,tot=0;
int a[MAXN],b[MAXN];
bool flag[MAXN];
struct rpt
{
int cnt; //循环节个数
int min;
}c[MAXN];
/*int find(int x)
{
int l=0,r=n,m;
while(l<r)
{
m=l+(r-l)/2;
if(x==b[m])
return m;
if(x<b[m])
r=m;
else
l=m+1;
}
}*/
void Polya(int x) //DFS找循环节
{
for(int i=0;i<n;i++)
{
if(b[i]==x && flag[i]==false)
{
flag[i]=true;
c[tot].cnt++;
c[tot].min = min(c[tot].min,a[i]);
Polya(a[i]);
}
}
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt,"w",stdout);
cin>>n;
tot=0;
int i,amin=INF,sum=0;
memset(flag,false,sizeof(flag));
for(i=0;i<n;i++)
{
cin>>a[i];
b[i]=a[i];
sum+=a[i];
amin = min(amin,a[i]);
}
sort(b,b+n);
for(i=0;i<n;i++)
{
if(!flag[i])
{
c[tot].cnt=1;
c[tot].min=a[i];
flag[i]=true;
Polya(a[i]);
tot++;
}
} www.zzzyk.com
for(i=0;i<tot;i++)
sum+=min(c[i].min*(c[i].cnt-2),amin*(c[i].cnt+1)+c[i].min);
cout<<sum<<endl;
/*for(i=0;i<tot;i++)
{
cout<<c[i].cnt<<" "<<c[i].min<<endl;
}*/
return 0;
}
无聊贴个代码
置换群用DFS实现,分别记录置换最小值和置换的元素个数就好了
在置换中最小的元素分别和别的元素置换就是最优解了
但注意有可能是整个数组中最小的元素进行交换,进行一次比较取最小值就行了
知道是置换但是后面的那个坑点还真没想到呢...
看题解才AC的捂脸...
补充：软件开发 , C++ ,
