转自:http://aceeca1.frostbytez.com/index.php/archives/SPFA%E4%BC%98%E5%8C%96
SLF：Small Label First 策略。
实现方法是，设队首元素为 ，队列中要加入节点
，在
时加到队首而不是队尾，否则和普通的 SPFA 一样加到队尾。
LLL：Large Label Last 策略。
实现方法是，设队列 中的队首元素为
，距离标号的平均值为
，每次出队时，若
，把
移到队列末尾，如此反复，直到找到一个
使
，将其出队。
初始化为-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;
}
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);
}
Burnside引理:
设置换群作用于有限集合
上，则在G作用下的等价类的数目为：
其中(g)为g在上的不动点个数，即满足g(a)=a的个数。
Polya定理:
设G是p个对象的一个置换群，用k种颜色涂染这p个对象，在置换群作用下的不同的染色方案数为
其中m(f)为置换f的循环节数。
刻盘启动
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
基本搞定。。。待续
