题面
Sol
网络流辣
枚举每个点的最优匹配，然后只建最优匹配的边跑网络流
下一个点的图中，保证上一个点只连了最优匹配的边
直接整个图复制过来
然后二分答案一个点向上跳多少
和上面一样建图(check)
# 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;
}