POJ 2536 二分匹配 匈牙利算法 || 網絡流

題意很簡單，不敘述了，我分別用二分匹配和最大流實現了一下這道題，算是對前面所學知識的一次綜合運用吧。

這是二分匹配：

[cpp] 
#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <string>  
#include <cmath>  
#include <cstring>  
#include <queue>  
#include <set>  
#include <vector>  
#include <stack>  
#include <map>  
#include <iomanip>  
#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 Map[200][200] ; 
int link[200] ; 
bool vis[200] ; 
int n , m ,s, v; 
int dfs(int now) 
{ 
    for (int i = 1 ;i <= m ;i ++) 
    { 
        if(Map[now][i]) 
        if(!vis[i]) 
        { 
            vis[i] = 1 ; 
            if(link[i] == -1 || dfs(link[i])) 
            { 
                link[i] = now ; 
                return 1 ; 
            } 
        } 
    } 
    return 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; 
} 
void build() 
{ 
    REP(i,1,n) 
    { 
        REP(j,1,m) 
        { 
            Map[i][j] = Can(a[i],b[j]) ; 
        } 
    } 
} 
int main() 
{ 
    while(cin >> n >> m >> s >> v ) 
    { 
        REP(i,1,n)cin >> a[i].x >> a[i].y ; 
        REP(i,1,m)cin >> b[i].x >> b[i].y ; 
        build() ; 
        mem(link ,-1) ; 
        int ans = 0 ; 
        REP(i,1,n) 
        { 
            mem(vis,0) ; 
            ans += dfs(i) ; 
        } 
        cout << n - ans <<endl; 
    } 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#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 Map[200][200] ;
int link[200] ;
bool vis[200] ;
int n , m ,s, v;
int dfs(int now)
{
    for (int i = 1 ;i <= m ;i ++)
    {
        if(Map[now][i])
        if(!vis[i])
        {
            vis[i] = 1 ;
            if(link[i] == -1 || dfs(link[i]))
            {
                link[i] = now ;
                return 1 ;
            }
        }
    }
    return 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;
}
void build()
{
    REP(i,1,n)
    {
        REP(j,1,m)
        {
            Map[i][j] = Can(a[i],b[j]) ;
        }
    }
}
int main()
{
    while(cin >> n >> m >> s >> v )
    {
        REP(i,1,n)cin >> a[i].x >> a[i].y ;
        REP(i,1,m)cin >> b[i].x >> b[i].y ;
        build() ;
        mem(link ,-1) ;
        int ans = 0 ;
        REP(i,1,n)
        {
            mem(vis,0) ;
            ans += dfs(i) ;
        }
        cout << n - ans <<endl;
    }
    return 0;
}

這是網絡流：

[cpp] 
#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <string>  
#include <cmath>  
#include <cstring>  
#include <queue>  
#include <set>  
#include <vector>  
#include <stack>  
#include <map>  
#include <iomanip>  
#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 = 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() <<endl; 
    } 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#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 = 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() <<endl;
    }
    return 0;
}