• 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 n,S,T;double d;
    14. int x[105],y[105],ni[105],mi[105];
    15. int H[205],X[85000],P[85000],tot,flow[85000],tott,floww[85000],xx[85000],h[205];
    16. inline void add(int x,int y,int z){
    17. 	P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;
    18. }
    19. int D[205];
    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. 	#ifdef LOCAL
    57. 	freopen("in.txt","r",stdin) ;
    58. 	freopen("out.txt","w",stdout) ;
    59. 	#endif
    60. 	scanf("%d",&tt);
    61. 	S=0,T=204;
    62. 	while(tt--){
    63. 		tot=1;
    64. 		memset(H,0,sizeof H);
    65. 		scanf("%d%lf",&n,&d);
    66. 		for(int i=1;i<=n;i++){
    67. 			scanf("%d%d%d%d",&x[i],&y[i],&ni[i],&mi[i]);
    68. 		}
    69. 		bool ok=1;
    70. 		int sum(0);
    71. 		// x<<1 x<<1|1
    72. 		for(int i=1;i<=n;i++){
    73. 			if(mi[i]) add(S,i<<1,ni[i]),add(i<<1,S,0),sum+=ni[i];
    74. 			add(i<<1,i<<1|1,mi[i]);add(i<<1|1,i<<1,0);
    75. 		}
    76. 		d=d*d;
    77. 		for(int i=1;i<=n;i++){
    78. 			for(int j=i+1;j<=n;j++){
    79. 				if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=d){
    80. 					add(i<<1|1,j<<1,inf);add(j<<1,i<<1|1,0);
    81. 					add(j<<1|1,i<<1,inf);add(i<<1,j<<1|1,0);
    82. 				}
    83. 			}
    84. 		}
    85. 		tott=tot;
    86. 		int maxflow;
    87. 		memcpy(h,H,sizeof H);
    88. 		memcpy(xx,X,sizeof X);
    89. 		memcpy(floww,flow,sizeof flow);
    90. 		for(int i=1;i<=n;i++){
    91. 			tot=tott;
    92.  
    93. 			memcpy(H,h,sizeof H);memcpy(X,xx,sizeof X);memcpy(flow,floww,sizeof flow);
    94. 			add(i<<1,T,inf);add(T,i<<1,0);
    95. 			if((maxflow=Dinic())>=sum){
    96. 				if(ok) ok=0;else putchar(' '); printf("%d",i-1);
    97. 			}
    98. 		}
    99. 		if(ok) puts("-1");else puts("");
    100. 	}
    101. 	return 0 ;
    102. }
    103.