Dinic 算法求最大流（最小割） POJ 2536

题意：给定n, m, s, v, 意思是有n只兔子，m个洞，兔子的跑步速度是v，兔子有s的时间跑进洞里，给定兔子和洞的坐标，问最少有多少只兔子在s时间内无法跑进洞里。

这道题是在Openjudge上看到的。。。。网络流。。。说好的NOIP有两道题从里面抽，然而加了这道网络流。要跪、♥碎。

于是去复习了一下以前看过的Dinic，有一段时间没写了，都快忘记了。数组范围都给忘了，RE了好多次。

这道题要求的就是哪只兔子进哪个洞，这样的一个最优方案，我们已知时间，速度，距离，就能知道每只兔子可以跑进哪些洞，然后我们把这样的组合连边，就是赤裸裸的二分图匹配了。纵然匈牙利算法很简单，我也不会。还是决定用Dinic来解决二分图匹配问题。复杂度O(sqrt(n)*E)，比匈牙利算法要优。

于是增加一个0号源点和一个n+e+1号汇点、所有边的容量设为1，用Dinic跑一次最大流就解决了问题。稍微复习一下Dinic：用BFS构造层次图，构造成功说明还有增广路，之后仅仅在层次图上DFS寻找增广路，如此循环。下面算是贴了个模板。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#define X first
#define Y second
using namespace std;

struct Edge {int u, v, flow, cap;};

struct Dinic
{
#define M 105

vector <int> G[M*2];
int e, d[M*2], cur[M*2];
    Edge E[M*M*2];
bool vis[M*2];

void Initialize()
    {
for(int i = 0; i <= 205; i++) G[i].clear();
memset(E, 0, sizeof E);
        e = 0;
    }

void Addedge(int u, int v, int cap)
    {
        G[u].push_back(e); G[v].push_back(e+1);
        E[e].u = u, E[e].v = v, E[e++].cap = cap; 
        E[e].u = v, E[e].v = u, E[e++].cap = 0;
    }

bool BFS(int s, int t)
    {
memset(vis, 0, sizeof vis);
queue <int> q;
while(!q.empty()) q.pop();
        q.push(s); d[s] = 0; vis[s] = 1;
while(!q.empty())
        {
int u = q.front(); q.pop(); 
for(int i = 0; i < G[u].size(); i++)
            {
                Edge k = E[G[u][i]];
if(!vis[k.v] && k.cap > k.flow)
                    { vis[k.v] = 1, d[k.v] = d[u] + 1; q.push(k.v); }
            }   
        } 
return vis[t];
    }

int DFS(int u, int flow, int t)
    {
if(u == t || !flow) return flow;

int f1 = 0, f2;
for(int &i = cur[u]; i < G[u].size(); i++)
        {
            Edge &k = E[G[u][i]];
            Edge &_k = E[G[u][i]^1];
if(d[u]+1 == d[k.v] && (f2 = DFS(k.v, min(flow, k.cap-k.flow), t)) > 0)
            {
                k.flow += f2, f1 += f2;
                _k.flow -= f2, flow -= f2;
if(!flow) break;
            }
        }
return f1;
    }

int Maxflow(int s, int t)
    {
int res = 0;
while(BFS(s, t))
        {
memset(cur, 0, sizeof cur);
            res += DFS(s, (1<<30), t);
        }
return res;
    }
};

int n, m, time, sped, Maxd;
pair <double,double> rab[105], hol[105];
Dinic Solver;

double dis(int a, int b)
{
    pair <double,double> t1 = rab[a], t2 = hol[b];
double dx = t1.X-t2.X, dy = t1.Y-t2.Y;
return sqrt(dx*dx+dy*dy);
}

int main()
{
while(~scanf("%d %d %d %d", &n, &m, &time, &sped))
    {
        Maxd = time*sped;
for(int i = 1; i <= n; i++) scanf("%lf %lf", &rab[i].X, &rab[i].Y);
for(int i = 1; i <= m; i++) scanf("%lf %lf", &hol[i].X, &hol[i].Y);

        Solver.Initialize();

for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) 
if(Maxd*1.0 >= dis(i, j)) Solver.Addedge(i, n+j, 1);

for(int i = 1; i <= n; i++) Solver.Addedge(0, i, 1);
for(int i = 1; i <= m; i++) Solver.Addedge(n+i, n+m+1, 1);

printf("%d\n", n-Solver.Maxflow(0, n+m+1));
    }
return 0;
}