[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;intidx= -1, S, T;int X, Y, C;struct Edge{ int wt, v; Edge* next;}tb;Edge* mat;int h, que;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.wt= x; tb.v= v; tb.next= mat; mat= tb+ idx; idx++; tb.wt= 0; tb.v= u; tb.next= mat; mat= 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= -1; que= S; h= 0; while( head<= tail ){ int u= que; for( Edge* p= mat; p; p= p->next ){ int v= p->v, w= p->wt; if( h== -1 && w> 0 ){ h= h+ 1; que[++tail]= v; } } } return h!= -1;}int dfs( int u, int flow ){ if( u== T ) return flow; int tf= 0, f; for( Edge* p= mat; p; p= p->next ){ int v= p->v, w= p->wt; if( h== h+ 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= -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= 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< r )add( S, i, inf );if( Y< r ) add( i+ n, T, inf );add( i, i+ n, C );}for( int i= 1; i<= n; ++i )for( int j= 1; j<= n; ++j )if( i!= j && distance( X, Y, X, Y )< 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;}
页:
[1]