今天心情不错，早上起来按部就班收拾自己，收拾书包，启程去苏州街75号，鼎钧大厦，考我希望是最后一次的GRE AW test。九点出发，到明光桥北等公交，490先于304到了，于是决定坐490转地铁，放弃等那个不知道多久能来一趟的304。9点45到达考场休息室，等着开始，9点56分左右进来三个奇形怪状的非主流，怎么看都不像GRE的，果不其然，他们是考护士的。于是我更担心的事情出现了：他们考上护士了是不是很危险。10点17分的时候后来被发现很NICE的考官甲出现了，叫我们领表和钥匙。之后是存包，交表，听考官乙用京腔讲的注意事项。之后是排队等着进场，我本来排在第四位，在一位记者朋友同志前面。结果我刚坐到登记用的电脑前就被告知我还要等等，因为前面那场用我即将使用的那台电脑的同学还在答题。于是我想到了两件事：第一，那个同学一定详细的填好了前面的22道令人不安且愤慨的背景调查部分，并且在选校环节异常纠结（因为随后当我被告知她/他还有两所学校要选之后，我又等了15分钟才被准许进场。当然，按照arguement精神，我还没排除他/她是否错点了remove all selected schools按钮，并重新选择了4所学校，或者他/她中间有什么不适晕过去了15分钟的可能性，我不能说他/她选校很纠结）；第二，ETS的机考每个考生所用的机器是事先安排好并不能随时更换的，否则应该是由排在队尾的那个面相狰狞的女同学来承担最后进场的等待的煎熬。在等待的过程中，那个考官甲在看到我来回踱步并嘴里默念着什么的时候对我投来了nice的笑容。当我终于进场时，我发现很多人的issue几乎已经写完了。不过，不过，这个不过很重要，不过，随后我的人品就爆发了，issue两题都很熟悉，并读过范文，做过练习，选择其中一个感觉逻辑更清晰的飞快的敲了出来，之后arguement是那个经典的west egg，不知道为什么，我就是对这个west egg很有印象。之后happy happy的敲完了arguement的5个正文段落。我想说的是，这学期以来积攒的人品终于爆发了。还有很重要的一点是，baidu终于收录了我的16个页面，yahoo也开始有了收录。
心情这么好，就废话了一大堆，下面是正文：
题目:poj2195,最小费用最大流。poj2195 Going Home。http://poj.org/problem?id=2195
题意:求几个原点到几个终点的最小费用最大流。有可能输出最小费用，不可能输出不可能。每个终点可接收1个单位的流，每个起点释放1个单位的流。
解法：最小费用最大流。这题poj2195是费用流的一个变形，我们加入两个超级节点，起点连接每个图中的源点，容量1，长度0，终点的处理方法相同。于是在这张图上费用流之。
代码:

#include<iostream>
#include<queue>
using namespace std;
int n,m,k,s,t,ans;
int xm[250],ym[250],xh[250],yh[250];
int map[520][520],c[520][520],f[520][520],d[520],p[520];
bool v[520];
char in[250][250];
int getpath()
{
    int cur,i;
    memset(d,127,sizeof(d));
    memset(v,0,sizeof(v));
    queue<int> q;
    d[s]=0;
    for(i=0;i<=t;i++)
    p[i]=-1;
    q.push(0);
    v[0]=1;
    while(!q.empty())
    {
        cur=q.front();
        q.pop();
        v[cur]=0;
        for(i=0;i<=t;i++)
        {
            if(c[cur][i]>f[cur][i]&amp;&amp;d[i]>d[cur]+map[cur][i])
            {
                d[i]=d[cur]+map[cur][i];
                p[i]=cur;
                if(!v[i])
                {
                    q.push(i);
                    v[i]=1;
                }
            }
        }
    }
    if(p[t]==-1)
    return 0;
    return 1;
}
void solve()
{
    int i,j,it;
    while(getpath())
    {
        it=t;
        while(p[it]!=-1)
        {
            f[p[it]][it]+=1;
            f[it][p[it]]-=1;
            it=p[it];
        }
    }
    ans=0;
    for(i=1;i<=k;i++)
    for(j=1;j<=k;j++)
    {
        ans+=f[i][k+j]*map[i][k+j];
    }
}
int main()
{
    int i,j,posm,posh;
    while(scanf("%d%d",&amp;n,&amp;m)!=EOF&amp;&amp;m+n!=0)
    {
        for(i=0;i<n;i++)
        {
            scanf("%s",in[i]);
        }
        posm=1;
        posh=1;
        for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        {
            if(in[i][j]=='m')
            {
                xm[posm]=i;
                ym[posm++]=j;
            }
            else if(in[i][j]=='H')
            {
                xh[posh]=i;
                yh[posh++]=j;
            }
        }
        memset(map,0,sizeof(map));
        k=posm-1;
        for(i=1;i<=k;i++)
        {
            for(j=1;j<=k;j++)
            {
                map[i][k+j]=abs(xm[i]-xh[j])+abs(ym[i]-yh[j]);
                map[k+j][i]=-map[i][k+j];
            }
        }
        s=0;t=2*k+1;
        memset(c,0,sizeof(c));
        for(i=1;i<=k;i++)
        {
            c[0][i]=1;
            c[i+k][t]=1;
        }
        for(i=1;i<=k;i++)
        for(j=1;j<=k;j++)
        c[i][k+j]=1;
        memset(f,0,sizeof(f));
        solve();
        printf("%dn",ans);
    }
}