RT, $O(N^3)$ 在$n <= 500$ 且时限两秒的情况下应该是能过的。然后我最后一个点永远超时。有没有大佬能帮忙优化一下？

#include <bits/stdc++.h>
using namespace std;
#define N 1010
#define ll long long

template <class T>
inline void read(T& a){
	T x = 0, s = 1;
	char c = getchar();
	while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
	a = x * s;
	return ;
}

struct edge{
  int u, v, next;
} t[N * 100];
int head[N];

int bian = 0;
inline void addedge(int u, int v){
  t[++bian] = (edge){u, v, head[u]}, head[u] = bian;
  return ; 
}

int lim[N];  // 最差礼物限制
int rev[N][N];  // 各礼物对于每个牛的排名
int G[N][N]; 
int ans[N]; 

int n; 

bool receive(int x, int opt){ 
  /*表示： x 和 opt 是可以互相交换的*/
  return rev[x][opt] < lim[x]; 
}

bool vis[N]; 


void dfs(int now, int hav, bool& flag){  // hav 为拖油瓶，一直找到可以互换为止，否则失败
  if(flag) return ; 
  vis[now] = 1; 
  for(int i = head[now]; i; i = t[i].next){
    int v = t[i].v; 
    if(vis[v]) continue ; 
    if(receive(v, hav)){
      flag = 1;
      break; 
    }
    else dfs(v, hav, flag); 
  }
  return ; 
}



int main(){
  // freopen("hh.txt", "r", stdin); 
  read(n);
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      int x; read(x); 
      G[i][j-1] = x;        // 记录内容
      rev[i][x] = j; 
      if(x == i) lim[i] = j;   // 排名
      if(!lim[i]){
        addedge(i, x);      // i 是可接受 x 的 
      }
    }
    ans[i] = i;  // 最差也是自己现在的
  }

  for(int i = 1; i <= n; i++){
    for(int j = 0; j < lim[i] - 1; j++){  // lim 之后及其自己的不用管
      int atte = G[i][j];  // 进行尝试
      if(receive(atte, i)){// 如果对面接受 
        ans[i] = G[i][j];   // 直接成功
        break; 
      }   
      else{ // 否则尝试多个
        bool flag = 0; 
        memset(vis, 0, sizeof(vis)); 
        vis[i] = 1; 
        dfs(atte, i, flag);   
        if(flag) {
          ans[i] = atte;
          break; 
        }
      }
    }
  }

  for(int i = 1; i <= n; i++)
    printf("%d\n", ans[i]); 
  return 0;
}

（蒟蒻就是因为不会闭包传递才写的 dfs）