不知道这个Zayid是谁...
题意：
有n个人，m个导师。每个导师能接纳bi个人，每个人对于这m个导师都有一个志愿档次。
优先满足靠前的人，问到最后每个人匹配的导师是他的第几志愿。
每个人又有一个限制si，问至少前进多少名才能被志愿档次不大于si的导师录取。
解：
首先发现，每个志愿档次只能填一个人的时候，可以直接贪心。否则在同一志愿档次内选择不同的导师会对后面有影响。
这时我们就可以利用网络流。
一个流量代表一个的归属，动态加边。
对于每个人枚举志愿档次，添加流向导师的边。然后看是否有流量。
如果有流量那么他就归于该志愿档次。
第二问，答案可以二分。
很简朴的想法是对于每个二分出来的值，重新建图来一遍。这样复杂度就是Tnlogn * nm，显然不行。
发现每次重新建图的时候我们进行了很多一模一样的操作。于是考虑把前k个人的网络流状态保存下来，之后直接调用。
但是太麻烦了...我们又发现一种很巧妙的方法：判断在前k个人加完之后是否可行，其实是看哪些导师还可以接纳人。于是我们从汇点出发，反向DFS，能够得到每次从哪些导师出发有增广路，就是哪些导师还能接纳。
然后二分的时候直接O(m)判定。
这样我们发现有90分，超时一个点。
回想第一问网络流的时候，如果一个志愿档次没有流量，那么这些加的边就没有用，不妨删了。
然后就A了...
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm> const int N = , INF = 0x3f3f3f3f; int b[N], C, n, m, a[N][N], s[N], mat[N];
std::vector<int> topo[N][N]; namespace fl { struct Edge {
int nex, v, c;
}edge[]; int top = ; int d[N << ], e[N << ], E[N << ], TOP;
bool vis[N][N << ];
std::queue<int> Q; inline void add(int x, int y, int z) {
top++;
edge[top].v = y;
edge[top].c = z;
edge[top].nex = e[x];
e[x] = top; top++;
edge[top].v = x;
edge[top].c = ;
edge[top].nex = e[y];
e[y] = top;
return;
} inline bool BFS(int s, int t) {
memset(d, , sizeof(d));
d[s] = ;
Q.push(s);
while(!Q.empty()) {
int x = Q.front();
Q.pop();
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(!edge[i].c || d[y]) {
continue;
}
d[y] = d[x] + ;
Q.push(y);
}
}
return d[t];
} int DFS(int x, int t, int maxF) {
if(x == t) {
return maxF;
}
int Ans = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(!edge[i].c || d[x] + != d[y]) {
continue;
}
int temp = DFS(y, t, std::min(edge[i].c, maxF - Ans));
if(!temp) {
d[y] = INF;
}
Ans += temp;
edge[i].c -= temp;
edge[i ^ ].c += temp;
if(Ans == maxF) {
break;
}
}
return Ans;
} inline int dinic(int s, int t) {
int Ans = ;
while(BFS(s, t)) {
Ans += DFS(s, t, INF);
}
return Ans;
} void DFS(int x, int k) {
vis[k][x] = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(!edge[i ^ ].c || vis[k][y]) {
continue;
}
DFS(y, k);
}
return;
} inline bool check(int x, int mid) {
for(int k = ; k <= s[x]; k++) {
for(int jj = topo[x][k].size() - ; jj >= ; jj--) {
int j = topo[x][k][jj];
if(vis[x - mid - ][j + n]) {
return ;
}
}
}
return ;
} inline void solve() {
memset(vis[], -, sizeof(vis[]));
int S = n + m + , T = n + m + ;
for(int i = ; i <= m; i++) {
add(n + i, T, b[i]);
}
for(int i = ; i <= n; i++) {
add(S, i, );
mat[i] = ;
for(int k = ; k <= m; k++) {
TOP = top;
E[i] = e[i];
for(int jj = topo[i][k].size() - ; jj >= ; jj--) {
int j = topo[i][k][jj];
E[n + j] = e[n + j];
add(i, n + j, );
}
int temp = dinic(S, T);
if(temp) {
mat[i] = k;
break;
}
else {
e[i] = E[i];
for(int jj = topo[i][k].size() - ; jj >= ; jj--) {
int j = topo[i][k][jj];
e[n + j] = E[n + j];
}
top = TOP;
}
}
if(!mat[i]) {
mat[i] = m + ;
}
DFS(T, i);
}
for(int i = ; i <= n; i++) {
printf("%d ", mat[i]);
}
puts("");
// first OVER for(int i = ; i <= n; i++) {
if(mat[i] <= s[i]) {
printf("0 ");
continue;
}
int l = , r = i;
while(l < r) {
int mid = (l + r) >> ;
if(check(i, mid)) {
r = mid;
}
else {
l = mid + ;
}
}
printf("%d ", r);
}
puts("");
return;
} inline void clear() {
memset(e, , sizeof(e));
top = ;
memset(vis, , sizeof(vis));
return;
}
} inline void solve() {
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) {
scanf("%d", &b[i]);
}
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
scanf("%d", &a[i][j]);
if(a[i][j]) {
topo[i][a[i][j]].push_back(j);
}
}
}
for(int i = ; i <= n; i++) {
scanf("%d", &s[i]);
}
// read over fl::solve();
return;
} inline void clear() {
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
topo[i][j].clear();
}
}
fl::clear();
return;
} int main() { int T;
scanf("%d%d", &T, &C);
while(T--) {
solve();
if(T) {
clear();
}
}
return ;
}
AC代码
我发现D2T1都好毒瘤...屠龙勇士也是的。