不知道这个Zayid是谁...
题意：
有n个人，m个导师。每个导师能接纳bi个人，每个人对于这m个导师都有一个志愿档次。
优先满足靠前的人，问到最后每个人匹配的导师是他的第几志愿。
每个人又有一个限制si，问至少前进多少名才能被志愿档次不大于si的导师录取。
解：
首先发现，每个志愿档次只能填一个人的时候，可以直接贪心。否则在同一志愿档次内选择不同的导师会对后面有影响。
这时我们就可以利用网络流。
一个流量代表一个的归属，动态加边。
对于每个人枚举志愿档次，添加流向导师的边。然后看是否有流量。
如果有流量那么他就归于该志愿档次。
第二问，答案可以二分。
很简朴的想法是对于每个二分出来的值，重新建图来一遍。这样复杂度就是Tnlogn * nm，显然不行。
发现每次重新建图的时候我们进行了很多一模一样的操作。于是考虑把前k个人的网络流状态保存下来，之后直接调用。
但是太麻烦了...我们又发现一种很巧妙的方法：判断在前k个人加完之后是否可行，其实是看哪些导师还可以接纳人。于是我们从汇点出发，反向DFS，能够得到每次从哪些导师出发有增广路，就是哪些导师还能接纳。
然后二分的时候直接O(m)判定。
这样我们发现有90分，超时一个点。
回想第一问网络流的时候，如果一个志愿档次没有流量，那么这些加的边就没有用，不妨删了。
然后就A了...
1 #include2 #include 3 #include 4 #include 5 #include 6 7 const int N = 210, INF = 0x3f3f3f3f; 8 9 int b[N], C, n, m, a[N][N], s[N], mat[N]; 10 std::vector topo[N][N]; 11 12 namespace fl { 13 14 struct Edge { 15 int nex, v, c; 16 }edge[2000010]; int top = 1; 17 18 int d[N << 1], e[N << 1], E[N << 1], TOP; 19 bool vis[N][N << 1]; 20 std::queue Q; 21 22 inline void add(int x, int y, int z) { 23 top++; 24 edge[top].v = y; 25 edge[top].c = z; 26 edge[top].nex = e[x]; 27 e[x] = top; 28 29 top++; 30 edge[top].v = x; 31 edge[top].c = 0; 32 edge[top].nex = e[y]; 33 e[y] = top; 34 return; 35 } 36 37 inline bool BFS(int s, int t) { 38 memset(d, 0, sizeof(d)); 39 d[s] = 1; 40 Q.push(s); 41 while(!Q.empty()) { 42 int x = Q.front(); 43 Q.pop(); 44 for(int i = e[x]; i; i = edge[i].nex) { 45 int y = edge[i].v; 46 if(!edge[i].c || d[y]) { 47 continue; 48 } 49 d[y] = d[x] + 1; 50 Q.push(y); 51 } 52 } 53 return d[t]; 54 } 55 56 int DFS(int x, int t, int maxF) { 57 if(x == t) { 58 return maxF; 59 } 60 int Ans = 0; 61 for(int i = e[x]; i; i = edge[i].nex) { 62 int y = edge[i].v; 63 if(!edge[i].c || d[x] + 1 != d[y]) { 64 continue; 65 } 66 int temp = DFS(y, t, std::min(edge[i].c, maxF - Ans)); 67 if(!temp) { 68 d[y] = INF; 69 } 70 Ans += temp; 71 edge[i].c -= temp; 72 edge[i ^ 1].c += temp; 73 if(Ans == maxF) { 74 break; 75 } 76 } 77 return Ans; 78 } 79 80 inline int dinic(int s, int t) { 81 int Ans = 0; 82 while(BFS(s, t)) { 83 Ans += DFS(s, t, INF); 84 } 85 return Ans; 86 } 87 88 void DFS(int x, int k) { 89 vis[k][x] = 1; 90 for(int i = e[x]; i; i = edge[i].nex) { 91 int y = edge[i].v; 92 if(!edge[i ^ 1].c || vis[k][y]) { 93 continue; 94 } 95 DFS(y, k); 96 } 97 return; 98 } 99 100 inline bool check(int x, int mid) {101 for(int k = 1; k <= s[x]; k++) {102 for(int jj = topo[x][k].size() - 1; jj >= 0; jj--) {103 int j = topo[x][k][jj];104 if(vis[x - mid - 1][j + n]) {105 return 1;106 }107 }108 }109 return 0;110 }111 112 inline void solve() {113 memset(vis[0], -1, sizeof(vis[0]));114 int S = n + m + 1, T = n + m + 2;115 for(int i = 1; i <= m; i++) {116 add(n + i, T, b[i]);117 }118 for(int i = 1; i <= n; i++) {119 add(S, i, 1);120 mat[i] = 0;121 for(int k = 1; k <= m; k++) {122 TOP = top;123 E[i] = e[i];124 for(int jj = topo[i][k].size() - 1; jj >= 0; jj--) {125 int j = topo[i][k][jj];126 E[n + j] = e[n + j];127 add(i, n + j, 1);128 }129 int temp = dinic(S, T);130 if(temp) {131 mat[i] = k;132 break;133 }134 else {135 e[i] = E[i];136 for(int jj = topo[i][k].size() - 1; jj >= 0; jj--) {137 int j = topo[i][k][jj];138 e[n + j] = E[n + j];139 }140 top = TOP;141 }142 }143 if(!mat[i]) {144 mat[i] = m + 1;145 }146 DFS(T, i);147 }148 for(int i = 1; i <= n; i++) {149 printf("%d ", mat[i]);150 }151 puts("");152 // first OVER153 154 for(int i = 1; i <= n; i++) {155 if(mat[i] <= s[i]) {156 printf("0 ");157 continue;158 }159 int l = 1, r = i;160 while(l < r) {161 int mid = (l + r) >> 1;162 if(check(i, mid)) {163 r = mid;164 }165 else {166 l = mid + 1;167 }168 }169 printf("%d ", r);170 }171 puts("");172 return;173 }174 175 inline void clear() {176 memset(e, 0, sizeof(e));177 top = 1;178 memset(vis, 0, sizeof(vis));179 return;180 }181 }182 183 inline void solve() {184 scanf("%d%d", &n, &m);185 for(int i = 1; i <= m; i++) {186 scanf("%d", &b[i]);187 }188 for(int i = 1; i <= n; i++) {189 for(int j = 1; j <= m; j++) {190 scanf("%d", &a[i][j]);191 if(a[i][j]) {192 topo[i][a[i][j]].push_back(j);193 }194 }195 }196 for(int i = 1; i <= n; i++) {197 scanf("%d", &s[i]);198 }199 // read over200 201 fl::solve();202 return;203 }204 205 inline void clear() {206 for(int i = 1; i <= n; i++) {207 for(int j = 1; j <= m; j++) {208 topo[i][j].clear();209 }210 }211 fl::clear();212 return;213 }214 215 int main() {216 217 int T;218 scanf("%d%d", &T, &C);219 while(T--) {220 solve();221 if(T) {222 clear();223 }224 }225 return 0;226 }
我发现D2T1都好毒瘤...屠龙勇士也是的。