• 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;
    13. int w[26];
    14. int a[26][26];
    15. int H[800],X[15000],P[15000],tot,flow[15000],S,T;
    16. int d[800];
    17. inline void add(int x,int y,int z){
    18. 	P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;
    19. }
    20. queue<int> q;
    21. bool bfs(){
    22. 	memset(d,0,sizeof d);
    23. 	d[S]=1;int x;q.push(S);
    24. 	while(!q.empty()){
    25. 		x=q.front();q.pop();
    26. 		for(int i=H[x];i;i=X[i]){
    27. 			if(flow[i]>0&&!d[P[i]]){
    28. 				d[P[i]]=d[x]+1;
    29. 				q.push(P[i]);
    30. 			}
    31. 		}
    32. 	}
    33. 	return d[T];
    34. }
    35. int dfs(int x,int a){
    36. 	if(x==T||a==0) return a;
    37. 	int f=a,tmp;
    38. 	for(int i=H[x];i;i=X[i]){
    39. 		if(flow[i]>0&&d[P[i]]==d[x]+1){
    40. 			tmp=dfs(P[i],min(flow[i],a));
    41. 			a-=tmp;
    42. 			flow[i]-=tmp;
    43. 			flow[i^1]+=tmp;
    44. 			if(!a) break;
    45. 		}
    46. 	}
    47. 	if(f==a) d[x]=-1;
    48. 	return f-a;
    49. }
    50. int Dinic(){
    51. 	int f(0);
    52. 	while(bfs()) f+=dfs(S,inf);
    53. 	return f;
    54. }
    55. int main(){
    56.  
    57. 	#ifdef LOCAL
    58. 	freopen("in.txt","r",stdin) ;
    59. 	freopen("out.txt","w",stdout) ;
    60. 	#endif
    61. 	scanf("%d",&tt);
    62. 	S=0,T=799;
    63. 	while(tt--){
    64. 		bool f=1;
    65. 		int n;
    66. 		scanf("%d",&n);
    67. 		int maxx=-inf;
    68. 		for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&d[i]),maxx=max(maxx,w[i]);
    69. 		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
    70. 		for(int aim=1;aim<=n;aim++){
    71. 			tot=1;memset(H,0,sizeof H);
    72. 			int total=w[aim];
    73. 			for(int j=1;j<=n;j++){
    74. 				total+=a[aim][j];
    75. 			}
    76. 			if(total<maxx) continue;
    77. 			int sum(0);
    78. 			int bz=26;
    79. 			for(int i=1;i<=n;i++){
    80. 				if(i==aim) continue;
    81. 				add(i,T,total-w[i]);
    82. 				add(T,i,0);
    83. 				for(int j=i+1;j<=n;j++){
    84. 					if(j==aim) continue;
    85. 					if(a[i][j]){
    86. 						sum+=a[i][j];
    87. 						add(S,bz,a[i][j]);
    88. 						add(bz,S,0);
    89. 						add(bz,i,inf);
    90. 						add(i,bz,0);
    91. 						add(bz,j,inf);
    92. 						add(j,bz,0);
    93. 						bz++;
    94. 					}
    95. 				}
    96. 			}
    97. 			if(Dinic()==sum){
    98. 				if(f) f=0;else putchar(' ');
    99. 				printf("%d",aim);
    100. 			}
    101.  
    102. 		}puts("");
    103. 	}
    104. 	return 0 ;
    105. }
    106.