Burnside引理 Polya定理
POJ 3660 传递闭包 warshall算法

poj 3270 置换,循环节

scturtle posted @ 2010年8月10日 23:11 in algorithm , 1475 阅读

firefox崩溃了,害我打的字儿没了……

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int cow[10001];
int scow[10001];
int pos[100001];
bool hasg[10001];

int main()
{
    freopen("in","r",stdin);
    int n,allmin,gsum,glen,gmin,tans,ans;
    int i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",cow+i);
        scow[i]=cow[i];
    }
    sort(scow,scow+n);
    allmin=scow[0];
    for(i=0;i<n;i++)
        pos[scow[i]]=i;

    memset(hasg,0,sizeof(bool)*n);

    ans=0;
    for(int i=0;i<n;i++)
    {
        if(!hasg[i])//new group
        {
            hasg[i]=1;
            gsum=cow[i];glen=1;gmin=cow[i];
            j=i;
            while(!hasg[pos[cow[j]]])
            {
                j=pos[cow[j]];
                hasg[j]=1;
                gsum+=cow[j];
                ++glen;
                if(gmin>cow[j]) gmin=cow[j];
            }

            tans=min(gsum+(glen-2)*gmin,
                    gsum+gmin+(glen+1)*allmin);
            ans+=tans;
        }
    }
    printf("%d",ans);
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter