有两支队伍，分别有 \(n,\ m\) 个成员，每个成员都必须与对方所有成员竞技恰好一次。现在举行 \(\max(n,\ m)\) 次比赛，每次将会有 \(\min(n,\ m)\) 次竞技，且每个成员只能在这次比赛中竞技一次。

现在请确定一个的 \(n\times m\) 的时间表， \((i,\ j)\) 表示一队的 \(i\) 与二队的 \(j\) 在哪一场比赛中竞技，使得它的按行比较字典序最小

\(n,\ m\leq50\)

二分图匹配

---

考虑对于时间表的每一行做一次二分图匹配，在第 \(i\) 行，左部 \(m\) 个点表示第 \(i\) 行的每一列，右部 \(\max(n,\ m)\) 个点表示比赛时间

若 \(n\leq m\) ，可以直接得到完美匹配，但若 \(n>m\) ，左部点个数小于右部点，直接匈牙利可能会导致时间表中某些地方没有匹配

若一个右部点满足在前 \(i-1\) 轮共匹配了 \(m-n+i-1\) 次，则第 \(i\) 轮必须匹配。考虑在左部建出 \(n-m\) 个虚点，若一个点不是必须匹配的，则将它与虚点连边

此外，问了保证字典序最小，还需再跑一遍匈牙利重组一次

时间复杂度 \(O(n^4)\)

代码

#include 
    
     using namespace std;const int maxn = 55;bool vis[maxn], e[maxn][maxn];int n, m, k, now, mat[maxn], sum[maxn], data[maxn];inline char get(int x) {  if (x < 10) return x | 48;  if (x < 36) return x - 10 + 'A';  return x - 36 + 'a';}bool dfs1(int u) {  if (vis[u]) return 0;  vis[u] = 1;  for (int v = 1; v <= k; v++) {    if (e[u][v] && (!mat[v] || dfs1(mat[v]))) {      return mat[v] = u, 1;    }  }  return 0;}bool dfs2(int u) {  if (vis[u]) return 0;  vis[u] = 1;  for (int v = 1; v <= k; v++) {    if (e[u][v] && (mat[v] == now || (mat[v] > now && dfs2(mat[v])))) {      return mat[v] = u, 1;    }  }  return 0;}struct TheContest {  vector 
     
       getSchedule(int N, int M) {    vector 
      
        ans;    memset(e, 1, sizeof e);    n = N, m = M, k = max(n, m);    for (int T = 1; T <= n; T++) {      string str = "";      memset(mat, 0, sizeof mat);      for (int i = m + 1; i <= k; i++) {        for (int j = 1; j <= k; j++) {          e[i][j] = sum[j] + n - T + 1 != m;        }      }      for (int i = 1; i <= k; i++) {        memset(vis, 0, sizeof vis);        dfs1(i);      }      for (int i = 1; i <= k; i++) {        memset(vis, 0, sizeof vis);        now = i, dfs2(i);      }      for (int i = 1; i <= k; i++) {        if (mat[i] <= m) {          e[mat[i]][i] = 0;          data[mat[i]] = i, sum[i]++;        }      }      for (int i = 1; i <= m; i++) {        str += get(data[i]);      }      ans.push_back(str);    }    return ans;  }};