简洁起见，我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。

　　我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

----------------

我实现的spfa 算法也是来自上面，但是速度有点慢，是在check  v是否在队列中，之前没有用hash，后来用hash就快了，但是还是卡在第九个测试样例上。 最后改成临接表的形式 ， 0.1s 刷过

//int graph[N][N];

//pair 第一个是点 ，第二个是边的权值
vector< vector < pair<int ,int > > > graph; 临接表 。。。。

大概的题意是： 给定一个序列 1 。。N ，假设全集为U那么存在多少种情况 ： 两个子集A B其中A∩B=∅ ，A∪B=U ，A元素的和== B元素的和。

开始写了个递归，枚举，提交超时：void work(int deep,int start)

但是提交后，在13 这个测试样例超时，然后就在想怎么剪枝

• 之前在判断放棋子是否冲突的时候，是在放的位置往四个方向拓展，如果没有冲突就放 。现在改进为直接判断 和之前放置的棋子是否冲突。
• 对称剪枝，这个在百度之后才知道的 ，这个是关键，直接砍掉一般的时间

/*
ID:fuxiang2
PROG: checker
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <list>
#include <algorithm>
#include <set>
#include <cmath>
#include <cstring>
#include <cstdlib>
 
#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define EACH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
 
using namespace std;
ofstream fout ("checker.out");
ifstream fin ("checker.in");
 
const int N = 14;
int graph[N][N];
int n;
int ans ;
int result ;
// 类似八皇后问题
int used[N];
//list <int >path;
int path[N];
 
bool isok(int x,int y)
{
    if(x >=1 && x<= n && y >= 1 && y <= n)
        return true;
    return false;
}
int dir[4][2] = { {-1,-1} ,{-1,1},{1,1},{1,-1} };
bool check(int x,int y )
{
    int nx = x;
    int ny = y;
    int n = x -1;
    if(n == 0)
        return true;
 
    FOR_1(i,1,n){
        nx = i;
        ny = path[i];
        if( abs(x-nx) == abs(y-ny))
            return false;
    }
    return true;
 
    //FOR_1(i,0,3){
    //    nx = x +  dir[i][0];
    //    ny = y +  dir[i][1];
    //    while(isok(nx,ny) ){
    //        if(graph[nx][ny] == 1)
    //            return false;
    //        nx += dir[i][0];
    //        ny += dir[i][1];
    //    }
    //}
    //return true;
 
}
 
void place(int col,int row)
{
    graph[row][col] = 1;
    if(row== n){
        ans ++;
        if(result + ans <= 3){
            //list<int >::iterator iter = path.begin();
            //fout<< *iter;
            fout<<path[1];
            //for(iter ++ ; iter != path.end() ; iter ++)
            for(int i = 2 ; i <= n ; i ++)
                fout <<" "<< path[i];
            fout<<endl;
        }
        graph[row][col] = 0;
        return ;
    }
    FOR_1(i,1,n){
        if(used[i] == 0 && check(row+1,i ) == true )
        {
            path[row+1] = i;//path.push_back(i);
            used[i] = 1;
            place(i,row+1);
            //path.pop_back();
            used[i] = 0;
        }
    }
    graph[row][col] = 0;
 
}
void work(int n)
{
    result = 0;
 
    FOR_1(j,1,n/2) {// 列
        path[1] = j;//path.push_back(j);
        used[j]  = 1;
        place(j,1);
        //path.pop_back();
        used[j] = 0;
    }
    int re =  ans;
    result = ans;
    if(re <3 || n%2 == 1){
        int t = n/2 + 1;
        ans = 0;
        path[1] = t;//path.push_back(j);
        used[t]  = 1;
        place(t,1);
 
    }
    if( n% 2 == 1)
        result += re + ans;
    else
        result += re;
}
 
int main()
{
    fin>>n;
    work(n);
    fout<< result<<endl;
    return 0;
 
}


原始博客地址： http://www.fuxiang90.com/2012/07/usaco1-5-checker-challenge/

和之前的clock 很像，标记状态hash 判重，遍历所有的情况就可以。

满足 a1 + a2 + …aK >= 0 (k = 1 2 … 2n ) 这个的条件的个数 为

证明：令An 为其中可以接受的系列Bn 为不可接受的系列

那么 An + Bn = .An 是我们要求的，我们可以通过求出Bn来得到An 。

我们假设存在 一个最小的K 使得a1 + a2 +…+ak 为负，那么 可以肯定 a1+…+ak-1 = 0,且ak = -1.k 为奇整数。

对于每一种不符合条件的序列a1 + a2 +…+ak +…+a2n 将a1 a2 ak 都用-a1 –a2 –ak 代替，那么新的数列

a1’ a2’ … a2n’ 就有 n+1 个 +1 和 n-1 个 –1  。即每一种 不符合条件的 数列经过上述过程都将变为

  n+1 个 +1 和 n-1 个 –1   的排列 。那么现在要证明 n+1 个 +1 和 n-1 个 –1   的排列数 == Bn

n+1 个 +1 和 n-1 个 –1   的排列 肯定存在一个 最小的k 使得 a1 + a2 + …aK <  0   而将这部分也用-a1 –a2 –ak 代替 ，也就成为了 n个1 和n个-1 构成的2n项 a1,a2….a2n   而Bn的排列就好求了

==》 

应用： 有2n个人要去剧场，入场5角，有n个人有1元，n个人有5角，剧场的卖票处刚开始没有零钱，那么存在多少种队列方式。

粗体的证明 ，我感觉有些牵强，呵呵 大家有好的方法，请指正。

我独立博客地址 http://www.fuxiang90.me/?p=286

ubuntu网络连接显示”设备未托管”解决方法

之前就遇到过这个问题，一直都没有去解决，这次是因为试着用虚拟机宽带连接进行上网设置，没有成功，后来导致NAT 也不行，并且发现 网络连接显示”设备未托管” , 一直以为是虚拟机的网络设置的问题，后来证实：之前宽带连接我设置了 pppoeconf ，因为pppoe修改了dns导致的。

造成问题的原因：

Linux里面有两套管理网络连接的方案：
1、/etc/network/interfaces（/etc/init.d/networking）
2、Network-Manager

两套方案是冲突的，不能同时共存。
第一个方案适用于没有X的环境，如：服务器；或者那些完全不需要改动连接的场合。
第二套方案使用于有桌面的环境，特别是笔记本，搬来搬去，网络连接情况随时会变的。

－－－－－－－－－－－－－
他们两个为了避免冲突，又能共享配置，就有了下面的解决方案：
1、当Network-Manager发现/etc/network/interfaces被改动的时候，则关闭自己（显示为未托管），除非managed设置成真。
2、当managed设置成真时，/etc/network/interfaces，则不生效。

ubuntu网络显示设备未托管的解决办法

在终端下执行

sudo gedit /etc/NetworkManager/nm-system-settings.conf

“managed=false”改为“managed=true”，重启电脑就可以。 真的是坑爹啊

同时 我之前一篇文章 http://www.fuxiang90.me/2011/07/vm-linux%E8%99%9A%E6%8B%9F%E6%9C%BA-%E5%92%8C%E4%B8%BB%E6%9C%BA%E8%BF%9B%E8%A1%8Cftp%E8%BF%9E%E6%8E%A5/

虚拟机上网要进行

这一步 其实也是没有必要的 。伤不起啊

参考： http://tieba.baidu.com/f?kz=740913480

http://www.ubuntuhome.com/ubuntu-networkmanager.html

今天赶星老师讲解了在centos下网络配置文件的修改 == ，ubuntu 下有些不一样，于是下午我就打开redhat 的虚拟机，准备尝试下，结果发现 ifconfig 不能用，切换到root 也不能用。

后来发现 在/sbin 目录下有ifconfig ，表明bash 没有去这里找,那么 export  PATH=$PATH:/sbin

或者 在/etc/profile 里 加上PATH=$PATH:/sbin   ，这样就可以执行 ifconfig 了

独立博客 http://www.fuxiang90.me/2011/07/redhat-ifconfig%E4%B8%8D%E8%83%BD%E7%94%A8%E7%9A%84%E8%A7%A3%E5%86%B3%E5%8A%9E%E6%B3%95/
欢迎访问交流 

自己的电脑只有１Ｇ 的内存，有时学习看视频还是喜欢在ｘｐ下弄，然后用ｓｓｈ 登入ｌｉｎｕｘ系统进行操作，我发现ubuntu 10 每次跑的时候 也只是需要200M的内存，当然是没有运行时候大程序，所以我配置linux的虚拟内存为312 M ，实践证明够用。

下次试试开两个虚拟机，准备跟着网上的教程 （赶星老师） ，进行学习，如果不使用putty,老是要切换到虚拟机界面进行操作，电脑反应有时会比较迟钝。所以使用putty 进行登入操作，确实不错。