• Source 
    1. #include <cstdio>
    2. #include <cstring>
    3. #include <algorithm>
    4. #include <queue>
    5. //  by zrt
    6. //  problem:
    7. //  无论你在什么时候开始，重要的是开始以后就不要停止。
    8. using namespace std ;
    9. typedef long long LL ;
    10. const double eps(1e-10) ;
    11. const int inf(0x3f3f3f3f) ;
    12. int tt,kase;
    13. int n,m;
    14. int a[25],b[25];
    15. int H[45],X[1004],P[1004],flow[1004],tot,cap[1005];
    16. int d[45];
    17. int S,T;
    18. inline void add(int x,int y,int z){
    19. 	P[++tot]=y;X[tot]=H[x];H[x]=tot;cap[tot]=flow[tot]=z;
    20. }
    21. queue<int> q;
    22. bool bfs(){
    23. 	memset(d,0,sizeof d);
    24. 	d[S]=1;int x;q.push(S);
    25. 	while(!q.empty()){
    26. 		x=q.front();q.pop();
    27. 		for(int i=H[x];i;i=X[i]){
    28. 			if(flow[i]>0&&!d[P[i]]){
    29. 				d[P[i]]=d[x]+1;
    30. 				q.push(P[i]);
    31. 			}
    32. 		}
    33. 	}
    34. 	return d[T];
    35. }
    36. int dfs(int x,int a){
    37. 	if(x==T||a==0) return a;
    38. 	int f=a,tmp;
    39. 	for(int i=H[x];i;i=X[i]){
    40. 		if(flow[i]>0&&d[P[i]]==d[x]+1){
    41. 			tmp=dfs(P[i],min(flow[i],a));
    42. 			flow[i]-=tmp;
    43. 			a-=tmp;
    44. 			flow[i^1]+=tmp;
    45. 			if(!a) break;
    46. 		}
    47. 	}
    48. 	if(f==a) d[x]=-1;
    49. 	return f-a;
    50. }
    51. int Dinic(){
    52. 	int f(0);
    53. 	while(bfs()) f+=dfs(S,inf);
    54. 	return f;
    55. }
    56. int M[21][21];
    57. int main(){
    58. 	#ifdef LOCAL
    59. 	freopen("in.txt","r",stdin) ;
    60. 	freopen("out.txt","w",stdout) ;
    61. 	#endif
    62. 	scanf("%d",&tt);
    63. 	while(tt--){
    64. 		kase++;
    65. 		S=0,T=44;
    66. 		tot=1;
    67. 		memset(H,0,sizeof H);
    68. 		scanf("%d%d",&n,&m);
    69. 		for(int i=1;i<=n;i++){
    70. 			scanf("%d",&a[i]);
    71. 		}
    72. 		for(int i=1;i<=m;i++){
    73. 			scanf("%d",&b[i]);
    74. 		}
    75. 		for(int i=n;i>1;i--){
    76. 			a[i]-=a[i-1];
    77. 		}
    78. 		for(int i=m;i>1;i--){
    79. 			b[i]-=b[i-1];
    80. 		}
    81. 		for(int i=1;i<=n;i++){
    82. 			add(S,i,a[i]-m);
    83. 			add(i,S,0);
    84. 		}
    85. 		for(int i=1;i<=m;i++){
    86. 			add(i+20,T,b[i]-n);
    87. 			add(T,i+20,0);
    88. 		}
    89. 		for(int i=1;i<=n;i++){
    90. 			for(int j=1;j<=m;j++){
    91. 				add(i,j+20,19);
    92. 				add(j+20,i,0);
    93. 			}
    94. 		}
    95. 		Dinic();
    96. 		for(int i=1;i<=n;i++){
    97. 			for(int j=H[i];j;j=X[j]){
    98. 				if(cap[j])M[i][P[j]-20]=1+cap[j]-flow[j];
    99. 			}
    100. 		}
    101. 		printf("Matrix %d\n",kase);
    102. 		for(int i=1;i<=n;i++){
    103. 			printf("%d",M[i][1]);
    104. 			for(int j=2;j<=m;j++){
    105. 				printf(" %d",M[i][j]);
    106. 			}
    107. 			puts("");
    108. 		}
    109. 		puts("");
    110. 	}
    111. 	return 0 ;
    112. }
    113.