不知道这个Zayid是谁...
题意：
有n个人，m个导师。每个导师能接纳bi个人，每个人对于这m个导师都有一个志愿档次。
优先满足靠前的人，问到最后每个人匹配的导师是他的第几志愿。
每个人又有一个限制si，问至少前进多少名才能被志愿档次不大于si的导师录取。
解：
首先发现，每个志愿档次只能填一个人的时候，可以直接贪心。否则在同一志愿档次内选择不同的导师会对后面有影响。
这时我们就可以利用网络流。
一个流量代表一个的归属，动态加边。
对于每个人枚举志愿档次，添加流向导师的边。然后看是否有流量。
如果有流量那么他就归于该志愿档次。
第二问，答案可以二分。
很简朴的想法是对于每个二分出来的值，重新建图来一遍。这样复杂度就是Tnlogn * nm，显然不行。
发现每次重新建图的时候我们进行了很多一模一样的操作。于是考虑把前k个人的网络流状态保存下来，之后直接调用。
但是太麻烦了...我们又发现一种很巧妙的方法：判断在前k个人加完之后是否可行，其实是看哪些导师还可以接纳人。于是我们从汇点出发，反向DFS，能够得到每次从哪些导师出发有增广路，就是哪些导师还能接纳。
然后二分的时候直接O(m)判定。
这样我们发现有90分，超时一个点。
回想第一问网络流的时候，如果一个志愿档次没有流量，那么这些加的边就没有用，不妨删了。
然后就A了...
1 #include <queue> 2 #include <cstdio> 3 #include <vector> 4 #include <cstring> 5 #include <algorithm> 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<int> 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<int> 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 OVER 153 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 over 200 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都好毒瘤...屠龙勇士也是的。