题面

传送门

Sol

网络流辣

枚举每个点的最优匹配，然后只建最优匹配的边跑网络流 下一个点的图中，保证上一个点只连了最优匹配的边 直接整个图复制过来

然后二分答案一个点向上跳多少 和上面一样建图 check c h e c k

# include <bits/stdc++.h> # define RG register # define IL inline # define Fill(a, b) memset(a, b, sizeof(a)) # define Copy(a, b) memcpy(a, b, sizeof(a)) # define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout) using namespace std; typedef long long ll; template <class Int> IL void Input(RG Int &x){ RG int z = 1; RG char c = getchar(); x = 0; for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1; for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); x *= z; } const int maxn(405); const int oo(1e9); int testcase, c, n, m, b[maxn], s[maxn], S, T, ans[maxn]; queue <int> Q; struct Max_Flow{ int max_flow, cur[maxn], first[maxn], cnt, lev[maxn]; struct Edge{ int to, f, next; } edge[maxn * 20]; IL void Init(){ cnt = 0, Fill(first, -1); } IL void Add(RG int u, RG int v, RG int f){ edge[cnt] = (Edge){v, f, first[u]}, first[u] = cnt++; edge[cnt] = (Edge){u, 0, first[v]}, first[v] = cnt++; } IL int Dfs(RG int u, RG int maxf){ if(u == T) return maxf; RG int ret = 0; for(RG int &e = cur[u]; e != -1; e = edge[e].next){ RG int v = edge[e].to; if(lev[v] != lev[u] + 1 || !edge[e].f) continue; RG int f = Dfs(v, min(edge[e].f, maxf - ret)); ret += f, edge[e].f -= f, edge[e ^ 1].f += f; if(ret == maxf) break; } if(!ret) lev[u] = 0; return ret; } IL int Bfs(){ Fill(lev, 0), Q.push(S), lev[S] = 1; while(!Q.empty()){ RG int u = Q.front(); Q.pop(); for(RG int e = first[u]; e != -1; e = edge[e].next){ RG int v = edge[e].to; if(!edge[e].f || lev[v]) continue; lev[v] = lev[u] + 1; Q.push(v); } } return lev[T]; } IL int Dinic(){ max_flow = 0; while(Bfs()) Copy(cur, first), max_flow += Dfs(S, oo); return max_flow; } } mp[maxn], tmp; struct Map{ int first[maxn], cnt; struct Edge{ int to, next; } edge[maxn * 10]; IL void Init(){ cnt = 0, Fill(first, -1); } IL void Add(RG int u, RG int v){ edge[cnt] = (Edge){v, first[u]}, first[u] = cnt++; } } edge[maxn]; int main(RG int argc, RG char *argv[]){ File("mentor"); for(Input(testcase), Input(c); testcase; --testcase){ Input(n), Input(m), T = n + m + 1; for(RG int i = 0; i <= n; ++i) mp[i].Init(), ans[i] = 0; for(RG int i = 1; i <= m; ++i) Input(b[i]), mp[0].Add(i + n, T, b[i]); for(RG int i = 1; i <= m; ++i) edge[i].Init(); for(RG int i = 1; i <= n; ++i){ for(RG int j = 1, x; j <= m; ++j){ Input(x); if(x) edge[x].Add(i, j + n); } for(RG int j = 1; j <= m; ++j){ for(RG int k = S; k <= T; ++k) mp[i].first[k] = mp[i - 1].first[k]; mp[i].cnt = mp[i - 1].cnt; for(RG int k = 0; k < mp[i].cnt; ++k) mp[i].edge[k] = mp[i - 1].edge[k]; mp[i].Add(S, i, 1); for(RG int e = edge[j].first[i]; e != -1; e = edge[j].edge[e].next) mp[i].Add(i, edge[j].edge[e].to, 1); if(mp[i].Dinic()){ ans[i] = j; break; } } if(!ans[i]) ans[i] = m + 1; printf("%d ", ans[i]); } puts(""); for(RG int i = 1; i <= n; ++i) Input(s[i]); for(RG int i = 1; i <= n; ++i){ if(ans[i] <= s[i]){ putchar('0'), putchar(' '); continue; } RG int l = 1, r = i - 1, ret = 0; while(l <= r){ RG int mid = (l + r) >> 1; for(RG int k = S; k <= T; ++k) tmp.first[k] = mp[mid - 1].first[k]; tmp.cnt = mp[mid - 1].cnt; for(RG int k = 0; k < mp[mid - 1].cnt; ++k) tmp.edge[k] = mp[mid - 1].edge[k]; tmp.Add(S, i, 1); for(RG int j = 1; j <= s[i]; ++j) for(RG int e = edge[j].first[i]; e != -1; e = edge[j].edge[e].next) tmp.Add(i, edge[j].edge[e].to, 1); if(tmp.Dinic()) ret = mid, l = mid + 1; else r = mid - 1; } printf("%d ", i - ret); } puts(""); } return 0; }