POJ 2536 二分匹配匈牙利算法 || 网络流 - c++编程基础

ed[num].next = head[e] ;
head[e] = num ++ ;
}

void init()
{
mem(head,-1) ;
num = 0 ;
}
struct pp
{
double x, y;
}a[200],b[200] ;
bool Can(pp x ,pp y)
{
double dis = sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y)) ;
double t = dis / v ;
if(t <= s)
return 1 ;
return 0;
}
int S , T ;
void build()
{
REP(i,1,n)
{
REP(j,1,m)
{
if(Can(a[i],b[j]))
{
add(i,j + n ,1) ;
}
}
}
REP(i,1,n)add(S,i,1) ;
REP(i,1,m)add(i + n ,T,1) ;
}
int deep[200] ;
int qe[2000000] ;
int dinic_bfs()
{
mem(deep,-1) ;
deep[S] = 0 ;
int h = 0 , t = 0 ;
qe[ h ++ ] = S ;
while( h > t )
{
int tt = qe[ t ++ ] ;
for (int i = head[tt] ; ~i ; i = ed[i].next )
{
int e = ed[i].e ;
int l = ed[i].l ;
if(deep[e] == -1 && l > 0 )
{
deep[e] = deep[tt] + 1 ;
qe[ h ++ ] = e ;
}
}
}
return deep[T] != -1 ;
}

int dinic_dfs(int now ,int f)
{
if(now == T)return f ;
int flow = 0 ;
for (int i = head[now] ; ~i ;i = ed[i].next )
{
int e = ed[i].e ;
int l = ed[i].l ;
if(deep[e] == deep[now] + 1 && l > 0 && (f - flow))
{
int mm = min(l,f - flow ) ;
int nn = dinic_dfs(e,mm) ;
flow += nn ;
ed[i].l -= nn ;
ed[i ^ 1].l += nn ;
}
}
if(!flow)deep[now] = -2 ;
return flow ;
}

int dinic()
{
int flow = 0 ;
while(dinic_bfs())
{
flow += dinic_dfs(S,inf) ;
}
return flow ;
}
int main()
{
while(cin >> n >> m >> s >> v )
{
S = 0 ,T = n + m + 1 ;
init() ;
REP(i,1,n)cin >> a[i].x >> a[i].y ;
REP(i,1,m)cin >> b[i].x >> b[i].y ;
build() ;
cout << n - dinic() < }
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PI acos(-1.0)
#define Max 2005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;

int n , m ,s, v;
struct kdq
{
int s , e, l ,next ;
}ed[200000] ;
int head[200], num ;
void add(int s ,int e ,int l)
{
ed[num].s = s ;
ed[num].e = e ;
ed[num].l = l ;
ed[num].next = head[s] ;
head[s] = num ++ ;

ed[num].s = e ;
ed[num].e = s ;
ed[num].l = 0 ;
ed[num].next = head[e] ;
head[e] = num ++ ;
}

void init()
{
mem(head,-1) ;
num = 0 ;
}
struct pp
{
double x, y;
}a[200],b[200] ;
bool Can(pp x ,pp y)
{
double dis = sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y)) ;
double t = dis / v ;
if(t <= s)
return 1 ;
return 0;
}
int S , T ;
void build()
{
REP(i,1,n)
{
REP(j,1,m)
{
if(Can(a[i],b[j]))
{
add(i,j + n ,1) ;
}
}
}
REP(i,1,n)add(S,i,1) ;
REP(i,1,m)add(i + n ,T,1) ;
}
int deep[200] ;
int qe[2000000] ;
int dinic_bfs()
{
mem(deep,-1) ;
deep[S] = 0 ;
int h = 0 , t = 0 ;
qe[ h ++ ] = S ;
while( h > t )
{
int tt = qe[ t ++ ] ;
for (int i = head[tt] ; ~i ; i = ed[i].next )
{
int e = ed[i].e ;
int l = ed[i].l ;
if(deep[e] == -1 && l > 0 )
{
deep[e] = deep[tt] + 1 ;
qe[ h ++ ] = e ;
}
}
}
return deep[T] != -1 ;
}

int dinic_dfs(int now ,int f)
{
if(now == T)return f ;
int flow

POJ 2536 二分匹配 匈牙利算法 || 网络流 (二)

POJ 2536 二分匹配匈牙利算法 || 网络流 (二)