Monthly Archives: April 2010

Hamilton路与带下界的网络流

QQ群里戴牛提了这样的一个问题:为什么不能用求解带下界的网络流的方法来做Hamilton问题?详细来说,就是把一个图的每个点拆成两个点,在中间加上一条容量上下界都为1的边,求从一点S到另一点T的流,如果可行流存在,则S,T之间存在Hamilton路。

乍一看上去似乎非常合理,当然,我们知道肯定是有哪里出了问题的。因为Hamilton路是经典的NPC,而网络流有无数种多项式做法,如果真的这么把一个NPC解决了,那这几十年以来的计算机科学家们也忒弱了。

问题出在下界的转化那一步。首先来复习一下标准做法:带下界的网络流的求法通常分两步,第一步是判断是否有可行流,然后再求最大流或最小流。这里我们只关心第一步,这一步实际上是把问题转化成了一个点上可以发出或吸收流量的可行环流问题。先形式化一下这个问题(1):

给定网络(V,E),其中每个点i都有一个可正可负的值e[i],每条边(u,v)上有一个容量上界c[u,v]。我们要对每条边[u,v]求一个流量f[u,v],满足f[u,v] <= c[u,v],且Sigma f[u,v] = e[u],这里v取遍u的所有相邻点求和。

也就是说必须满足每个点都可以发出或吸收一定数量的流量,显然要使可行流存在必须有Sigma e[u] = 0,u取遍所有点。对这个问题的求解,我们可以添加一个源S和汇T,S向所有e[u]>0的点连边,容量为e[u]。所有e[u]<0的点向T连边,容量为|e[u]|。求最大流,若最大流能把S发出的边充满,则原问题(1)有解。

然后我们来看下界的转化。设每条边(i,j)有上界U[i,j]和下界L[i,j],流量f[i,j]须满足L[i,j] <= f[i,j] <= U[i,j],我们把它们全减去L[i,j],即0 <= f[i,j] – L[i,j] <= U[i,j] – L[i,j]。可以发现,这样变成了只以(U[i,j] – L[i,j])为上界的边。但是因为流入的量减少了L[i,j],我们必须把它补偿上,也就是说必须强制点j“发出”一份L[i,j]的流量,这个就对应了上面的e[]。同时,强制点i“吸收”一份L[i,j]的流量。

于是转化方法就是,把边的上界变成U[i,j]-L[i,j],然后令e[i] = Sigma L[i,j] – Sigma L[k,i]。这里j取遍所有i指向的点,k取遍所有指向i的点。然后我们添加一条从T指向S,容量为正无穷的边。求此网络是否存在可行环流。这就回到了问题(1)

注意问题(1)里并没有哪两个点是特殊的源或汇,这是一个环流问题,只要满足每个点的e满足要求就行。对于有源汇的问题,就如上面的转化,加一条从汇指向源的边,容量为正无穷即可。这样就可以让所有流量都再流回去了。但是Hamilton的转化也就在这里出了问题,我们经过转化后求的是可行环流,但这个可行环流并不一定是Hamilton路。原因在于这个环流并不保证连通Hamilton路中的两个端点,我们求出的可能是若干个不相连的环,它仍然是可行环流,满足问题(1)里的所有限制条件,但无法从它构造出Hamilton路。见下例,很明显,1和6之间不存在Hamilton路:

hami1

如果按照上述转化,就得到下图:

hami2

这里i和i’间的虚线本来是上下界都为1的,相减之后没有了。6’到1的虚线是容量为正无穷,其余边容量均为1。图比较乱,仔细看会发现S发出的6条边都能充满,比如S->2′->3->T, S->3′->1->T等等。这个图的可行环流存在。但是这个可行环流实际上是不相关的两部分,所以Hamilton并不存在。

有童鞋可能认为可以求出流来,再判断一下这个环流是不是相通了原来的两个端点。但是这并不是充要条件,我们求出的环流不连通并不说明Hamilton路一定不存在,而我们在求环流时无法强制令其连通。

ZJU 2010校赛解题报告

Edit: 已经有官方完整版了 http://www.hhanger.com/blog/?p=438

抢在官方报告前发一个,为Blog增人气,嘿嘿。题目出得我觉得非常好,先写大家比较关心的D和G,以后再慢慢补全。比赛页面:http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=307

Problem D. Game

我们把棋子看作点,若两棋子的距离不超过L则在两点间连边。结论是很简单的:求这个一般图的最大匹配,如果不存在完美匹配(即有的点没有被匹配上),则先手必胜,否则后手必胜。下面说原因:

如果图中不存在完全匹配,则先手方可以先拿走任意一个不在最大匹配中的点u,则后手方不管怎么拿一定会拿到在最大匹配中的点v。(不然的话我们就可以把u-v这条边加进去得到更大的匹配,与前提矛盾)然后,每次先手方只要拿与后手方上次拿的那个点匹配的点即可。因为我们知道当得到最大匹配以后,图中是不可能存在交错增广路的,所以后手方每次都不可能选出不在匹配中的点(不然就是找到一条新的交错增广路了),这样一直进行下去,最后无路可走的一定也是后手方。

反之,若图中有完美匹配,则先手第一手无论如何都会选择在匹配中的点,然后后手就掌握主动了,像前面说的一样一直沿着这个最大匹配走下去,最终先手必败。

Problem G. Islands

这题我觉得我的做法可能有点复杂了。首先的观察是,因为不允许有多余的边,所以最后补出来的结果必定每个点都有一入一出,所以如果某个点的入度或出度大于1的话,直接无解。然后我们可以发现,如果一开始没有任何边的话,实际上这就是一个错排问题,也就是求一个1..N的排列使得每个数都不在它对应的位置上。下面先来说错排问题的递推解法(关于错排还能用容斥原理得到一个漂亮的公式,此处略):

设n个数的错排方案数是f[n],考虑最左边一个位置A,设它指向B,则有两种情况:
(1)B指回A,这时还剩n-2个数,所以问题变成了N-2个数的错排
(2)B指向A以外的数,这时我们会发现得到了一个N-1个数的错排(因为A已经确定指向B,本来是限制B不能指向自身,现在变成了限制B不能指向A,其实是一样的)

因为A一开始可以有n-1种B的选择,所以就有 f[n] = (n-1) * (f[n-1] + f[n-2])

现在的复杂之处在于这个排列里某些位置的值已经确定了(就是那些已经存在的边),除掉这种边以后,剩下的位置就分为了两类,一类是没有任何限制的,一类是不能指向它自身的。比如有五个点,已经有(2->3),(3->4)两条边,则4这个点就是没有任何限制的(它可以随便指向1或2或5),而1,5两点不能指向自身。类比错排问题的递推,我们用f[n][m]表示n个被限制不得指向自身,m个无限制的方案数,仍考虑第一个位置A,则有如下几种情况:

(1) A指向了一个有限制的B,共有(n-1)个这样的B,则有两种情况:
1a. B指回A,问题变成n-2个有限制,m个无限制
1b. B指向其他数,问题变成n-1个有限制,m个无限制(B的限制是不能指回A,类似上面错排第二种情况的讨论)

(2)A指向了一个无限制的B,共有m个这样的B,同样有两种情况:
2a. B指回A,问题变成n-1个有限制,m-1个无限制
2b. B指向其他数,变成n个有限制,m-1个无限制(这时B从无限制变成了有限制)

综上得到递推方程 f[n][m] = (n-1) * (f[n-2][m] + f[n-1][m]) + m * (f[n-1][m-1] + f[n][m-1])

边界条件是f[0][0] = 1

C++ Primer 笔记(5)

Chapter 14

这章主要讲操作符重载。

操作符重载不能用于操作数都是内置类型的时候。比如,我们不能重载operator+(int,int)。操作符的优先级、结合性、操作数个数不能改变。重载&&,||和逗号后,不再保证求值顺序和短路运算,最好不要重载这几个。

大部分重载操作符可以作为普通函数或类的成员函数,在第二种情况下,参数列表里会少一个,因为省略了隐含的this。一般将算术和关系操作符定义非成员函数,而将赋值操作符定义为成员(如上章介绍)。如果作为普通函数,因为往往要访问私有成员,在类定义里往往要将该函数设为友元。操作符也可以用类似函数调用的形式访问,像这样 loli = operator+(loli, loli2).

赋值(=)、下标([])、函数调用(())、成员访问(->)这几种操作符必须定义为类成员。+=, ++之类,最好定义为成员。对称的运算,如+, ==,往往定义成普通函数。

重载IO操作符应该声明为普通函数,不然的话类就只能作为左操作数,就会变成这样的诡异形式 loli<<cout,明显不符合习惯。而我们又不能为iostream类添加成员,所以只能定义成普通函数了,然后把它作为我们的类的友元。

重载加法时应该返回一个新的对象而不是引用(所以a+b是右值),而+=一般返回的是对左操作符的引用。(这种情况下用+=效率高些?)

某些算法(例如find())以及关联容器需要我们定义<或是==,要注意<的定义满足以前说的那几个条件。

下标运算符可能作为左值,故应返回引用。但对const对象应返回const引用,所以应该写const与非const两个版本的重载函数,如chapter 12所讲。

重载自增和自减操作符应该遵循惯例,前置返回引用,应该这样写:Loli& operator++(),后置返回变化之前的,应该这样写:Loli operator++(int),最后那个int是为了与前置区分,在函数体内无视它。

定义了函数调用操作符的类,又被称作函数对象,因为这种类的对象看上去表现得像一个函数。这种东西最常用在STL里,比如我们自己定义一个结构体的比较函数对象,优先按照年龄,然后按照姓名排序:

struct Lolicmp {
    bool operator()(const Loli &a, const Loli &b) {
        if (a.age != b.age) return a.age < b.age;
        return a.name < b.name;
    }
};

std::set<Loli, Lolicmp> loli_set;
std::vector<Loli> loli_arr;
sort(loli_arr.begin(), loli_arr.end(), Lolicmp());

标准库也定义了若干函数对象,比如我们最常用的greater<T>,所以把int数组从大到小排序就是sort(a, a+N, greater<int>())

Chapter 15

本章介绍OOP的核心:类继承和动态绑定。继承就是指类之间的层次关系,一个类是另一个类的派生类之类。动态绑定是指在运行时才决定是调用基类的成员函数还是派生类的成员函数,这就产生了所谓多态。C++里实现要想实现动态绑定需要用对象的引用或指针,看下面例子:

class Loli {
public:
    virtual void speak() { cout<<"oniisan~"<<endl; }
    virtual ~Loli() { }
    Loli() : age(0) { }
protected:
    int age;
};

class TsundereLoli : public Loli {
public:
    void speak() { cout<<"ulusai! I am "<<age<<" years old."<<endl; }
};

void func(Loli &t) { t.speak(); }

int main() {
    Loli a;
    TsundereLoli b;
    func(a);
    func(b);
    return 0;
}

这个程序有很多地方需要解释,下面会慢慢说。

执行上面程序会发现,两次调用func()实际上调用了不同的函数,尽管func里写的是接受基类的引用(在书里这个引用或指针的类型叫做静态类型),但传进去的对象会“知道”自己实际的类型(书里叫动态类型)。要实现这个功能,一定要把基类对象的相应成员函数声明为virtual,只有虚函数才会执行动态绑定,普通成员函数的执行是在编译期就确定的。如果上面例子中的speak()不是虚函数的话,因为func接受的是基类Loli的引用,故一定调用基类的speak()。注意,一旦基类里声明某函数为虚函数,它就一直是虚函数,在派生类的实现里无需再带virtual关键字(是不是带上更清晰些?)

基类与派生类之间的转换

如上所述,存在派生类引用(或派生类指针)到基类引用(或基类指针)的自动转换,这就是实现多态的关键。反之的自动转换则不存在,例如如果把上面func()函数改成接受TsundereLoli的引用,则编译不过,因为func(a)这句要求一个基类引用到派生类引用的转换,这是不能自动进行的。

上面说的是指针或引用的转换,对象的转换则完全不同,如果把上面的func函数改成 void func(Loli t) {…},此时它自始至终都是接受一个Loli类型的对象,不存在动态绑定,如果把TsundereLoli对象传递过去,则TsundereLoli会被强行“切割”(slice down)成一个Loli对象,然后调用Loli::speak(),TsundereLoli对象的任何不属于Loli子对象的数据成员和函数成员将被丢弃。

下面来详细分析一下原因:

当用派生类对象对基类对象进行初始化或赋值时,有两种可能的情况发生:第一种情况很罕见,就是在基类里有一个以派生类为参数的复制构造函数和赋值运算符,像下面这样子:

class TsendereLoli;
class Loli {
public:
    Loli(const TsendereLoli &) { ... }
    Loli& operater=(const TsendereLoli &) { ... }
};

这时我们可以自己定义从派生类对象转换到基类对象时做什么。不过这种情况显然是非常罕见的,理论上基类的作者不应该知道具体是谁继承了自己,他只应该对自己以及父类负责。第二种情况是常见的,也就是基类里只有以自己的引用为参数的构造函数和赋值运算符(如果不写的话默认产生的也是这种):

class Loli {
public:
    Loli(const Loli &) { ... }
    Loli& operater=(const Loli &) { ... }
};

这时如果我们把一个派生类作为参数传进构造函数或赋值过来,这时会发生的事情是:首先将基类类型的引用(Loli&)绑定到一个派生类的对象,然后将这个引用作为实参传递给复制构造函数或赋值符,因为是基类的引用且非虚函数,函数内部只能使用到派生类里的Loli子对象部分,如果调用函数的话也只能调用基类的函数,通常情况下函数内部的实现是把基类的成员一一复制过来(不写的话默认也是这样的),当函数结束后,就得到了一个真正是基类的对象,不存在任何派生类的成分,这时我们就说派生类被slice down了。

(15章未结束,待续)

C++ Primer 笔记(4)

Chapter 12 (cond)

关于构造函数

所谓构造函数初始化式(Constructor Initializer)是指在构造函数参数列表后面冒号里的那一列东西,这是一个很多熟练程序员都可能不太了解的地方,大家可能更习惯在构造函数的花括号里写东西。但是实际上只有在冒号后面的那些才是真正的初始化,在花括号执行的只是普通的赋值语句,明确地区分这两者看上去有点无聊,但某些情况下是必须要考虑的。一是效率上的原因,不管怎么写,在创建对象时都要先对每个成员进行初始化,然后再执行花括号里的普通计算。如果写在花括号里,实际上是先初始化一次,再赋值一次覆盖掉初始化的内容,这样就造成了浪费,如果成员是比较大的对象,效率上会有影响。二是某些对象是不允许赋值的,比如引用和const成员,这时只能在初始化式里初始化,不能在花括号里赋值。总之,尽量写在初始化式里比较好。

初始化的次序与成员声明的次序一致,与初始化式里的次序无关。尽量不要让初始化的值依赖其他成员变量,以免造成混乱。

如果初始化式里没有指明某个成员变量,则按照默认方式初始化:对于类类型成员调用默认构造函数,对于内置类型成员,如果是全局对象则置0,局部对象则为未定义值。

如果对类A声明了任何一个构造函数,则编译器不会再自动合成默认构造函数。这种情况下会带来诸多不便,比如如果某个类B以类A作为一个成员,则类B也不再有默认构造函数;不能声明A的静态数组;包含A的容器也不能只用一个表示大小的值来初始化,等等。所以通常情况下最好要有个默认构造函数。

如果类有接受一个参数的构造函数,这时就隐含了一种类型转换的可能,见下面代码:

class Loli {
public:
    Loli(int n) : age(n) {}
    int get_age() {return age;}
private:
    int age;
};

void print_loli_age(Loli loli) {
    cout<<loli.get_age();
}

虽然print_loli_age要接受一个Loli类型的参数,但我们可以直接调用print_loli_age(15)。因为Loli有一个接受一个int参数的构造函数,这样就把15自动转化生成了一个Loli类型。有的时候这样的隐式转换不是我们想要的,就需要在构造函数前面加一个explicit来禁止这种转化,此时如果想转化的必须显式调用:print_loli_age(Loli(15))

关于static成员

static成员独立于类的任何实例对象而存在。static成员函数没有this指针,也不能访问非static成员。static数据成员必须在类的定义体外定义恰好一次,在定义同时初始化,通常把它和类的成员函数的实现放在同一个源文件里。

Chapter 13

本章主要是三部分内容:复制构造函数、赋值运算符和析构函数

复制构造函数是一种特殊构造函数,具有单个形参,该形参(常用 const 修饰)是对该类类型的引用。当定义一个新对象并用一个同类型的对象对它进行初始化时,将显式使用复制构造函数。当将该类型的对象传递给函数或函数返回该类型的对象时,将隐式使用复制构造函数。

在初始化的时候,如果是直接在圆括号里写参数,例如 string s(10, ‘a’),则调用相应的构造函数,如果出现了赋值号(不知道这么说严谨不),例如 string s = “aaaa”,则先生成一个临时对象,再调用复制构造函数复制过去。

当对象作为非引用的参数传递给函数的时候,以及从函数里返回一个非引用的对象的时候,会调用复制构造函数生成一个副本。另外如果是定义了类似vector<T> v(n)之类的东西的话,会先用默认构造函数生成一个临时对象,然后用复制构造函数复制n份。

如果没有显式声明复制构造函数,编译器会自动生成一个。多数情况下这就够用了,但是有些情况下还是不行的,比如对象里面有个指针或引用而我们想实现一个deep copy的功能,或者对象里有一个不可复制的成员,这时候就要自己定制了。定制的复制构造函数和普通的构造函数没什么大区别,接受一个相同类型的引用(通常是const)作参数,推荐用初始化式进行初始化,然后在花括号里干其他的事。

如果我们想禁止对象被复制,应该写一个private的复制构造函数(不能不写,不写会自动生成),但这样的话自己的成员函数和友元还是可以调用它,进一步的方法是只声明而不实现(好强-_-)。这样的话,如果是外部调用,会编译错误,如果是自己的成员函数或友元调用,会链接错误。

重载赋值运算符时,代码的写法看上去就像把operater=当作类的一个成员函数一样,它接受一个相同类型的const引用作为参数,返回值是同一类类型的引用。注意处理好赋值给自己的情况,这种情况通常要特判一下。

如果是new出来的对象,只有在delete时才会被删除(此时调用析构函数)。如果忘了删除就会导致所谓内存泄漏。内存泄漏往往只有在程序长时间运行后内存消耗严重时才表现出来,比较难于发现。

关于智能指针:所谓智能指针是指保存了一个“引用计数”的指针,它可以避免当多个指针指向同一对象时,通过其中某个指针把对象删除了,但其他的指针并不知道,继续访问就会导致错误。通过保存一个引用计数,只有当指向这个对象的指针数为0时,才真正把对象删除。在这种情况下需要自己实现一个指针类,把原生指针包装一下,通过重写该指针类的构造、复制、析构函数实现引用计数的管理。在13章的最后给了一个很好的例子。(ps. 在boost里有标准的智能指针实现了?)

C++ Primer 笔记(3)

后面的内容我比较不熟,所以写得详细些。

第12章到第14章是本书的第三部分,是关于“类和数据抽象”。把数据和对数据的操作结合在一起,形成所谓的抽象数据类型(ADT)。只把操作暴露给类的使用者,把具体的实现隐藏起来,类的使用者无需关心,这就体现了传说中的“封装”。以这种方式写程序被称为“基于对象”(Object-Based),它并不是完全的“面向对象”(Object-Oriented),没有涉及类的继承、多态、虚函数、动态绑定等等复杂的机制(这是本书第四部分的内容)。很多国产书上往往对此混淆不清,让读者以为在结构体里加个方法就是面向对象了,对于真正面向对象的精髓一笔带过,读者看完整本书都不知道所谓多态到底是怎么回事。

完全彻底的“面向对象”不一定就是最好的,很多情况下用基于对象的方法才是最合适的,比如STL可以说就没有面向对象的内容。对于小程序来说甚至面向过程的方法就已经足够,没有必要搞得过于复杂。

Chapter 12

在类内部定义的成员函数默认为inline,在类外部定义的成员函数要用class_name::member_func这样的方式指明其所属的类。非static的成员函数有一个隐含的参数this,它是一个指向调用该函数的对象的指针。如果把成员函数声明为const,相当于这个this指针是const指针,也就是不能修改对象的内容了。另外,声明时这个const必须在声明和定义时都出现,否则编译不过(原因很有趣,后面会解释)

class和struct关键字的区别只有一点,class里成员默认是private,struct默认是public。

在类的内部可以用typedef定义类型别名,比如

  class Loli {
  public:
    typedef unsigned short age_type;
  private:
    age_type age;
  };

这样就有了一个Loli::age_type的类型了,类的实现会保证它能处理任何年龄的loli,我们无需关心它具体是个什么类型。标准库里的string::size_type也是同样的道理。

类的定义在遇到右花括号时结束,这时编译器就知道了全部的类的成员,以及存储一个对象所需的空间(成员函数的实现可能未知)。类的定义通常写在头文件中,然后被include到各个源文件中。一个源文件中同一个类的定义只能出现一次(这一点可以用#ifdef机制保证),多个源文件中可以多次出现同一个类的定义,但它们必须完全相同。

也可以先声明而不定义一个类,像这样 class Loli; 这样的语句被称为前向声明,这时得到一个“不完全”的类型,因为编译器只知道一个名字,此时只能以有限的方式使用它。使用方式可以是定义指向该类型的对象的指针或引用,或者声明(而不是定义)一个以该类型对象作为参数或返回值的函数。但是不能定义该类型的对象,也不能定义上面提到的那种函数。总之就是不能有涉及类的内部成员的东西。有时候我们需要互相依赖的类(A里有B的引用,B里有A的引用),这时就需要这种前向声明。

this指针一般不需要显式地指明,但是在我们需要返回一个对象自身的引用时,需要写成 return *this; 这个样子。见下例:

class Loli {
public:
    typedef unsigned int age_type;
    Loli &set_age(age_type k) {age = k; return *this;}
    Loli &grow_up() {++age; return *this;}
    Loli &push() {
        cout<<"You pushed a loli who is "<<age
            <<" years old."<<endl;
    	return *this;
    }
    Loli() : age(0) { }
private:
    age_type age;
};

这样我们就可以方便地按如下方式连成一串调用了:

Loli a;
a.set_age(14).grow_up().push();

进一步地,我们发现push()这个操作不改变loli的状态(其实是改变的吧XD),所以可以希望将其声明为const。另外一个原因是,如果我们有一个const的loli对象,也希望能进行这个push()调用。但是我们会发现如果只把成员函数后面加个const是编译不过的,原因在于返回值还是非const的,这样在return的时候会试图把const的*this转换成非const,而这是不允许的,所以应该写成:

class Loli {
public:
  ...
  const Loli &push() const { ... }
}

但是这样我们又发现了新问题,下面的语句

a.set_age(14).grow_up().push().grow_up();

竟然编译不过。其原因在于push()返回了const对象引用,这个引用不允许再访问非const的grow_up()了。解决方法是写两个不同版本的push(),分别支持const和非const,如下:

class Loli {
public:
    typedef unsigned int age_type;
    Loli &set_age(age_type k) {age = k; return *this;}
    Loli &grow_up() {++age; return *this;}
    Loli &push() {
        cout<<"You pushed a loli who is "<<age
            <<" years old."<<endl;
    	return *this;
    }
    const Loli &push() const {
        cout<<"You pushed a loli who is "<<age
            <<" years old."<<endl;
    	return *this;
    }
    Loli() : age(0) { }
private:
    age_type age;
};

可见“const与否”也是作为了“函数签名”的一部分,是可以重载的。现在这种写法就可以针对Loli对象到底是不是const而调用不同的函数。这也说明了前面的问题:为什么const成员函数里那个const字样要在声明和定义里都出现,否则他们就不是指的同一个函数了。另外,上面的写法出现了代码重复,最好把重复的部分提取出来放到一个private成员函数里。

如果希望一个成员变量无论如何是可变的(即使在const对象里),应该把其声明为mutable。