SPFA的两个优化(转)

2010年8月26日 08:36

转自:http://aceeca1.frostbytez.com/index.php/archives/SPFA%E4%BC%98%E5%8C%96

  SLF:Small Label First 策略。
实现方法是,设队首元素为 $i$,队列中要加入节点 $j$,在 $d_j \le d_i$ 时加到队首而不是队尾,否则和普通的 SPFA 一样加到队尾。

  LLL:Large Label Last 策略。
实现方法是,设队列 $Q$ 中的队首元素为 $i$,距离标号的平均值为 $\overline d = \frac {\sum_{j \in Q} d_j }{\left| Q \right|}$,每次出队时,若 $d_i > \overline d$,把 $i$ 移到队列末尾,如此反复,直到找到一个 $i$ 使 $d_i \le \overline d$,将其出队。

评论(0) 阅读(3050)

POJ 3660 传递闭包 warshall算法

2010年8月16日 19:31

  初始化为-1,计算传递闭包过程中赢记为1,输记为0,最后检查传递闭包中无-1的行数或列数。

 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int adj[101][101];
int tc[101][101];

int main()
{
    //freopen("in.txt","r",stdin);
    int n,m,v,w,i,s,t,ans;
    scanf("%d%d",&n,&m);
    memset(adj,-1,sizeof(adj));
    for(i=1; i<=n; i++) adj[i][i]=1;
    for(i=1; i<=m; i++)
    {
        scanf("%d%d",&v,&w);
        adj[v][w]=1;
    }

    for(s=1; s<=n; s++)
        for(t=1; t<=n; t++)
            tc[s][t]=adj[s][t];

    for(i=1;i<=n;i++)
        for(s=1;s<=n;s++)
            if(tc[s][i]>0)
                for(t=1;t<=n;t++)
                    if(tc[i][t]>0) {tc[s][t]=1;tc[t][s]=0;}

//    for(s=1; s<=n; s++)
//    {
//        for(t=1; t<=n; t++)
//            printf("%3d ",tc[s][t]);
//        cout<<endl;
//    }

    ans=n;
    for(s=1; s<=n; s++)
        for(t=1; t<=n; t++)
            if(tc[s][t]==-1)
            {
                ans--;
                break;
            }
    printf("%d\n",ans);
    return 0;
}

 

评论(0) 阅读(1457)

poj 3270 置换,循环节

2010年8月10日 23:11

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);
}

 

评论(0) 阅读(1265)

Burnside引理 Polya定理

2010年7月31日 03:36

Burnside引理:

设置换群作用于有限集合上,则在G作用下的等价类的数目为:

 

其中(g)为g在上的不动点个数,即满足g(a)=a的个数。

 Polya定理:

设G是p个对象的一个置换群,用k种颜色涂染这p个对象,在置换群作用下的不同的染色方案数为

其中m(f)为置换f的循环节数。

评论(0) 阅读(3117)

archlinux 2010.05 安装笔记

2010年7月25日 17:08

刻盘启动

root 无密码

# /arch/setup

分区 选择软件包 安装软件包

配置系统

/etc/rc.conf: 语言(可稍后设置免得命令行下方块) 网络部分

/etc/resolv.conf: 设置dns服务器

/etc/locale.gen: 反注释zh_CN开头的四行

选定pacman镜像 设定root密码 安装grub

就可以重启了

 

ping -c www.google.com

网络不通的话 再配置/etc/rc.conf /etc/resolv.conf

开启ipv6

modprobe ipv6

新建用户

useradd -m -G users,audio,lp,optical,storage,video,wheel,power -s /bin/bash yourusername

passwd yourusername

在/etc/pacman.conf文件里,最后添加两行

[archlinuxfr]
Server = http://repo.archlinux.fr/$arch

更新系统

pacman -Syu

安装yaourt:  pacman -S yaourt

安装sudo: pacman -S sudo

然后 visudo 加入 YOURNAME ALL=(ALL) NOPASSWD: SETENV: ALL 就不用输密码了

安装alsa(参照wiki)

安装ati显卡驱动

pacman -S xf86-video-ati libgl ati-dri

安装xorg,生成 xorg.conf 配置文件

pacman -S xorg

Xorg -configure

(测试见官方指南)

cp /root/xorg.conf.new /etc/X11/xorg.conf

安装字体

pacman -S ttf-dejavu ttf-bitstream-vera

pacman -S wqy-zenhei

yaourt ttf-ms-fonts wqy-microhei

安装gdm : pacman -S gdm 添加到rc.conf 的 DEAMONS 保证顺序(dbus hal gdm)

安装gnome

pacman -S gnome gnome-extra gnome-system-tools

pacman -S hal dbus

DEAMONS 里添加 hal , MODULES里添加 fuse

基本搞定。。。待续

评论(1) 阅读(5720)