当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,