学步园

题目：http://acm.hdu.edu.cn/showproblem.php?pid=3488

注：最小权二分匹配

源代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 305
#define INF 1e9　 　 　//不要太大

using namespace  std;

int n,m,cas,u,v,w;

int g[N][N],nx,ny; //需要初始化

int mx[N],my[N],lx[N],ly[N]; //lx[],ly[]为KM算法中Xi与Yi的顶点标号

bool sx[N],sy[N]; //标记是否在交错树上

int prev[N],slack[N]; //prev[i]为Y中i点在交错树上的前点；slack为松弛量

int q[N*2],head,tail;

void augment(int v){ //增广
    while(v!=-1){
        int pv=mx[prev[v]];
        mx[prev[v]]=v; my[v]=prev[v];v=pv;
    }
}

bool bfs(){
    while(head!=tail){
    int p=q[head++],u=p>>1;
    if(p & 1){
    if(my[u]==-1){ augment(u);return true; }
    else { q[tail++]=my[u]<<1; sx[my[u]]=true; }
    }
    else for(int i=0;i<ny;i++)
    if(sy[i])continue;
    else if(lx[u]+ly[i]!=g[u][i]){
    int ex=lx[u]+ly[i]-g[u][i];
    if(slack[i]>ex){ slack[i]=ex; prev[i]=u; }
    }
    else { prev[i]=u; sy[i]=true; q[tail++]=i*2+1; }
    }
    return false;
}

int KMmatch(bool maxsum ){ //默认为最大权匹配
    int i,j,ex,cost=0;
    if(!maxsum) for(i=0;i<nx;i++) for(j=0;j<ny;j++) g[i][j]*=-1;
    memset(mx,-1,sizeof(mx));
    memset(my,-1,sizeof(my));
    memset(ly,0,sizeof(ly));
    for(i=0;i<nx;i++)
    for(lx[i]=-INF,j=0;j<ny;j++)
    lx[i]=max(lx[i],g[i][j]);
    for(int live=0;live<nx;live++){
    memset(sx,0,sizeof(sx)); memset(sy,0,sizeof(sy));
    for(i=0;i<ny;i++)slack[i]=INF;
    head=tail=0; q[tail++]=live*2; sx[live]=true;
    while(!bfs()){
        for(ex=INF,i=0;i<ny;i++)if(!sy[i]) ex=min(ex,slack[i]);
        for(i=0;i<nx;i++) if(sx[i])lx[i]-=ex;
        for(j=0;j<ny;j++){ if(sy[j])ly[j]+=ex;slack[j]-=ex;}
        for(i=0;i<ny;i++)
        if(!sy[i] && slack[i]==0){q[tail++]=i*2+1;sy[i]=true;}
        }
    }
    if(!maxsum) for(i=0;i<nx;i++) for(j=0;j<ny;j++) g[i][j]*=-1;
    for(i=0;i<nx;i++)cost+=g[i][mx[i]];
    return cost;
}

int main()
{
    //freopen("F:\\a.txt","r",stdin);
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d %d",&n,&m);
        for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)
           g[i][j]=-INF;
        for(int i=0;i<m;i++)
        {
            scanf("%d %d %d",&u,&v,&w);
            if(g[u-1][v-1]<-w)
             g[u-1][v-1]=-w;
        }
        nx=ny=n;
        printf("%d\n",-KMmatch(true));
    }
}