刚学费用流，KM 算法和 Dinic 算法都试了下，但是只通过前面两个点，其他全部 TLE。求大佬帮忙看看

KM：

#include<bits/stdc++.h>
#define MAXN 200
#define MAXM 40000
#define INF 0x3f3f3f3f
using namespace std;
struct edge{
    int pre, to, flow, cost;
};
int n, cnt = 1, s, t, cst, flw, ban = -1;
int head[MAXN], dis[MAXN], dep[MAXN], cur[MAXN], flow[MAXN], pre[MAXN];
bool vis[MAXN];
edge e[MAXM], et[MAXM];
vector<pair<int, int>> res;
void add_edge(int u, int v, int f, int c){
    e[++cnt].pre = head[u]; e[cnt].to = v; e[cnt].flow = f; e[cnt].cost = c; head[u] = cnt;
    e[++cnt].pre = head[v]; e[cnt].to = u; e[cnt].flow = 0; e[cnt].cost = -c; head[v] = cnt;
}

bool SPFA(){
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    queue<int> q; q.push(s);
    vis[s] = true; dis[s] = 0; flow[s] = INF;
    while(!q.empty()){
        int now = q.front(); q.pop();
        vis[now] = false;
        for(int i = head[now]; i; i = e[i].pre){
            if(i == ban || (i ^ 1) == ban) continue;
            if(e[i].flow != 0 && dis[e[i].to] > dis[now] + e[i].cost){
                flow[e[i].to] = min(flow[now], e[i].flow);
                dis[e[i].to] = dis[now] + e[i].cost;
                pre[e[i].to] = i;
                if(!vis[e[i].to]){
                    q.push(e[i].to);
                    vis[e[i].to] = true;
                }
            }
        }
    }
    return !(dis[t] == INF);
}
void update(){
    int now = t;
    while(now != s){
        e[pre[now]].flow -= flow[t];
        e[pre[now] ^ 1].flow += flow[t];
        now = e[pre[now] ^ 1].to;
    }
    flw += flow[t];
    cst += dis[t] * flow[t];
}
int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int x; scanf("%d",&x);
            add_edge(i, n + j, 1, -x);
        }
    }
    s = n * 2 + 1; t = s + 1;
    for(int i = 1; i <= n; i++) add_edge(s, i, 1, 0);
    for(int i = 1; i <= n; i++) add_edge(n + i, t, 1, 0);
    memcpy(et, e, sizeof(e));
    int final_f = 0, final_c = 0;
    while(SPFA()) update();
    final_c = cst;
    printf("%d\n",-final_c);
    for(int i = 2; i <= cnt; i += 2){
        if(e[i].to == s || e[i].to == t) continue;
        if(e[i ^ 1].to == s || e[i ^ 1].to == t) continue;
        ban = i; cst = 0; flw = 0;
        memcpy(e, et, sizeof(et));
        while(SPFA()) update();
        if(cst != final_c) res.push_back(make_pair(e[i ^ 1].to, e[i].to - n));
    }
    sort(res.begin(), res.end());
    for(int i = 0; i < res.size(); i++) printf("%d %d\n",res[i].first,res[i].second);
    return 0;
}

Dinic：

#include<bits/stdc++.h>
#define MAXN 200
#define MAXM 40000
#define INF 0x3f3f3f3f
using namespace std;
struct edge{
    int pre, to, flow, cost;
};
int n, cnt = 1, s, t, cst, ban = -1;
int head[MAXN], dis[MAXN], dep[MAXN], cur[MAXN];
bool vis[MAXN];
edge e[MAXM], et[MAXM];
vector<pair<int, int>> res;
void add_edge(int u, int v, int f, int c){
    e[++cnt].pre = head[u]; e[cnt].to = v; e[cnt].flow = f; e[cnt].cost = c; head[u] = cnt;
    e[++cnt].pre = head[v]; e[cnt].to = u; e[cnt].flow = 0; e[cnt].cost = -c; head[v] = cnt;
}
bool SPFA(){
    memset(dep, 0, sizeof(dep));
    memset(dis, 0x3f, sizeof(dis));
    queue<int> q; q.push(s);
    vis[s] = false; dis[s] = 0; dep[s] = 0;
    while(!q.empty()){
        int now = q.front(); q.pop(); vis[now] = false;
        for(int i = head[now]; i; i = e[i].pre){
            if(i == ban || (i ^ 1) == ban) continue;
            if(e[i].flow != 0 && dis[e[i].to] > dis[now] + e[i].cost){
                dis[e[i].to] = dis[now] + e[i].cost;
                dep[e[i].to] = dep[now] + 1;
                if(!vis[e[i].to]){
                    q.push(e[i].to);
                    vis[e[i].to] = true;
                }
            }
        }
    }
    return !(dis[t] == INF);
}
int dfs(int now, int lim){
    if(now == t) return lim;
    int res = 0;
    for(int i = head[now]; i && lim > 0; i = e[i].pre){
        cur[now] = i;
        if(i == ban || (i ^ 1) == ban) continue;
        if(dep[e[i].to] != dep[now] + 1 || e[i].flow == 0 || dis[e[i].to] != dis[now] + e[i].cost) continue;
        int incf = dfs(e[i].to, min(lim, e[i].flow));
        if(incf == 0) dep[e[i].to] = 0;
        e[i].flow -= incf; e[i ^ 1].flow += incf;
        res += incf; cst += incf * e[i].cost; lim -= incf;
    }
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int x; scanf("%d",&x);
            add_edge(i, n + j, 1, -x);
        }
    }
    s = n * 2 + 1; t = s + 1;
    for(int i = 1; i <= n; i++) add_edge(s, i, 1, 0);
    for(int i = 1; i <= n; i++) add_edge(n + i, t, 1, 0);
    memcpy(et, e, sizeof(e));
    int final_f = 0, final_c = 0;
    while(SPFA()){
        memcpy(cur, head, sizeof(cur));
        final_f += dfs(s, INF);
    }
    final_c = cst;
    printf("%d\n",-final_c);
    for(int i = 2; i <= cnt; i += 2){
        if(e[i].to == s || e[i].to == t) continue;
        if(e[i ^ 1].to == s || e[i ^ 1].to == t) continue;
        ban = i; cst = 0;
        int flow = 0;
        memcpy(e, et, sizeof(et));
        while(SPFA()){
            memcpy(cur, head, sizeof(cur));
            flow += dfs(s, INF);
        }
        if(cst != final_c) res.push_back(make_pair(e[i ^ 1].to, e[i].to - n));
    }
    sort(res.begin(), res.end());
    for(int i = 0; i < res.size(); i++) printf("%d %d\n",res[i].first,res[i].second);
    return 0;
}