【AC_LCC_CWJ 第二场】World Final 2006

这场最后太疼了,都是我个人的原因,第一题有些情况没考虑到,于是最后A题这个大水题很遗憾地没过。

一开始师父有事就跑了,大概1个多小时以后又回来了。

这短时间LCC沉浸在G中,我沉浸在J中,貌似都不可自拔

然后后来我觉得J太大自然了,于是又看了一个Board,UESTC的队过了I,然后赶去围观,果断发现是水题,于是切掉。

接下来LCC大神在G题题意极度不清晰的情况下暴力试出了Accepted,Orz。

然后后来又看到了UESTC那队把B过了,我一看,迅速反应出这和昨天那题最大流的构图是一样,只要求个费用流就可以了。

但是第一遍提交的时候出现的很神奇的事情,我交上去Waiting,然后等了N久之后,UESTC也交了一个Waiting,在之后,LCC也交了一个Waiting,我顿时惊叹,题库爆了!然后再过了几秒之后,3个TLE出现,顿时觉得有点假。。。

然后手测了一些数据,发现由于精度问题,费用流跑了正向边以后又去跑反向边去了,然后+个eps以后就Y了。

此期间LCC用小号对E题不断进行轰炸,后来发现是输出的时候格式出了问题…

师父一跑来就说,D是数论,我来切,然后就切掉了~Orz!!!!

接着我看了A题,觉得比较简单,于是开切,然后由于一种情况没有考虑到,应该说题意上有一点误解。

就是这一句

the travel covered by a ticket be completed in order and without intervening travel

然后在我脑海里形成映像,后面的路程也是要完全吻合的,于是悲剧。。。

最后就5题了(B D E G I),师父表示当年WF2006最多的一队也就是6题。我顿时捶胸顿足……就差了我的A题啊

都是我的错……

下面简单说说我做的两题(都超级水):

B题就是要填一个m*n的矩阵c,分别给出每一行和每一列的和,然后每个格子还有一个实数权w,最后输出最小和最大的

Sum{c[i][j]*w[i][j]},有一些实权位-1的表示不可填。然后就是最小费用最大流+最大费用最大流了。

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22056

代码:http://xiudaima.appspot.com/code/detail/4554012

I题就一个Floyd

然后现在把A题补一下。

【题目链接】http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22055

就是给定20张机票,每张机票有一条旅行路线和一个价格,每次可以用一张机票路线的前缀,然后给定20个询问,每个询问都是一条路线,问你通过这些机票,最少花多少钱可以完成这条路线。完成这条路线时必须按顺序经过路线上的点,但是在路线的各点中间,你可以先跑去其它地方再飞回来。

【解法】

F[i,j,k]表示已经完成这个路线的前i个点,现在在第j张飞机票的第k个点时,最少的费用是多少。

由于有后效性,用SPFA来转移之。

然后就解决了

【Hint】题目给出的各城市的编号是任意的。。。如果处理的不好要先离散化。一般直接判等于就行。

【CODE】

http://xiudaima.appspot.com/code/detail/4490007

最后Orz LCC、Orz AC,鄙视我自己

[UVALive 4865 Data Recovery] 疼疼最大流

【题目链接】http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=15554

【题目大意】

给定一个m*n的矩阵,矩阵里每个格子填一个[0,100]的数,有些格子被挖空了(用-1表示),让你向里面填数字。再给定每一行和每一列的和。

如果没有解,那么输出-1

有解的情况下,对于那些确定值的格子填出来,不能确定值的格子,用-1代替。

(m,n<=50)

样例1:

Input:

2 2

1 -1           //-1表示被挖空的不确定的位置

-1 -1

100 100      //每行的和都是100

100 100     //每列的和都是100

Output:

1 99

99 1

【算法分析】

首先用点分别代表行和列,然后形成二分图,行列之间的边就对应着格子。

然后加个源汇沙茶建边做一次最大流就可以得到(确定的格子不需要加边,直接对行列和减一下就可以了)。

无解什么的都解决了。

但是判定一个点是否必须填这个值就需要思考一下了。

由于一个流对应一个解,所以解不同对应着流不同。

我们看图中二分图中的红色的那条边:

假如它要减少流量,那么必须要在残余网络中存在类似这样的路径(注意箭头方向):

假如它要增加流量,那么必须要在残余网络中存在类似这样的路径(注意箭头方向):

实际上从残余网络上看,从二分图左边的点集指向右边点集的边可以视为是增加流量的边,从右边点集指向左边点集的边可以视为撤销原流的边。
于是乎,我们判定一条边上面的流值是否一定,只需要看这条边在残余网络中,是否存在一个点数>=3的环(=2的时候显然是没意义的,就是两个点之间跑),包含这条边就可以了。

实现随意,暴力可过。一开始写了个Floyd发现好难搞=2的环的情况,于是改回暴力dfs。

复杂度O(m^2*n^2)

【CODE】

#include #include #include #define clr(a) memset(a,0,sizeof(a))
const int N=55;
int m,n,S,T,Flow;
int map[N][N];
int c[N+N][N+N];
int v[N+N];
int v2[N+N];
int L[N+N];
int fa[N+N];
int Sx[N],Sy[N];

void init(){
     int i,j;
     clr(c);
     clr(Sx);
     clr(Sy);
     scanf("%d%d",&m,&n);
     for (i=1;i<=m;i++)
       for (j=1;j<=n;j++){
         scanf("%d",&map[i][j]);
         if (map[i][j]!=-1){
           Sx[i]-=map[i][j];
           Sy[j]-=map[i][j];
         }
         else c[i][j+m]=100;
       }
     for (i=1;i<=m;i++){int x; scanf("%d",&x); Sx[i]+=x;}
     for (i=1;i<=n;i++){int x; scanf("%d",&x); Sy[i]+=x;}
}

void build(){
     int i,j;
     S=m+n+1;
     T=m+n+2;
     for (i=1;i<=m;i++) c[S][i]=Sx[i];
     for (i=1;i<=n;i++) c[i+m][T]=Sy[i];
}

bool bfs(){
     int head=0,tail=1,i,j;
     for (i=1;i<=T;i++) v[i]=0;
     L[1]=S;
     v[S]=1;
     while (head!=tail){
           head++;
           for (i=1;i<=T;i++)
             if (c[L[head]][i]>0 && v[i]==0){
               v[i]=1;
               L[++tail]=i;
               fa[i]=L[head];
               if (i==T) return true;
             }
     }
     return false;
}

void change(){
     int nf=0x7FFFFFFF;
     for (int i=T;i!=S;i=fa[i])
       if (c[fa[i]][i]     for (int i=T;i!=S;i=fa[i]){
         c[fa[i]][i]-=nf;
         c[i][fa[i]]+=nf;
     }
     Flow+=nf;
}

void Edmonds_Karp(){
     Flow=0;
     while (bfs())
       change();
}

bool check(){
     int Sum=0;
     for (int i=1;i<=m;i++) Sum+=Sx[i];
     if (Sum!=Flow) return false;
     Sum=0;
     for (int i=1;i<=n;i++) Sum+=Sy[i];
     if (Sum!=Flow) return false;
     return true;
}

void dfs(int p){
     v[p]=1;
     int i;
     for (i=1;i<=m+n;i++){
         if (p==S && i==T || p==T && i==S) continue;
         if (c[p][i]>0 && !v[i]) dfs(i);
     }
}

void solve(){
     if (!check()){puts("-1"); return;}
     int i,j,k,l;
     for (i=1;i<=m;i++)
       for (j=m+1;j<=m+n;j++)if (map[i][j-m]==-1){
           S=i; T=j;
           for (k=1;k<=m+n;k++) v[k]=0;
           bool flag=false;
           if (c[i][j]>0){
             dfs(T);
             if (v[S]==1) flag=true;
           }
           if (!flag && c[j][i]>0){
             for (k=1;k<=m+n;k++) v[k]=0;
             dfs(S);
             if (v[T]==1) flag=true;
           }
           if (!flag) map[i][j-m]=c[j][i];
       }
     for (i=1;i<=m;i++)
       for (j=1;j<=n;j++){
           printf("%d",map[i][j]);
           if (j==n) putchar(‘n’);
                else printf(" ");
       }
}

int main(){
    while (1){
          init();
          if (n+m==0) break;
          build();
          Edmonds_Karp();
          solve();
    }
    return 0;
}
【Others】

今天和AC、LCC做了一场比赛,我队累计切了10题,我显然属于打杂类型……水了4个题,难的都他们去搞了。

Mark一下这四道水题,以后出给小朋友还是可以的

C

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22045

代码:http://xiudaima.appspot.com/code/detail/4568015

状压dp,各种合并

D

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22046

代码:http://xiudaima.appspot.com/code/detail/4514015

模拟

K

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22053

代码:http://xiudaima.appspot.com/code/detail/4572008

DP,需要转一下思路

L

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22054

代码:http://xiudaima.appspot.com/code/detail/4442019

想出了n^2 per data的,直接交超时,于是打表交。因为表才1000,所以程序并不是很长,上面的代码是用来打表的。其实这个预处理可以放在程序前面,不过需要变一下,降为n^2。当时没怎么想到就直接n^3地打表了。

【转】揭秘最露骨的大学生活——如果你也是大学生

       中国从来不缺乏对教育倾注无限热情的人,大师、学者、作家,不一而足,而学生作为教育最直接的产品,却往往失去了话语权。近日,一篇万言长帖《一名大学毕业生的反思》备受中国人关注。一时间对于教育质量的讨论再次达到了一个高度。帖子如此之长恐怕会花费你的一些时间,但可以保证,真正将该帖完整读完,你一定会为作者所写的最真实,最露骨的大学所揪心不已。你也可以保存,或推荐给其他朋友。 
    一年半以前,我自以为已经看清了中国大学的本质,不愿意再继续自欺欺人地“学”下去,主动放弃了学校保研的名额,退出了用青春和热血换取一纸毫无真实内容和分量文凭的游戏,退出了中国虚伪可笑的“精英学历社会”。决心进入企业,踏踏实实地从事“实业”,站到中国经济第一线,为国家和社会以及自己作真实的努力和贡献。因为我不想用镀金的“文凭”和“文化”来糊弄我自己,也糊弄其他人。 
    五年多以前,我进入了全国重点名牌大学:武汉大学读书。我抱着最理想的热情,以为从此走上了一条报效祖国,报效父母的人生坦途,以为我的人生即将要大展宏图! 
    三年以前,抱着对“我的大学”最大的疑惑和不解,我辞去了分团委副书记的职务,开始认真地大量阅读和思考我的人生,我的大学,我的未来。试图找到对周围一切我无法理解问题的解决方案。这一次的决定,也意味着我放弃了原来一直抱有的,通过“从政”来为国家民族做贡献的“远大理想”。
    一年半以前,我自以为已经看清了中国大学的本质,不愿意再继续自欺欺人地“学”下去,主动放弃了学校保研的名额,退出了用青春和热血换取一纸毫无真实内容和分量文凭的游戏,退出了中国虚伪可笑的“精英学历社会”。决心进入企业,踏踏实实地从事“实业”,站到中国经济第一线,为国家和社会以及自己作真实的努力和贡献。因为我不想用镀金的“文凭”和“文化”来糊弄我自己,也糊弄其他人。 
    今天,在毕业工作一年多后,在我的工作和能力已经得到老板和同事的肯定,马上就要派我出国任职的时候,我却辞职了。我不想违心地接受这个光荣,我决心到远在大山中的一所规模很小的,志在探索中国新教育模式的私立学堂,试图通过投身中国最缺乏,最需要的教育,来实现我人生最大的价值:为我热爱的中国,为中国的孩子和未来,也为我自己,做一点真正有意义的事情,而不是日复一日地在无望的等待中浪费掉自己的生命。 
    因为,中国真正缺的不是钱,我缺的也不是钱。中国缺文化,缺教育。我也一样! 
    周围的人都认为我疯了,鬼迷心窍阿了。放弃了中国人从小就灌输的,从小就追求的“最正宗”、“最正确”、“最理所当然”的道路的确令人不解。我也在认真地思考我这样做的理由。在这里,把自己对家人和朋友质疑的回答写出来。你们也可以自己评析:到底是我疯了,还是这个社会疯了?
  一、精神缺乏、游戏成风、学生忙着贴金、老师忙着项目——你认识这样的大学么? 
    当我从那古朴典雅的建筑旁走过,再深入到自己的学习环境和学校其他地方后,我发现这个地方与我之前在书中读到的宁静的大学校园不同,这里各色人等纷纷扰扰,大小汽车进进出出,随处可见各式各样的商业海报或者广告,草坪上遛狗的大妈悠然自得。那种在中小学可以听到的琅琅书声在大学里却寥寥无几,大学怎么竟然不如小学?这些大学生们都不读书么?我很困惑。 
    在正式开始上课之后,我更加见识了大学里很多人是怎么样上课的:早晨上课铃响了之后有很多人穿着拖鞋边吃早点慢悠悠地晃进教室,吃完早点后看看上面的老师,讲得没意思,于是爬着再补一觉。有的学生干脆一睡不起,大学里有句话是这样流传的:“一觉醒来一看表十点了,继续睡到十一点半,起来连早点、中饭一起吃了。” 
    晚上十一点后,应该是夜深人静、正值休息的时候,如果你此时走进大学里的男生寝室,你绝对可以看到他们的**才“刚刚开始”,打游戏、玩麻将或者是看武侠小说,好不热闹。鲜见一起读书、共同讨论人生智慧的场景,相反可以看到很多的大学生去网吧包夜,或者在寝室联机打游戏,他们的日常交流沟通内容就是游戏,以至于很多学生迫不得已,为了和同寝室的哥们“打成一片”而“学习”打游戏。游戏已经成为了大学里男生的主要“学习内容”,而且不少人发奋用功地学习了四年。
  当我第一次在高我一级的学长寝室楼里看到凌乱的宿舍,散发着异味,一抬头就会看到一个蓬松的脑袋和迷离的眼神,我的灵魂被震撼了!我的心中真的不敢相信,这就是武汉大学的学生?空洞的眼神昭示着灵魂的无知和内心的空虚,在终日游戏的日子里打发自己的青春岁月!这是大学生么?这些人就是“为中华之崛起”而努力学习的新一代?我的内心里有一个强烈的声音告诉我:我绝对不要成为这个样子! 
    我的一个同学,从大一到大四,四年的时间,除了考试和教室见个面,其他时间全部在寝室打游戏或者看武侠,反正大学里也没有人管。后来因为挂科太多被学院劝退,家长过来求情延缓时间,但于事无补,游戏照打不误,直到大四时无法毕业。另外一个同学,也是因为打游戏挂科太多被劝退,母亲来到学院跪在学院领导面前说:“我自己在家里吃剩的菜叶在供他读书,求你们给他一次机会吧!”当时我听到学院领导讲到这样的事情的时候,我的内心很受震撼。父母吃菜叶供孩子在城市里打游戏,混日子?还要求情“给机会”?给他继续游戏的机会吗? 
    都说可怜父母心,我想起我辛勤劳作的父母,我想起那千百万把孩子送进大学的天下父母,他们都以为自己的子女在大学里“努力学习”,辛苦地赚钱,无私地供养儿女“上学”,让他们解除“后顾之忧”,不用担心生活的问题。殊不知如今大学校园里,有多少人是在游戏人生。用我在西安电子科技大学一位同学的话来说:“如果他的妈妈来在大学住一个星期,就一定会让他退学回去”。因为在中国“上大学”,可能是人生中一段最轻松愉快的时光了。大家可以游戏,看电视,逃课,武侠小说,这是很多大学男生的全部生活。
  女生呢?看韩剧,不少女大学生的主要学习内容就是看韩剧等各种连续剧,感情剧,一部接着一部。你能想象这就是“我的大学”么?很不幸的,这一切都是真实的,而且就发生在武大这样的名牌重点大学里。这些人考上大学的时候都是家里的骄傲、很多同学眼羡的对象,可是为什么他们在风华正茂的青春时代里,行为如此令人费解?当时的自己不得而知。当然,并不是所有的学生都这样混日子,大学里还是有很多人依然比较用功地学习,但是他们也一样困惑:让他们努力学习的原因主要是“恐惧”和压力:怕找不到好工作,怕考不上研究生。 
    大家都听说就业很困难,武大每年找不到工作的毕业生都很多,因此不敢“放纵”自己。但是很少有学生努力学习是因为追求智慧,追求真理,为国为民而学。这些用功的学生虽然没有“游戏人生”,但是却生活在沉重的压抑心理状态下,思维往往呆滞,慢慢地走上一条被大学生们嘲笑的“越学越傻”的“傻博士”道路。实际上,每年大学里自杀的大学生,往往不是“不用功”的“坏学生”,而是这种心理严重压抑,用功学习的“好学生”。他们一样,从一进大学开始就碰到很多无法解决的困惑,同时被灌输着一些所谓“正确的发展方向”,他们只是愿意服从这些“权威结论”,以自我的压抑而不是以心灵的呼唤来“学习”,这难道就真的比“玩游戏”“看影碟”更好吗?大学的学习到底是要达到什么目的?大学生们为何都迷失了自己的理想。
    照本宣科的老师 一学期也见不到几次 
    首先是专业的学习让人迷惑:很多老师照本宣科,大学里面真正关注教学、关心学生,有上课水平的老师越来越少了,不知道老师都在忙些什么。 
    老师的本职工作应该是传业授道解惑,可是有的老师一个学期学生也见不了几次,派他的研究生来上课。后来我才明白原来他们都在忙着自己的项目和课题。大一的时候,我们通信工程专业有个博导带物理,学生的评价是这样:“还博导呢,都博成个啥了?讲得稀里糊涂,还经常不来上课。”。大学选用的教材令人费解,明明有很好的全国通用教材,比如高等数学的同济五版,却偏偏要选用自己学校编的教材,艰难晦涩,连选用的习题都是历年研究生考试的数一类,可能是编排教材的老师想提前让我们进行考研准备吧? 
    后来才知道学校选用这种“自编教材”的原因,是老师们因为要“评职称”。需要“科研成果”,就东拼西凑的乱编一些“教材”来“完成任务”,这种放到书店里根本没有人会要的垃圾教材,他们就利用自己教学的权利,发给大学生们上课用。据说老师们也很可怜,每年都要完成所谓的“科研成果”,要写论文,出书来完成任务,否则就可能降职。有些老师没办法就自己花钱在外面找刊物发表文章,这种可以不花钱出教材,让学生买单的事情也很容易理解了。
  大学里的学生生涯,除了要求学生的专业学习之外,鲜有启迪心灵的声音,更重要的是缺乏指导大学生人生发展与定位的课程,能够让大学生明白自己为什么学,为什么活的课程。我自己学习的专业是电子信息科学类,和很多同学一样,我在必修的公选课如高等数学等认真学习,但是我在每天的专业学习之外内心十分彷徨,我不知道这个专业适合不适合自己,不知道这个专业意味着什么? 
    不知道这个专业的社会发展方向和主流是什么?也不明白这个专业培养的目的是什么样的人才要求?我不知道该怎样进行大学的学习,更不知道前面的路在那里。我该怎样去一步步实现自己的理想?我碰到过很多的大学生也是如此。他们对于自己所选择的专业了解甚少。其实我觉得老师也根本不了解这些专业到底要做什么,后来知道大学里的管理人员,看专业叫什么名字容易吸引学生,就改个名字。看什么专业热门好找工作,就赶快“上马”一个专业,拼凑一些“课程”出来糊弄人就完事了。 
    很多学生只是为了就业的方便而“选择专业”,但是当他们真正想去定位自己的时候,就反而陷入了“专业思维”而不能自拔。多数人只是为了一份工作而读一个热门的专业,却忘了去关注自己的兴趣、爱好,甚至综合能力的培养和理想的思考。 
    《大学重建》让我开始了解大学的起源、存在的意义,那就是大学应该是一个社会的良知和思想发动器,大学应该为这个社会培养具有正义、勇气和智慧的学子,在他们走上社会之后能够有能力去逐步改善这个社会中不好的东西,促进社会的发展,并不断致力于人类物质社会的改造,以及科学、艺术文学等精神文明的探索和提升。 
    我听到了一些激动内心的声音,也似乎抓住了一些东西,但是我的内心依然彷徨,方向不明确,理想似乎越发遥远,而不知如何下手。同时,为什么我们的大学会是这个样子?为什么这么多的学生缺乏精神思考而且没有老师指引?除了在一些讲座上偶尔能够听到一些激动内心的声音外,为什么大学里的老师讲完课就像是打工混日子,无趣无内容,讲完就走人?为什么大学老师从来不与学生探讨人生智慧?为什么我们这么多的大学生对此熟视无睹?这些问题我不得而知,而我自己也在从事学生干部工作的道路上,碰到了更多的困惑。
    二、为什么要辞去团委副书记? 
    大一时我参加学生会新闻部,然后做部长,和一群志气相投的朋友激扬文字,度过一段难忘的日子。在大二下的时候,成功竞选为分团委副书记兼学生会主席团成员。然而在半年后,我就毅然辞去了这个光鲜的职务,你可能会很惊讶,我不是有“总理的梦想”么?为什么要辞去呢?这可是走上“官员之路”的正途呀?在我最开始做学生会一个小小的部委时候,我只是抱着开阔眼界、锻炼自己的想法。到了后来做部长,在我的本职工作之外,我开始思考我做的事情作用在那里?到底能够做那些有价值的事情去服务同学? 
    大学里的学生有很多的问题需要引导帮助,就像我自己内心就有很多的困惑需要解答,学生会做得这么多活动能够解决了么?没有。从我进学生会开始,我就抱着相机在各种各样的活动跑着,班团会、运动会、文艺比赛等等,在开始我很兴奋,因为生活很充实,活动的确还比较丰富多彩。但是慢慢的,我的内心开始不明白,我发现这些活动组织了、举办了、精彩了、笑过了,却没有更多的智慧启迪,似乎只是一个“政绩”的记录。那些游戏的大学生继续游戏,我内心对于理想的迷惘更没有在这些活动中得到解答。
  于是我开始不明白,为什么要花很大力气很多精力组织这一些形式上的活动,而不去关注学生真正的问题、做学生和大学里真正应该做的工作?那个时候我还是学生会的新闻部部长,在面临换届的时候我想过退出,我的内心已经隐约地告诉我这个地方不适合自己。但内心那个朦胧的梦想让我思考:如果我的“地位”更高一些,“权力”更大一些,如果自己可以领导团委和学生会,是不是就可以去做一些真正有意义有价值的事情了?自己也可以通过这个机会锻炼自己,以明确自己的方向。有很多的学生干部就是这样一步步走上从政之路的。 
    于是我开始努力“提升自己”:凭借自己比较不错的实力和老师的信赖,我成功地竞选为学院的分团委副书记,这可能是学生中地位最高的“官”了。我的内心鼓足了干劲,我要做出一些真正对学生有帮助的事情。可是当真正到了这个位置时候,我才发现我是多么的天真:各种各样的活动,不是我们能够“安排”的,我们只是按照“上面老师”布置的既定程式和内容去走,想要改变其形式上的作用几乎不可能;学院的老师有自己的安排,校团委的领导有自己的想法,一切都要达到一个目的:活动要精彩,形式要多样!可是没有一个人去思考这样的活动带来的实际意义在那里。 
    我发现自己更加没有个人的“自主权”,必须要面对更多的无聊会议,要去组织很多无意义的活动,这些会议、这些活动大多数对于服务学生或者实现自己的理想都根本没有什么作用,更没有办法去解决我所碰到的诸如沉迷网络游戏、缺乏精神风貌的现状,我甚至还失去了思考和学习提高的时间和空间。 
    我的内心不明白:为什么我们不能针对性地去解决学生中切实存在的各种问题?为什么不在他们沉迷网络与游戏时加以规劝和引导,甚至采取一些强硬的措施?难道非得等到他们挂课后给予处分、开除学籍么?更有甚者,与其他学院的一些学生干部打交道后,我发现大学学生会里面的学生干部,有不少本人就是“游戏大学”的优等生,但是他们却因为和辅导员老师关系不错而成为学生干部,来帮助老师“管理学生”。这样的学生干部能够引领学生走向哪里?同时,这些人似乎非常自信自己是一个“精英团体”,个个都感觉良好。 
    学生干部中开始有很多的饭局来“拉进”彼此的关系,喝酒甚至吸烟,所谓的“烟搭桥,酒开路”这样的话,我第一次就是从学生会主席的口里听到的,我很困惑,这是在读大学的有志青年学子么?这就是要引领国家未来的“精英集团”嘛?我们国家就缺这样的“人才”吗?
  当面对着这样的现状的时候,我的内心开始痛苦:我可以选择若无其事尽自己最大的努力做下去,反正都已经做到了这个地步,熬一两年就会有各种优秀的荣誉、保研的机会,通过这个平台可以一步步走上从政之路。但是,我也开始明白了,无论我将来的“地位”有多高,“权力”有多大,我都无法实现自己的理想,我是一个人在与一个庞大的,堕落的,只关心物质利益和为自己捞好处的集团体系作对。 
    我如果想当上“总理”或者其他能够有决策权的位置,就必须跟他们一样混下去,否则早早就会被这个体制踢开。但我真的希望这样么?如果我把宝贵的时间都花在了一些根本不能起到实际作用的事情上,来收获一些所谓的荣誉和好处,我内心的困惑将怎么办?我之后的道路该怎样继续?难道这就是我的理想? 
    在经历了深入的思考后,任职半年我就毅然申请辞去这一职务。当时学院的老师很惊讶我的举动,在明确我执意要辞后,非常好心地建议我可以挂名不做事,这样在大四时候就可以获得保研的机会。我不愿意占这个便宜,告诉老师,既然要走就走个彻底,不需要挂名,我的内心不喜欢这样的方式。 
    于是,我很高兴地脱离了很多无聊的“学生工作”,回到了没有会议,没有那么多我看不懂活动的自由日子。自己读书、听讲座、听武大的“周末艺苑”,让自己的内心自由自在地成长。我努力去重新定位自己的理想,因为我发现从政似乎不适合自己。剩下来的选择还有两个,一个就是大家都很热衷的,也是很传统的“实业救国”之路,我可以去帮助我们国家成为一个经济强国,也帮助自己成为一个“经济英雄”,做“李百万” 另外一条就是冷板凳的“学术之路”:考研,攻博,成为一个学者。 
    我很敬佩经济学家林毅夫先生,当年作为热血青年,做为一个台湾军官,由于反对蒋家王朝的政治腐败,他“叛逃”到大陆。他当然可以享受“义士”级的待遇,在我国的“party政军”系统里快速地升职。但是,他当时叛逃台湾,绝对不是为了谋取物质利益,而是为了心中的热血理想。我想他后来离开政治圈子,走上学者之路,是不是跟我一样,发现在中国“从政”不能解决“为人民服务”的理想,只好去研究学问,去当学者。否则如果他叛逃的目的,仅仅是想当一个学者的话,当时的台湾条件更好,所以一定有他的难言之隐。他现在已经成为了世界经济学界最好的学者之一,还被提名诺{mod}经济学奖。
  到底那条路更有意义和价值呢?我努力去大量阅读,努力去思考,去发现各种线索和事实来帮助我决定,去解决我内心所有的困惑。 
    三、读懂“大学”,我发现“做学问”在大学也是一条走不通的死路。 
    我真的能够专专心心去做一个学者吗?像林毅夫那样?在不断地阅读和思考中,我对于大学的认识也越来越多,我也开始明白为什么这个曾经安静和充满追求智慧风气的象牙塔越来越千奇百怪。商业中逐利的浮躁气息充斥着整个校园,学术与商业的挂钩和教师职称评定的畸形化,使得大学校园里越来越多的老师不重视教学而忙于自己的项目,忙于发表论文。因为有了论文,有了项目,才会有职称和金钱,才会有房子、车子和各种名誉,这样的老师那里有时间去传业授道解惑呢? 
    但是现在的大学校园里,基本上都是这样的老师。因为“理想型”的老师注定要被现实“淘汰”。别的学校不了解,但是全国有名的易中天,在武大的时候却因为个性独特,不愿流俗而被排挤,出走厦门大学。后来是学生们敬仰的武大四大名嘴之一的哲学教授赵林也要离开武大,引起学生轰动。 
    后来据说校长看民意沸腾,才执意挽留赵林老师,勉强留了下来。但是根子上的问题并没有解决,因为我最近又听说专注学问的知名哲学教授邓晓芒要去华工。一个文科教授,却要离开以文科着名历史悠久的名牌大学,宁愿去一所工科大学任职,武大到底怎么了?珞珈山还是个做学问的地方吗?四大名嘴的尚重生教授也说:当年与他一起留校任教的早期很多有才华的老师,都离开武汉大学了。而且很多离开了大学,离开了学界。难道在中国,学者之路也同“从政”之路一样,是一条不可行的“梦幻之路”?中国之大,放得下一张安静的书桌吗?我很不安地探讨自己从事“学问之路”的可能性。越来越多地发现:所谓的“名牌大学”里,真正的学问根本没有地位。 
    老师不关心学问和学习。在这样的大学里,缺乏真正传道授业解惑的老师。因为老师在大学里其实是“弱势群体”,他们被一群根本不懂教育的教育官员们“管理”着,迫于生存压力,为了职称,为了提级,为了饭碗等等,不得不向畸形的评定机制屈服。能够独立思考和具有独立人格的老师,可能根本就不见容于这个教育官僚体制。
  连知名的教授如赵林,邓晓芒都不得不屈服于“体制”,连四大名嘴尚重生都不断地抱怨无法发挥所长,我一个小小的后生,真的能在“学问”的路上实现理想吗?很多博士生导师会派自己的研究生替代自己给本科生上课,自己忙项目,当老板,追逐金钱和权力地位,这与“官场”和“商场”又有什么不同呢?真正的不同,就是这里更虚伪,贴了一张“教育”的皮,所以更害人。 
    校长把老师当打工仔 谁也不关心学生 
    大学的领导不关心学问。他们不关心教师,仅仅是把教师当做打工仔。他们也不关心学生,不理会学生的愿望和要求。很多管学生的“大学领导”在学生面前高高在上,一副“官员”的样子。他们也不关心自己的毕业生到底受不受社会的欢迎,不关心学科的设计是不是符合教育和社会的要求。他们只关心“如何保住位置”,“如何捞取好处”,如何“买卖文凭”,如何与社会上的官员们“交易”。 
    学校的老师告诉我:武汉大学授予了很多官员“特聘教授”的头衔拉拢他们,还送出大量的“博士学位”给各级官员,仅仅因为他们是有实权的“官员”,学校愿意“证明”他们“很有学问”,让他们捞一笔“学问资本”。这些都是公开的秘密。大家都知道前几个月武汉大学的两个校领导被抓,其中一个还是享有“国家荣誉”的获奖“杰出领导”,这暴露了大学一系列问题的冰山一角,据说出事以后,很多有实权的“大学领导”们都惶惶不安,生怕有一天查到自己头上来。我相信这不是武汉大学一家的事情,可能其他大学更腐败。
  可是,我关心的是:这说明了什么?这样的大学,难道真的有“大学精神”吗?真的是一个我要做学问的地方吗? 
    1.我缺钱么?我们的社会缺钱么?我的人生需要去做一件没人需要的事情吗? 
    现在我们的国家里,大家都在努力创造着物质的财富,每一个城市里可以看到很多忙忙碌碌的人,每个人都在辛苦的追逐着。特别是我在深圳工作,这个节奏很快的城市就是金钱驱动的城市。每一次,我坐公交车的时候,我都会留意下那些等车的和街上走过的人们,很多人的脸上都写着焦虑和疲惫。 
    大家都在追求金钱以为会带来幸福,可是为什么都这么不快乐?望着车外的人们,我就问我自己:会不会有一天我也会变成跟他们一样?我问自己追求的幸福是什么?是更多的物质财富,不是,我想幸福于我而言,是一个健康的身体,一份开心有价值的工作并能保障物质生活,一个和睦的家庭。并能把这个幸福的圈子尽自己最大的能力去推广,那么我实业的梦想能够带给自己幸福和更多的人幸福么? 
    再看看我们的国家,改革开放三十年了,中国已经诞生了很多的企业,华为、联想、等等,人们已经创造积累了很多的物质财富,物质生活也越来越优越。而我们却越来越齐心协力地追求金钱,我们创造了很高的GDP,但同时我们面临着越来越多的社会问题:工业的发展带来了很多的环境污染,大都市白领的生理和心理健康每况日下,都市女性白领越来越多的人不能走进婚姻的殿堂,越来越多的高校毕业的大学生找不到工作,都市人在物质富足的表象里精神匮乏,借以酒吧、网络游戏、聚餐等打发时间,青少年儿童以及高校大学生自杀比率升高,流行文化越来越庸俗甚至恶俗化,以及我在大学所碰到的种种困惑,为什么会有这样的问题?怎样去解决?靠追求金钱可以么?
  而这些问题却很实在地关乎我们每一个人的幸福,我们这个社会的整体幸福。但这一切,靠钱都不能解决,是要靠文化,靠智慧。如果金钱可以解决,那我们可以用钱买来生理和心理健康,可以买来家庭的幸福和谐,可以买来优秀的文化,我当然应该多赚钱。可惜这一切都买不来。 
    2. 为什么说中国缺乏真正的教育? 
    靠文化,靠智慧,人才能够得到幸福,国家才会真正强大。为什么一定要去做教育?答案是只有教育才能从根本上改变一个国家的素质,而我们目前的中国缺乏真正的教育,为什么这么说?看看教育和社会的现状以及我们传统文化的断层现象我们就可以明白。 
    我们的小学、中学乃至大学教育都在教学生不断地考试,关注考分,然而,做了那么多的试卷,考了那么多的试,拿了学士、硕士、博士文凭就能解决人生和幸福的问题吗?看一看现在的大学生面貌,有多少人不过是在混一张文凭而已,还自欺欺人地以为:这张文凭会给自己带来一份不错的工作和钱途,可能么?那么多经过高考的学生,走进大学为什么就失去了青年人本来应该有的朝气和活力?为什么他们沉迷网络游戏、在无聊中打发着自己最宝贵的年华?为什么那么多的人找不到工作呆在家里成为“啃老一族?”还有工作之后很多成为“月光一族”? 
    我们最终都要走上社会,我们最终都要独立地去面对生活和生存,我们最终都要为人父母,我们最终都要赡养自己的父母,真正关乎我们人生幸福的问题,诸如怎样去强身健体,怎样去规划人生方向,怎样去处理婚姻问题,怎样去教育孩子,我们的教育有去关注或者启发我们去思考这些问题吗?难道我们的教育就是要在学校里培养一群考试的机器,然后出来成为一个工作的机器?老了成为一个等死的废物吗? 
    那么什么是真正的教育?德国二百年前的教育宣言曾经如此说道:教育的目的,不是培养人们适应传统的世界,不是着眼于实用性的知识和技能,而要去唤醒学生的力量,培养他们自我学习的主动性,抽象的归纳力和理解力,以便使他们在目前无法预料的种种未来局势中,自我做出有意义的选择。教育是以人为最高的目的,接受教育是人的最高价值的体现。
  问一问亲爱的朋友们,在中国目前的小学、中学和大学校园里,有这样的教育么?没有,中国太缺乏真正的教育、缺乏真正的大学了!同时我们回过头来看看中国传统的知识分子是怎样做的,宋朝一代大儒张载曾如此说过:为天地立心,为生民立命,为往圣继绝学,为万世开太平!从此以后,这句话成为了中国知识分子的共识,而现在,我们的社会中有多少这样的学者?我们的大学里有多少这样的教授和博导?我们可以看到为各种利益集团说话的所谓“专家”,可以看到为了金钱奔波在官场和商场的教授和博导。 
    现在我们的社会很多人都在一味地追求金钱作为人生最高目标,从让我们痛恨的房地产商到现在的医院,从老师到卖奶粉的,很多人都忘了自己本职工作的职业道德,一味地拜金。缺乏文化和责任的富人们给我们的社会带来了越来越高的交易成本和越来越多的危害。我们可曾知道美国的清洁工人的工资可以达到年薪五六万,但是他们的房子只需要三十万左右的美金?而我们国内的老百姓却需要耗费两代甚至三代人的积蓄去买一套房子,就因为一些人昧着良心攫取高额利润,而让多少大学生一毕业就要面临这个严峻的人生大事,房子真的值那么多钱么?孟子曾经告诉过我们:上下交征利,国危矣。三鹿奶粉、各地不断的儿童血铅案例已经用血的事实不断地印证着这句话,而我们的社会还需要多少这样的例子来唤醒大家:如果仅为了钱而忘记了道德,昧了良知,我们的社会将走向何方? 
    在这么一个逐利的社会里,究竟还有多少中国人会静下心来学习和传承我们博大精神的传统文化?《老子》、《论语》、《大学》、《金刚经》、《资治通鉴》等等,这些经典的遗产我们继承了么?我们该怎样把这些东西交给我们的下一代,如果不能交给,如果不能完成五千年里中国文化的传承,我们何以有颜面自称为中国人? 
    曾经有句话是这样说的,一个国家破亡而文化存在的民族,一定可以恢复国家(比如以色列),但一个文化破亡了的民族,无一例外地彻底从历史舞台上消失了,比如古巴比伦等。而正是由于这些精髓的传统文化丢失,我们的社会才变得越来越千奇百怪。
  学校缺乏真正的教育导致了社会上很多人盲目逐利、精神空虚、各种社会问题曾出不穷,传统文化精髓遗失,后面两者又反过来影响着学校的教育,如此的恶性循环回把我们带向哪里?我们的后代将会生存在一个什么样的社会里? 
    究竟是这个社会在疯狂地走向一个危险的境地,还是我是一个疯子在危言耸听? 
    3.为中华之崛起做教育 
    考虑到如此的地步,我对于自己做实业的想法又发生了深深的怀疑,我对于自己,对于这个社会的生存发展产生了深深地担忧。一百多年前,梁启超先生曾写下《少年中国说》,一百多年后的今天,我们仍然面临着同样的问题,而且更加严重。只有从教育上去入手,培养优秀和有良知的公民及社会领袖,我们才有希望去改变我们社会中丑恶的一面,才能传承我们的文化,我们的子孙后代才会健康、幸福地生存在这块土地上,才能自豪地说:我是一个中国人! 
    因此我决定走进大山,去一个小小的私立学校做一名普通老师,学习中国博大精深的传统文化,习武修身,传播智慧。为我热爱的这个国家,为中国的孩子和未来,也为自己,去做一些真正有价值的事情!因为唯有文化方能立国,唯有真正的教育才能树人!唯有智慧方能让一个人拥有真正的幸福,让一个社会真正的和谐,让一个国家真正的强大! 
    注:没有想到文章受到这么多人的关注,在此说明下——由于体制内教育的失败,我不可能加入任何一所官办的应试学校来实现自己做真正教育的理想,而选择了在大山里的这所私立精英学堂(别误会,不是农村支教,那样我再努力也只是为体制培养几个低级打工仔),不提学堂名字的原因,是因为避免有人说我是商业炒作(毕竟是私立的),玷污了这个神圣的教育理想。
  同时,这所学堂目前因为超前的教育理念,虽然规模不大,但影响力已波及全国,她必将成为中国未来先进教育的一个范例,因此我也不想借名生辉,借学堂出名。我更愿意贡献自己的一份力量,通过自己踏实的努力来让学堂因我而更荣耀而非相反。希望大家理解。 
    另外,我开始新的工作才两个月。在这里,我第一次尝到了“挫折”的感觉,相对于我一贯的“顺风顺水”,我在这里明显感到了自身能力的不足和思想的浅薄。相比一起工作的,跟我同年毕业的同事和朋友,我感到了实实在在的差异,我需要有更多的努力来提高和完善自己。但是,这反而让我更加高兴,更加认定了自己选择的正确:这是一个可以让我不断提高的地方,这是一个可以让我实现自己理想的地方,去实现自己的教育强国之梦—-去不断提高自己和需要我帮助提高的人。 
    写这篇文章目的有两个: 
    1. 能够唤醒大学里沉睡的一部分人去思考自己的人生而非随波逐流、人云亦云,自助者天助之。 
    2. 引起更多的人对于教育的关注和反思,因为这关系着我们每一个人的幸福。我们不能因为老师、大学和社会对我们不负责任就放任自流,相反正因为学校和社会没有为我们负责,我们更要加倍地为自己负责,更要认真地思考和选择自己人生。如若能达到此两者,足矣,谢谢各位。

骑士王的荣耀

听纯音乐版《骑士王的荣耀》的时候酷狗突然出现歌词,然后我又用歌词link回歌曲。。。找到一首有中文歌词的。

晨月-骑士王的荣耀


石中剑启 长摆飞扬
士卒高呼骑士王
骨肉终是 兵刃相向
悲难泯化英灵征战场
誓约胜利之剑展锋芒
惊破层楼寒天光
高居王位之上 眺望边疆
何处是我期盼的彼方
落日昏黄 满目苍凉
伏尸百万路漫长
乱军之中 傲然身影
何处是她追逐的理想
转身道别犹若梦一场
谁言生死两茫茫
黄泉碧落踏尽 耀目夕阳
弹指此身百年已沧桑
我愿为卿 歌罢此一曲
仗剑定兴亡 何尝对镜妆
树影葬 戎马生涯枉
相忆自断肠 唯余泪两行
落日昏黄 天地苍凉
乱军之中 傲然身影
去往梦中飘渺理想乡

Kosaraju算法的证明

首先提出图的转置的概念。所谓转置就是将一个图上所有的有向边反向。简单来说就是本是x->y的一条边,现在变为y->x这样一条边。

另外强连通性质具有传递性,如果(i,j),(j,k)属于同一强连通分量,那么(i,k)属于同一强连通分量。因为如果满足题设,那么存在路径i->j->k和k->j->i。所以传递性得证。所以其实我们要求点i所属的极大强连通分量,只需要把所有和i可以互达的点求出来就可以了。

该算法的流程如下:

1、 利用深度优先搜索遍历原图,并按出栈的先后顺序把点放进一个线性表里。这里可以每次取任意一个点出发DFS,如果还有点未被DFS到,那么继续任选未被遍历到的点出发DFS。

2、 将整个图转置。

3、 按照线性表中的出栈顺序,从后往前依次作为起点DFS。每次DFS到的就是一个强连通分量。

初看这个算法很神奇,但是其实是不难证明的。

命题1:该算法求出的都是强连通分量

假设在后来转置后的图中从x dfs到了 y处,说明存在路径x->y。因为这是在转置图中,所以说明原图中存在路径y->x

然后另外一个信息就是x的序号在y之后。这有两种可能:

1、以y为根先DFS出了一棵搜索树(可以认为是整个搜索树的一棵子树),但是这棵子树里不包含x,并且此时x还未被dfs到。(利用反证法,如果这棵子树里包含了x,那么x的序号会在y之前)

2、y是x扩展出来的搜索树中的一个结点。

综合两个条件,综合两个条件取交。那么上面两种可能中的第一种不成立。因为存在路径y->x,所以如果x未被dfs到,一定会被y为根的搜索树包含的。于是只剩下第二种可能,那么第二种情况表明存在路径x->y。所以x,y可以互相到达。至此证明了该算法求出的都是强连通分量。命题1得证。

命题2:所有的极大强连通分量都会被该算法求到。

命题2等价于:不存在两个点(i,j),他们互相可达,但是没有被放进同一个强连通分量中。易知若(i,j)可以互相到达,那么肯定其中一个点在另外一个点扩展出去的搜索树中(注意DFS的性质,走完一个分叉再走另外一个分叉)。

由于轮换对称,不妨设j在i扩展出去的搜索树中,那么显然j比i先出栈。假如命题2不成立,那么必须是有一棵以A为根(而且这个A必须比i后出栈)的搜索树,它包含了j但不包含i。由命题1可知,(A,j)可互达。那么由于(i,j)可互达,在这颗搜索树中,肯定能有j扩展到i,所以这样的一棵搜索树是不存在的。因此反证得命题2成立。

该算法比Tarjan算法慢一点,但是有一个好处:该算法依次求出的强连通分量已经是拓扑序的。

下面给出这一性质的证明:

对于两个不同的强连通分量A,B,设A中出栈顺序最晚的点为a,B中出栈顺序最晚的点为b。不妨设a出栈顺序在b之前,那么有两种可能。

1、存在路径b->a。由于两点不属于同一强连通分量,所以不存在路径a->b。这种情况下Kosaraju算法会先把B强连通分量拿出来,所以是满足拓扑序的。

2、不存在路径b->a。那么这种情况下必然也不存在路径a->b,否则a出栈之时,b必然已经出栈了。所以,先拿出B强连通分量是符合拓扑序的。

所以,该性质得证。

【写图论教程时无聊证了一下。。。各位无视】