dfs版本ac了
但为什么bfs版本跑第二个KM会tle （有无佬救救=_+）

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int N = 55, inf = 0x3f3f3f3f;

int d[N][N];  //邻接矩阵--后续用到边，所以方便

int matcha[N],matchb[N];  //女朋友编号  /  女朋友编号

int la[N],lb[N];  //顶标
bool va[N],vb[N];  //交错路上的结点标记
int slack[N];  //顶标和  与  边权的差值  （取最小）
int pre[N];  //交错路从男生->女生的男生编号
queue<int> q;  //交错路的男生编号

//题目给的
int n;

inline int read()  //每次读入一个数字
{
    int x = 0, f = 1;  //数值  符号

    char ch = getchar();

    while(ch<'0'||ch>'9')  //负号
    {
        if(ch=='-') f = -1;

        ch = getchar();
    }

    while(ch>='0'&&ch<='9')  //字符变整数
    {
        x = x*10 + (ch-'0');

        ch = getchar();
    }


    return f*x;
}

inline void write(int x)
{
    if(x<0) putchar('-'), x=-x;  //类似__int128的输出

    if(x>9) write(x/10);  //找到最前面

    putchar('0'+x%10);
}

void aug(int v)
{
    while(v) //回溯到起点，起点的原女朋友为0
    {
        int tmp = matcha[pre[v]];

        matcha[pre[v]] = v;

        matchb[v] = pre[v];

        v = tmp;
    }
}

void find(int x)
{
    q.push(x);

    while(true)  //知道找到增广路为止
    {
        //1.尝试走交错路
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            va[u] = true;  //交错路上男生结点标记

            for(int v=1;v<=n;v++)  //一定有边
            {
                if(vb[v]) continue;  //被虚拟标记了

                if(la[u]+lb[v]-d[u][v]<slack[v])  //取更小
                {
                    slack[v] = la[u]+lb[v]-d[u][v];
                    pre[v] = u;  //设置巧妙，后续一旦差值变为0，
                    //就可以直接继续跑交错路了

                    if(slack[v]==0)  //是相等子图的边
                    {
                        vb[v] = true;  //加入交错路

                        //没男朋友--找到增广路了
                        if(!matchb[v]) 
                        {
                            aug(v);  //增广路回溯
                            return;  //皆大欢喜
                        }
                        else
                        q.push(matchb[v]);  //继续走交错路
                    }
                }
            }

        }

        //2.找不到增广路了--修改顶标--缩小边的差值
        int delta = inf;
        for(int i=1;i<=n;i++) if(!vb[i]) delta = min(delta,slack[i]);

        for(int i=1;i<=n;i++)
        {
            if(va[i]) la[i] -= delta;

            if(vb[i]) lb[i] += delta;
            else slack[i] -= delta;  //差距缩小了
        }

        //加入新边
        for(int i=1;i<=n;i++)
          if(!vb[i]&&slack[i]==0)
          {
              vb[i] = true;  //加入交错路

              if(!matchb[i])
              {
                  aug(i);
                  return;
              }
              else
              q.push(matchb[i]);
          }
    }
}

void KM()
{
    //初始化match  (重新连边)
    memset(matcha,0,sizeof matcha);
    memset(matchb,0,sizeof matchb);

    //1.初始化顶标
    fill(la+1,la+1+n,-inf);   //等下第二次KM，权值有负数了

    for(int i=1;i<=n;i++)   //边权最大
      for(int j=1;j<=n;j++)
        la[i] = max(la[i],d[i][j]);

    // //lb初始化0  
    memset(lb,0,sizeof lb);  //要跑两次KM

    //2.开始求”相等子图“的完美匹配
    for(int i=1;i<=n;i++) //只跑一遍交错路
    {
        //初始化，重新跑交错路
        memset(va,0,sizeof va);
        memset(vb,0,sizeof vb);
        fill(slack+1,slack+1+n,inf);
        memset(pre,0,sizeof pre);

        if(!q.empty()) q.pop();

        find(i);  //一定可以找到女孩纸
    }
}

int main()
{
    n = read();

    //加边 （必定有边）
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        d[i][j] = read();

    //跑KM算法
    KM();

    int max_ans = 0;
    for(int i=1;i<=n;i++)
      max_ans += d[matchb[i]][i];



    //负边 （必定有边）
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
          d[i][j] *= -1;


    //跑KM算法
    KM();       

    int min_ans = 0;
    for(int i=1;i<=n;i++)
      min_ans += d[matchb[i]][i];    

    write(-min_ans);  putchar('\n');
    write(max_ans);  putchar('\n');

    return 0;
}