带权二分图最优匹配(KM)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<cstdlib>
#include<cctype>
#define ll long long
#define ld long double
#define rep(i,a,b) for(int i = a;i<=b;++i)
#define mem(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f

using namespace std;
const int N = 110;
int n;
int weight[N][N];
int cx[N],cy[N];
bool sx[N],sy[N];
int match[N];

inline int read()
{
    int num = 0, w=0;char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch = getchar();}
    while(isdigit(ch)){num = (num<<3) + (num<<1) + (ch^48);ch = getchar();}
    return w? -num: num;
}
inline void write(int x)
{
    if(x<0){putchar('-');x = -x;}
    if(x>9) write(x / 10);
    putchar(x % 10 + '0');
}
void fast()
{ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
int dfs(int u)
{
    sx[u] = 1;
    rep(v,1,n)
    {
        if(!sy[v]&&cx[u]+cy[v]==weight[u][v])
        {
            sy[v] = 1;
            if(match[v]==-1||dfs(match[v]))
            {
                match[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
int km(bool max_weight)
{
    if(!max_weight)//如果求最小匹配,权值取反
    {
        rep(i,1,n)
        {
            rep(j,1,n)
            {
                weight[i][j] = - weight[i][j];
            }
        }
    }
    //初始化顶标，cx[i] = max(weight[i][j]|j=1,2,3...n)cy[i] = 0;
    rep(i,1,n)
    {
        cy[i] = 0;
        cx[i] = -INF;
        rep(j,1,n)
        {
            if(cx[i]<weight[i][j])
            {
                cx[i] = weight[i][j];
            }
        }
    }
    mem(match,-1);
    //不断修改顶标，直到找到完备或完美匹配
    rep(u,1,n)//为x里的每一个点找到匹配
    {
        while(1)
        {
            mem(sx,0);
            mem(sy,0);
            if(dfs(u))//若x[u],在相等子图找到匹配，继续为下一个点找匹配
                break;
            //如果没在相等子图里找到匹配，就修改顶标，直到找到匹配为止
            //首先找到修改顶标时的增量inc，min(cx[i]+cy[i]-weight[i][j],inc)
            //cx[i] 为搜索过的点，cy[i]是未搜索过的点，
            //因为现在是要给u找匹配，所以只需要修改找的过程中搜索过的点，增加有可能对u有帮助的边
            int inc = INF;
            rep(i,1,n)
            {
                if(sx[i])
                {
                    rep(j,1,n)
                    {
                        if(!sy[j]&&((cx[i]+cy[i]-weight[i][j])<inc))
                        {
                            inc = cx[i]+cy[i]-weight[i][j];
                        }
                    }
                }
            }
            //找到增量后修改顶标，因为sx[i]与sy[j]都为真，则必然符合cx[i]+cy[j] = weight[i][j],
            //然后cx[i]-inc,cy[j]+inc,不会改变等式，但是原来的cx[i]+cx[j]!=weight[i][j],
            //即sx[i]与sy[j]最多一个为真，cx[i]+cy[j]就会发生改变，从而符合等式，边也就加入相等子图
            rep(i,1,n)
            {
                if(sx[i])
                    cx[i]-=inc;
                if(sy[i])
                    cy[i]+=inc;
            }

        }
    }
    int sum = 0;
    rep(i,1,n)
    {
        if(match[i]>0)
        {
            sum+=weight[match[i]][i];
        }
    }
    if(!max_weight)
        sum = -sum;
    return sum;
}
int main()
{
   while(cin>>n)
   {
       rep(i,1,n)
       {
           rep(j,1,n)
           {
               cin>>weight[i][j];
           }
       }
       cout<<km(1)<<endl;
   }
   system("pause");
   return 0;
}