思路：这题我在下午重现的时候就用的费用流做，可是各种悲催的超时，只是我一开始的那种建图方式多了一个二分查找。
戏剧性的是，求距离的返回值写成int型了，CodeBlock编译器又没有警告，然后就WA啊WA，AC率一下就被拉低了。
当然，对每种工人分别建图是不变的，因为每种工人互不影响。
后来想到了一个较好的建图方式，将每个点拆成3个点，i,i+n,i+2*n。
1号点就是仓库，也就是超级源点，3*n+1号点为超级汇点。
由1号点想每个i建一条流量为ty[i][j]，费用为1的边。表示每次增加流量，人数就增加。
由i向i+2*n建一条流量为ty[i][j]，费用为0的边。
由i+2*n向汇点建一条流量为ty[i][j]，费用为0的边。
由1向每个i+n建一条流量为ty[i][j]，费用为0的边。
对i号点，寻找开始时间sta[k]满足b[i]+p[i]+d[i][j]的点k，然后由i+n向k+2*n建一条流量为ty[i][j]，费用为0的边。
这样，如果i号点的工人能到k号点工作，那么k号点的k+2*n到3*n+1的流量就会减少ty[i][j]。
#include<iostream>
#include<cstring>
#include<cstring>
#include<cmath>
#include<cstdio>
#define inf 100000000
using namespace std;
const int Maxn = ;
struct Edge{
int v;
int val;
int cost;
int next;
}edge[Maxn*];
struct Point{
double x,y;
}p[Maxn];
int head[Maxn],n,m,k;
int e;
int dis[Maxn],pre[Maxn], pos[Maxn],sta[Maxn],en[Maxn],ty[Maxn][],flow;
int que[Maxn*];
double d[Maxn][Maxn];
bool vis[Maxn];
void add(int u, int v, int val, int cost)
{
edge[e].v = v;
edge[e].val = val;
edge[e].cost = cost;
edge[e].next = head[u];
head[u] = e++;
edge[e].v = u;
edge[e].val = ;
edge[e].cost = -cost;
edge[e].next = head[v];
head[v] = e++;
}
double DIS(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void init()
{
memset(head,-,sizeof(head));
e=;
}
bool spfa(int s, int t)
{
int i;
memset(pre, -, sizeof(pre));
memset(vis, , sizeof(vis));
int Head, tail;
Head = tail = ;
for(i = ; i < Maxn; i++)
dis[i] = inf;
que[tail++] = s;
pre[s] = s;
dis[s] = ;
vis[s] = ;
while(Head != tail)
{
int now = que[Head++];
vis[now] = ;
for(i=head[now]; i != -; i = edge[i].next)
{
int adj = edge[i].v;
if(edge[i].val > && dis[now] + edge[i].cost < dis[adj])
{
dis[adj] = dis[now] + edge[i].cost;
pre[adj] = now;
pos[adj] = i;
if(!vis[adj])
{
vis[adj] = ;
que[tail++] = adj;
}
}
}
}
return pre[t] != -;
}
int MinCostFlow(int s, int t)
{
int i;
int cost = ;
flow = ;
while(spfa(s, t))
{
int f = ;
for(i = t; i != s; i = pre[i])
if (edge[pos[i]].val < f)
f = edge[pos[i]].val;
flow += f;
cost += dis[t] * f;
for(i = t; i != s; i = pre[i])
{
edge[pos[i]].val -= f;
edge[pos[i] ^ ].val += f;
}
}
return cost;
}
void build(int type)
{
int i,j;
init();
for(i=;i<=n;i++){
add(,i,ty[i][type],);
add(i,i+*n,ty[i][type],);
add(,i+n,ty[i][type],);
add(i+*n,*n+,ty[i][type],);
for(j=;j<=n;j++){
if(sta[i]+en[i]+d[i][j]<=sta[j]){
add(i+n,j+*n,ty[i][type],);
}
}
}
}
int solve()
{
int i,j,u,v;
int ans=;
for(i=;i<=m;i++){
build(i);
ans+=MinCostFlow(,*n+);
}
return ans;
}
int main()
{
int i,j,u,v,c,t;
scanf("%d",&t);
while(t--)
{
init();
scanf("%d%d",&n,&m);
scanf("%lf%lf",&p[].x,&p[].y);
for(i=;i<=n;i++){
scanf("%lf%lf%d%d",&p[i].x,&p[i].y,&sta[i],&en[i]);
for(j=;j<=m;j++){
scanf("%d",&ty[i][j]);
}
}
for(i=;i<=n;i++){
for(j=i+;j<=n;j++){
d[i][j]=d[j][i]=DIS(p[i],p[j]);
}
}
printf("%d\n",solve());
}
return ;
}