方法②代码:
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int get(){
int n;char c;while((c=getchar())||1)if(c>='0'&&c<='9')break;
n=c-'0';while((c=getchar())||1){
if(c>='0'&&c<='9')n=n*10+c-'0';
else return(n);
}
}int pipei1[201][201],pipei2[201][201];
int back1[201][201],back2[201][201];
unsigned char biao[201][201][201];
int ans[201];int n,m;int as[201];
unsigned char bv[201][201];
int dfs(int ren,int zhiyuan){
if(ren+zhiyuan==0)return(1);
for(register int i=1;i<=biao[ren][zhiyuan][0];i++){
int me=biao[ren][zhiyuan][i];
for(register int j=1;j<=as[me];j++){
if(!bv[me][j]){
bv[me][j]=1;if(dfs(pipei1[me][j],pipei2[me][j])){
pipei1[me][j]=ren;pipei2[me][j]=zhiyuan;return(1);
}
}
}
}return(0);
}int main(){
int ltt=get();get();while(ltt){
ltt--;n=get(),m=get();for(register int i=1;i<=m;i++)as[i]=get();
memset(pipei1,0,sizeof(pipei1));memset(pipei2,0,sizeof(pipei2));
for(register int i=1;i<=n;i++){
for(register int j=1;j<=m;j++){
biao[i][j][0]=0;
}
for(register int j=1;j<=m;j++){
int a=get();if(a){
biao[i][a][0]++;
biao[i][a][biao[i][a][0]]=j;
}
}
}for(register int i=1;i<=n;i++){
for(register int j=1;j<=m;j++){
if(biao[i][j][0]==0)continue;
memset(bv,0,sizeof(bv));
if(dfs(i,j)){
printf("%d ",j);ans[i]=j;goto cjr;
}
}
printf("%d ",m+1);ans[i]=m+1;
cjr:;
}cout<<endl;
for(register int i=1;i<=n;i++){
int qiwang=get();if(ans[i]<=qiwang){
printf("0 ");continue;
}int anss=i,l=1,r=i-1;
while(l<=r){
int mid=(l+r)>>1;
//printf("mid=%d\n",mid);
for(register int j=1;j<=m;j++){
for(register int k=1;k<=as[j];k++){
back1[j][k]=pipei1[j][k];
back2[j][k]=pipei2[j][k];
if(pipei1[j][k]<i-mid)continue;
//printf("clear %d,%d\n",j,k);
pipei1[j][k]=0;pipei2[j][k]=0;
}
}
for(register int j=1;j<=qiwang;j++){
memset(bv,0,sizeof(bv));
if(dfs(i,j)){
anss=mid;r=mid-1;goto ywy;
}
}l=mid+1;
ywy:
for(register int j=1;j<=m;j++){
for(register int k=1;k<=as[j];k++){
pipei1[j][k]=back1[j][k];
pipei2[j][k]=back2[j][k];
}
}
}printf("%d ",anss);
}
cout<<endl;
}
return(0);
}
```
by 颜伟业_C_Asm @ 2018-04-09 16:08:26
好吧大概是边太多了……
by 颜伟业_C_Asm @ 2018-04-09 23:35:55