hdu2426——Interesting Housing Problem

44424742

过得稀里糊涂，对最大权值的匹配还是不甚理解，明天继续！！！
终于对此算法有点理解了！不过，下面这个发现有些BUG，另贴一个！
#include<stdio.h>#include<string.h>#define INF 0xfffffffint g[502][502],s,r,e;int lx[502],ly[502],my[502],stack[502];bool vx[502],vy[502];int find(int v){    int i,temp;    vx[v]=true;    for(i=0;i<r;i++)    {        if(!vy[i])        {            temp=lx[v]+ly[i]-g[v][i];            if(temp==0)            {                vy[i]=true;                if(my[i]==-1||find(my[i]))                {                    my[i]=v;                    return true;                }            }            else if(temp<stack[i])                stack[i]=temp;        }    }    return false;}void KM(){    int i,j,min;    for(i=0;i<s;i++)    {        lx[i]=0;        for(j=0;j<r;j++)            if(lx[i]<g[i][j])                lx[i]=g[i][j];    }    for(j=0;j<r;j++)        ly[j]=0;    memset(my,-1,sizeof(my));    for(i=0;i<s;i++)    {        for(j=0;j<r;j++)            stack[j]=INF;        while(1)        {            memset(vx,false,sizeof(vx));            memset(vy,false,sizeof(vy));            min=INF;            if(find(i))                break;            for(j=0;j<r;j++)            {                if(!vy[j]&&stack[j]<min)                    min=stack[j];            }            for(j=0;j<s;j++)                if(vx[j])                    lx[j]-=min;            for(j=0;j<r;j++)            {                if(vy[j])                    ly[j]+=min;                else stack[j]-=min;            }        }    }}int main(){    int i,j,CASE=0,a,b,c,t;    while(scanf("%d%d%d",&s,&r,&e)!=EOF)    {        if(e==0)            printf("Case %d: %d\n",++CASE,-1);        else         {        for(i=0;i<s;i++)            for(j=0;j<r;j++)                g[i][j]=-INF;        while(e--)        {            scanf("%d%d%d",&a,&b,&c);            if(c>=0)                g[a][b]=c;        }        KM();            int ans=0,cnt=0;            for(i=0;i<r;i++)            {                t=my[i];                if(t>=0&&g[t][i]!=-INF)                {                    cnt++;                    ans+=g[t][i];                }            }            if(cnt<s)                ans=-1;            printf("Case %d: %d\n",++CASE,ans);        }    }    return 0;}
转：
#include<iostream>using namespace std;#define Max(a,b) (a)>(b) ? (a) : (b)#define Min(a,b) (a)<(b) ? (a) : (b)const int INF=0x7f7f7f7f;const int MAXN=501;int n,m,e,res;int w[MAXN][MAXN];int mat[MAXN],slack[MAXN];int lx[MAXN],ly[MAXN],vx[MAXN],vy[MAXN];bool dfs(int u){    int v,t;    vx[u]=1;    for(v=0;v<m;++v)    {        if(!vy[v])        {            t=lx[u]+ly[v]-w[u][v];            if(t==0)            {                vy[v]=1;                if(mat[v]==-1||dfs(mat[v]))                {                    mat[v]=u;return true;                }            }            else slack[v]=Min(slack[v],t);        }    }    return false;}bool km(){    memset(mat,-1,sizeof(mat));    memset(ly,0,m*sizeof(ly[0]));    for(int i=0;i<n;++i)    {        lx[i]=-INF;        for(int j=0;j<m;++j)    lx[i]=Max(lx[i],w[i][j]);        if(lx[i]==-INF)    return  false;    }    for(int i=0;i<n;++i)    {        memset(slack,127,m*sizeof(slack[0]));        while(true)        {            memset(vx,0,n*sizeof(vx[0]));            memset(vy,0,m*sizeof(vy[0]));            if(dfs(i))    break;            int d=INF;            for(int j=0;j<m;++j)    if(!vy[j])    d=Min(slack[j],d);            for(int j=0;j<n;++j)    if(vx[j])    lx[j]-=d;            for(int j=0;j<m;++j)    if(vy[j])    ly[j]+=d;        }    }    int cnt=res=0;    for(int i=0;i<m;++i)        if(mat[i]!=-1&&w[mat[i]][i]!=-INF)    res+=w[mat[i]][i],cnt++;    if(cnt==n)    return true;    return false;}int main(){    bool flag;    int s,r,v,len,tmp,num=0;    while(scanf("%d%d%d",&n,&m,&e)!=EOF)    {        flag=true;        if(n>m)        {            flag=false;            for(int i=0;i<e;++i)    scanf("%d%d%d",&s,&r,&v);        }        else        {            for(int i=0;i<n;++i)                for(int j=0;j<m;++j)    w[i][j]=-INF;            for(int i=0;i<e;++i)            {                scanf("%d%d%d",&s,&r,&v);                if(v>=0)    w[s][r]=v;            }            flag=km();        }        printf("Case %d: ",++num);        if(!flag)    printf("-1\n");        else printf("%d\n",res);    }    return 0;}