技术手记

最优匹配(Kuhn_Munkras算法)

Posted on by snoopy 
// ** Start of PerfectMatch *******************************
// Name: PerfectMatch by Kuhn_Munkras O(n^3)
// Description: w is the adjacency matrix, nx,ny are the size of x and y,
// lx, ly are the lables of x and y, fx[i], fy[i] is used for marking
// whether the i-th node is visited, matx[x] means x match matx[x],
// maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays are start at 1

int nx,ny,w[MAXN][MAXN],lx[MAXN],ly[MAXN];
int fx[MAXN],fy[MAXN],matx[MAXN],maty[MAXN];

int path(int u)
{
    int v;
    fx[u]=1;
    for(v=1;v<=ny;v++)
        if((lx[u]+ly[v]==w[u][v])&&(fy[v]<0)) {
            fy[v]=1;
            if((maty[v]<0)||(path(maty[v]))) {
                matx[u]=v;
                maty[v]=u;
                return(1);
            } // end of if((maty[v]...
        } // end of if((lx[u]...
    return(0);
} // end of int path()

int PerfectMatch()
{
    int ret=0,i,j,k,p;

    memset(ly,0,sizeof(ly));
    for(i=1;i<=nx;i++) {
        lx[i]=-INF;
        for(j=1;j<=ny;j++)
            if(w[i][j]>lx[i])
                lx[i]=w[i][j];
    } // end of for(i...

    memset(matx,-1,sizeof(matx));
    memset(maty,-1,sizeof(maty));
    for(i=1;i<=nx;i++) {
        memset(fx,-1,sizeof(fx));
        memset(fy,-1,sizeof(fy));
        if(!path(i)) {
            i--;
            p=INF;
            for(k=1;k<=nx;k++)
                if(fx[k]>0)
                    for(j=1;j<=ny;j++)
                        if((fy[j]<0)&&(lx[k]+ly[j]-w[k][j]<p))
                            p=lx[k]+ly[j]-w[k][j];
            for(j=1;j<=ny;j++) ly[j]+=(fy[j]<0?0:p);
            for(k=1;k<=nx;k++) lx[k]-=(fx[k]<0?0:p);
        } // end of if(!path(i))
    } // end of for(i...

    for(i=1;i<=ny;i++) ret+=w[maty[i]][i];
    return ret;
} // end of int PerfectMatch()
// ** End of PerfectMatch *********************************

最大匹配(匈牙利算法)

Posted on by snoopy 
// ** Start of MaximumMatch *******************************
// Name: MaximumMatch by Hungray O(n^3)
// Description: mat is the adjacency matrix, nx,ny are the size of x and y,
// fy is used for marking whether the k-th node is visited, matx[x] means x
// match matx[x], maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays start at 1

int nx,ny,mat[MAXN][MAXN],fy[MAXN],matx[MAXN],maty[MAXN];

int path(int u)
{
    int v;
    for(v=1;v<=ny;v++)
        if((mat[u][v])&&(fy[v]<0)) {
            fy[v]=1;
            if((maty[v]<0)||(path(maty[v]))) {
                matx[u]=v;
                maty[v]=u;
                return(1);
            } // end of if((maty[v]...
        } // end of if((mat[u][v]...
    return(0);
} // end of int path()

int MaximumMatch()
{
    int i,ret=0;
    memset(matx,-1,sizeof(matx));
    memset(maty,-1,sizeof(maty));
    for(i=1;i<=nx;i++)
        if(matx[i]<0) {
            memset(fy,-1,sizeof(fy));
            ret+=path(i);
        } // end of if(matx[i]...
    return(ret);
} // end of int MaximumMatch()
// ** End of MaximumMatch *********************************

KMP

Posted on by snoopy

直接抄的武大李春葆老师的数据结构上的改进KMP

// return the first matching string2 in the string1
#include <stdio.h>
#include <string.h>
#define MaxSize 1000

typedef struct
{
    char ch[MaxSize];
    int len;
} SqString;

void GetNextval(SqString t,int nextval[])
{
    int j=0,k=-1;
    nextval[0]=-1;
    while(j<t.len)
    {
        if((k==-1)||(t.ch[j]==t.ch[k]))
        {
            j++;
            k++;
            if(t.ch[j]!=t.ch[k]) nextval[j]=k;
            else nextval[j]=nextval[k];
        }
        else k=nextval[k];
    }
}

int KMP(SqString s,SqString t)
{
    int nextval[MaxSize],i=0,j=0,v;
    GetNextval(t,nextval);
    while((i<s.len)&&(j<t.len))
    {
        if((j==-1)||(s.ch[i]==t.ch[j]))
        {
            i++;
            j++;
        }
        else j=nextval[j];
    }
    if(j>=t.len) v=i-t.len;
    else v=-1;
    return(v);
}

int main()
{
//    freopen("kmp.in","r",stdin);
//    freopen("kmp.out","w",stdout);

    SqString str1,str2;
    gets(str1.ch);
    str1.len=strlen(str1.ch);
    gets(str2.ch);
    str2.len=strlen(str2.ch);
    printf("%dn",KMP(str1,str2));
    return(0);
}

RMQ

Posted on by snoopy

从whummd的blog上copy来的,加了点自己的修改,正在看,集训加油

// StandCode for RMQ, return the smallest number in array s[i..j]
#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 1000000
int f2[30];
int s[MAXN];
int r[MAXN][22];

void make_f2(int n)
{
    int i;
    for(i=0;i<=n;i++)
        f2[i]=1<<i;
    return;
}

void make_RMQ(int n)
{
    int i,j;
    for(i=1;i<=n;i++)
        r[i][0]=s[i];
    for(j=1;j<=log(n)/log(2);j++)
        for(i=1;i<=n;i++)
            r[i][j]=min(r[i][j-1],r[i+f2[j-1]][j-1]);
    return;
}

int RMQ(int i,int j)
{
    int k=int(log(j-i+1)/log(2));
    return(min(r[i][k],r[j-f2[k]+1][k]));
}

int main()
{
    freopen("rmp.in","r",stdin);
    freopen("rmp.out","w",stdout);

    int n,i,start,end;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&s[i]);
    make_f2(20);
    make_RMQ(n);
    while(scanf("%d%d",&start,&end)!=EOF)
        printf("%dn",RMQ(start,end));
    return 0;
}

在尝试IE7beta2和WindowsMediaPlayer11

Posted on by snoopy

RT.好奇啊…本来不是这么喜欢尝鲜的人的,但是挂在山水上做Software斑竹,好歹也要在其位谋其政吧.最近试用的东西不是太多了,但是比较敏感的东西还是在试,比较有代表性的就是IE7beta2和WindowsMediaPlayer11了吧.
自己已经发的关于这两个东西的意见都在武大珞珈山水BBS的Software上,也上了一些图.有图的Link写一下吧:
http://202.114.68.70/bbscon.php?bid=46&id=13141
http://202.114.68.70/bbscon.php?bid=46&id=13139
http://202.114.68.70/bbscon.php?bid=46&id=13000
http://202.114.68.70/bbscon.php?bid=46&id=12999

下面开始介绍,IE7beta2是微软官方发布的,所有WindowsXP用户均可使用,当然,现在要通过正版验证.我下了后传了一个到C.S.的ftp上,有兴趣的可以去看看.
ftp://cs:cs2006@cs.whu.edu.cn/incoming/IE7B2P-WindowsXP-x86-enu.exe

现在只有英文版的,还好一般软件的英文还是挺简单的,特别是这种常用软件,菜单也都能背下来了.IE7变PP了很多,很有Vista的风格,传统的菜单栏默认是不显示的,从而腾出了更多空间来浏览页面.

IE7默认就是分页浏览(Tabs),对Tab的配置可以进入Option里面调整(就是Internet选项啦),IE7还是加入了不少的新内容需要去适应.我的习惯都是在新的Tab里面打开网页,所以调了一下.不过好像在很多地方反应还是没Maxthon好,还是会去打开一个新的窗口就是一个新的IE而不是一个新的Tab.还有一个不是很爽的地方就是默认都是激活新的Tab页,没找到类似Maxthon那个选项,即打开新Tab后当前激活Tab是目前的还是新的.IE7里面对Tab的控制个人感觉还是不够人性化,经常出现点开一个新的Link然后覆盖了当前查看的内容.Tabs这个新的功能对那些习惯了Maxthon的人很不错,并且在打开非常多的Tab的时候上面不会成为一排密密麻麻的小标签,而是保持了一个最小宽度,左右加入了<>这样的滑动按钮.关闭Tab方面,IE7在有多个Tab的时候会在当前激活Tab的标签右边出现一个X号来关闭,要关闭非激活Tab需要先点激活然后关闭,无法跟Maxthon一样通过双击来实现.在只有一个Tab的情况下,无法关闭此Tab,就是说,没办法保持只有一个空的页面,当然,也可以通过新开一个新空白Tab然后关闭有内容的.存在多个Tab的情况下,IE7加入了一个缩略页的功能,可以同时显示多个小页面,能比较方便找到自己要的页面然后直接点开.

IE7里面加入的Feed是我非常喜欢的功能,虽然RSS这个Web2.0的一个前端概念早就知道也通过其他一些乱七八糟的RSS阅读器了解了一下,不过一直没太去刻意用这个.最近去看了看很多好朋友的Blog,发现如果只是用浏览器一个一个打开太慢了,刚好有Feed这个功能,就整合进去算了.现在没事刷新看看有没更新.然后打开Feed看,风格都比较统一,比较顺眼 :P

关于MS历来是一个诟病的资源占用问题,beta2的IE7解决的还是不好.我一般使用下都是75-90M内存,今天中午居然都截到了占有240M+内存,90%+CPU的图,当然,那个是我在开多个包含Flash,图片并且正在打开过程中截的,平时用Maxthon遇见这种情况也是比较卡.不过现在还好,我的Sempron2400+(1.833G)和512M内存跑起来没卡的感觉.

说完了IE7,我们来讨论WMP11,WMP11发布的消息我是在几天前知道的,然后就有人说5.17正式发布XP版,不过在昨天5Q上开始有泄漏出来的下载,开始没敢下,怕病毒,后来有人用了没问题就用吧.同样的,我也传了一个到C.S.的ftp服务器上:
ftp://cs:cs2006@cs.whu.edu.cn/incoming/mpsetup.exe

中午才下到的,没仔细测试乱七八糟的功能.第一反应是:PP了好多,为了Vista啊…然后是:真PP.

系统资源占有方面,没仔细注意,反正不卡,我上面那个IE截图240+M内存的时候就开了WMP.没去MS的主页看WMP11到底改变了什么,对我有影响的就是界面好看了很多,然后Library也好看了很多,没细看Library的功能变化.在对文件格式的支持上,我一般听的mp3和wma都没问题,不过还是不支持ape/cue,不能不说是一个遗憾.

WMP11还是没有加入官方的新皮肤,就是skin mode里面的,现在大家貌似还都是在用的9里面的那个,其他的个人都觉得不是很PP…

用了半天WMP11,唯一的感觉就是PP了好多,其他,没有了.呵呵,以后有了可以再发吧.

机器今天晚上准备重装,习惯…机器一直都还在裸奔,中毒不浅,QQ还连续被盗了两次,第一次是我去重庆了,结果天天在发垃圾消息,回来后被好友名单里半数拉黑名单了.55~第二次就在昨天吧,不过更多的是怀疑是系统的问题,好友丢失了近50个,奇怪.

西方俗语说:好奇会使猫丧命.希望不要太好奇真的让偶家猫猫挂了.乌鸦嘴:P

读书计划

Posted on by snoopy

不能一直只沉迷于同一件事情上,开始好好学点实用的东西.给自己一个计划,让自己好好进步.

HTML语言入门.五一前看完书,做基本的应用,开始接手维护OJ的首页.
离散数学及其应用.花一个学期好好看看吧,计算机科学的灵魂所在.
DreamWeaver.考四级前看完,能基本应用,以后可以考虑自己做东西玩.
Windows编程.用2个星期看完,串讲式的看一遍,了解一下.

有能力去看看asp和jsp吧,以后还想去维护OJ玩呢.

最后,四级.过掉,最好能漂亮的过掉.