题意:给出一个有源网络流图,每个点射出的流量有上界限制(除源点外),问是否可以在图中找到汇点使得该网络流图满流。
做法:感觉这题唯一的收获就是学会了控制结点射出流量的方法,拆点,i->i`点连一条容量为限制数的边,这样就可以控制这个点流出的流量了。

struct node2


{
double x,y;
int a,b;
}p[maxn];
int n;
double D;


double dist(node2 a,node2 b)


{
return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}

void input()


{
scanf("%d %lf",&n,&D);
for(int i=0;i<n;i++)
scanf("%lf%lf%d%d",&p[i].x,&p[i].y,&p[i].a,&p[i].b);
}
int s;
int tol;

//入结点为2*i
//出结点为2*i+1 ^_^
void get()


{
for(int i=0;i<2*n+1;i++)
adj[i]=NULL;
len=0;
tol=0;

for(int i=0;i<n;i++)
insert(i*2,i*2+1,p[i].b);
for(int i=0;i<n;i++)

{
insert(s,i*2,p[i].a);
tol+=p[i].a;
}
for(int i=0;i<n;i++)

{
for(int j=0;j<n;j++)

{
if(i==j)continue;
if(dist(p[i],p[j])<=D)
insert(i*2+1,j*2,INF);
}
}
}

int ans[1000];
int pans;

int main()


{
int ca;
scanf("%d",&ca);
while(ca--)

{
input();
pans=0;
s=n*2;
for(int i=0;i<n;i++)

{
get();
if(sap(s+1,s,i*2)==tol)
ans[pans++]=i;
}
if(pans==0)
printf("-1\n");
else

{

for(int i=0;i<pans-1;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[pans-1]);
}
}
return 0;


}