[XTU][1489][Fat Man][网络流]

题意为给定一个矩形，矩形中有一些点，要使一个半径为 r 的圆穿过这个矩形而不经过这些点，至少得去掉这些点的几个点。 将上边界看成源，下边界看成汇，点到源距离小于直径，则边一条无穷大边，同样，点到下边界距离小于直径，连一条无穷大边，将点拆成两点，权值为 cost, 对任意两点，距离小于直径则连无穷边，问题就转化成求新图的最小割。

具体建图见代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int const N= 250, inf= 0x7fffffff;
#define min(a,b) ( (a)<(b)?(a):(b) )

int w, l, r, n;
int  idx= -1, S, T;
int X[N], Y[N], C[N];

struct Edge{
    int wt, v;
    Edge* next;
}tb[N*N];

Edge* mat[N];
int h[N], que[N];

double distance( double x1, double y1, double x2, double y2 ){
	return sqrt( (x1-x2)* (x1-x2)+ (y1-y2)* (y1-y2) );
}

void inline add( int u, int v, int x ){
    idx++;
    tb[idx].wt= x; tb[idx].v= v; 
    tb[idx].next= mat[u]; mat[u]= tb+ idx;
    
    idx++;
    tb[idx].wt= 0; tb[idx].v= u;
    tb[idx].next= mat[v]; mat[v]= tb+ idx;
}

inline Edge* reserve( Edge* p ){
    return tb+ ((p-tb)^1);
}

int bfs(){
    int head= 0, tail= 0;
    for( int i= 0; i<= T; ++i ) h[i]= -1;
    
    que[0]= S; h[S]= 0;
    while( head<= tail ){
        int u= que[head++];
        
        for( Edge* p= mat[u]; p; p= p->next ){
            int v= p->v, w= p->wt;

            if( h[v]== -1 && w> 0 ){
                h[v]= h[u]+ 1; que[++tail]= v;
            }
        }
    }
    return h[T]!= -1;
}

int dfs( int u, int flow ){
    if( u== T ) return flow;
    int tf= 0, f;
    for( Edge* p= mat[u]; p; p= p->next ){
        int v= p->v, w= p->wt;
        if( h[v]== h[u]+ 1 && w> 0 && tf< flow && ( f= dfs( v, min( w, flow- tf ) ) ) ){
            p->wt-= f;
            reserve(p)->wt+= f;
            tf+= f;
        }
    }
    if( tf== 0 ) h[u]= -1;
    return tf;
}

int main(){
	int test;
	scanf("%d",&test );
	for( int te= 1; te<= test; ++te ){
		scanf("%d%d%d%d", &w, &l, &r, &n );
		
		S= 0; T= 2* n+ 1; idx= -1; r*= 2;
		for( int i= 0; i<= T; ++i ) mat[i]= 0;
		
		if( w< r ) add( S, T, inf );
		int x, y, c;
		for( int i= 1; i<= n; ++i ){
			scanf("%d%d%d", X+ i, Y+ i, C+ i );
			
			if( w- Y[i]< r )add( S, i, inf );
			if( Y[i]< r ) add( i+ n, T, inf );
			
			add( i, i+ n, C[i] );
		}
		
		for( int i= 1; i<= n; ++i )
		for( int j= 1; j<= n; ++j )
		if( i!= j && distance( X[i], Y[i], X[j], Y[j] )< r )
		add( i+ n, j, inf );
		
		int ans= 0;
		while( bfs() ) ans+= dfs( S, inf );
		
		if( ans== inf ) puts("-1");
		else printf("%d\n", ans );
	}
	
	return 0;
}