题目链接
题解
在上一个人匹配完图的基础上，我们可以对每个人的志愿分别匈牙利算法二分图匹配
匹配时,从小到大枚举该人的志愿匹配，复杂度是(O(nC+m))，然后第一问做完了
第二问(~~我们可以二分答案，匈牙利算法~~)我们暴力枚举在i位置之后的每个位置k,做一次假的二分图匹配只寻找，不修改...判断能否匹配成功
然后我们需要匈牙利(n^2)次
所以总复杂度(O(n^3C+n^2m))
ε=(´ο｀*)))唉，考场上还是太Naive了QAQQQQQQ
代码
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using std::vector;
inline int read() {
int x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c <= '9' && c >= '0') x=x * 10 +c - '0' ,c = getchar();
return x *f ;
}/*
inline void add_edge(int u ,int v,int flow ,int cost) {
edge[++num].v = v;edge[num].flow = flow;edge[num].next =head[x];haed[x] = num;
}*/
const int maxn = 207;
int T,C,n,m;
int a[maxn][maxn],b[maxn];
vector<int>vec[maxn][maxn],que[maxn];
int s[maxn],ans[maxn],match[maxn],Wmatch[maxn];
bool vis[maxn];
void init() {
for(int i = 1;i <= n;++ i) que[i].clear();
for(int i = 1;i <= n;++ i) for(int j = 1;j <= m;++ j) vec[i][j].clear(),
s[i] = b[i] = match[i] = Wmatch[i] = ans[i] = 0 ;
n = read(), m = read();
for(int i = 1;i <= m;++ i) b[i] = read(),que[i].clear();
for(int i = 1;i <= n;++ i)
for(int a,j = 1;j <= m;++ j) a = read(),vec[i][a].push_back(j) ;
for(int i = 1;i <= n;++ i) s[i] = read();
}
bool dfs(int x,bool flag) {
int l,r; if(!flag)l = Wmatch[x] == 0 ? 1 : Wmatch[x],r = Wmatch[x] == 0 ? s[x] : Wmatch[x];
else l = Wmatch[x] == 0 ? 1 : Wmatch[x],r = Wmatch[x] == 0 ? m : Wmatch[x];
for(int i = l;i <= r;++ i) {
for(int j = 0;j < vec[x][i].size(); ++ j) {
int v = vec[x][i][j];
if(vis[v]) continue;
vis[v] = 1;
//printf("%d
",que[v].size());
if(que[v].size() < b[v]) {
if(flag) {
que[v].push_back(x);
match[x] = v;
Wmatch[x] = i;
}
return true;
}
for(int k = 0;k < que[v].size();k ++ ) {
int tv = que[v][k];
if(dfs(tv,flag)) {
if(flag) {
que[v].erase(que[v].begin() + k);
match[x] = v;
Wmatch[x] = i;
que[v].push_back(x);
}
return true;
}
}
//if(que[2].size() == 1) puts("!!!!!!!!!!!!");
}
}
return false;
}
int main() {
T = read();C = read();
while(T --) {
init();
for(int i = 1;i <= n;++ i) {
for(int j = i;j <= n;++ j) {
memset(vis,0,sizeof vis);
if(dfs(j,false)) ans[j] = i;
}
memset(vis,false,sizeof vis);
dfs(i,true);
printf("%d ",Wmatch[i] ? Wmatch[i] : m + 1);
}
puts("");
for(int i = 1;i <= n; ++ i) {
printf("%d ",i - ans[i]);
}
puts("");
}
return 0;
}