Destroying the bus stations HDU - 2485（最小割点）

题意：

　　就是求最小割点

解析：

　　正向一遍spfa 反向一遍spfa  然后遍历每一条边，对于当前边 如果dis1[u] + dis2[v] + 1 <= k 那么就把这条边加入到网络流图中，

　　每个点拆点 边权为1

　　跑最大流即可

代码还是改的那一题。。。

　　

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

#include <cmath>

#include <vector>

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

const int maxn = 1e3 + , INF = 0xfffffff, maxm = ;

typedef long long LL;

int n,m, cnt, s, t, k;

int head[maxn], d[maxn], vis[maxn], dis1[maxn], dis2[maxn], head1[maxn], cur[maxn];

int from[maxm], to[maxm];

int bz[][], way[][];

struct edge

{

    int u, v, c, next;

}Edge[maxm << ];

void add_(int u, int v, int c)

{

    Edge[cnt].u = u;

    Edge[cnt].v = v;

    Edge[cnt].c = c;

    Edge[cnt].next = head1[u];

    head1[u] = cnt++;

}

void add_edge(int u, int v, int c)

{

    add_(u, v, c);

    add_(v, u, );

}

bool bfs()

{

    mem(d, );

    queue<int> Q;

    Q.push(s);

    d[s] = ;

    while(!Q.empty())

    {

        int u = Q.front(); Q.pop();

        for(int i = head1[u]; i != -; i = Edge[i].next)

        {

            edge e = Edge[i];

            if(!d[e.v] && e.c > )

            {

                d[e.v] = d[u] + ;

                Q.push(e.v);

                if(e.v == t) return ;

            }

        }

    }

    return d[t] != ;

}

int dfs(int u, int cap)

{

    int ret = ;

    if(u == t || cap == )

        return cap;

    for(int &i = cur[u]; i != -; i = Edge[i].next)

    {

        edge e = Edge[i];

        if(d[e.v] == d[u] +  && e.c > )

        {

            int V = dfs(e.v, min(e.c, cap));

            Edge[i].c -= V;

            Edge[i ^ ].c += V;

            ret += V;

            cap -= V;

            if(cap == ) break;

        }

    }

    if(cap > ) d[u] = -;

    return ret;

}

int Dinic()

{

    int ans = ;

    while(bfs())

    {

        memcpy(cur, head1, sizeof(head1));

        ans += dfs(s, INF);

    }

    return ans;

}

struct node

{

    int u, v, w, next;

}Node[maxn * ];

void add(int u,int v,int w,int i)

{

    Node[i].u = u;

    Node[i].v = v;

    Node[i].w = w;

    Node[i].next = head[u];

    head[u] = i;

}

void spfa(int s)

{

    for(int i = ; i < maxn; i++) d[i] = INF;

    queue<int> Q;

    d[s] = ;

    mem(vis,);

    Q.push(s);

    vis[s] = ;

    while(!Q.empty())

    {

        int u = Q.front();Q.pop();

        vis[u] = ;

        for(int i=head[u]; i!=-; i=Node[i].next)

        {

            node e = Node[i];

            if(d[e.v] > d[u] + e.w)

            {

                d[e.v] = d[u] + e.w;

                if(!vis[e.v])

                {

                    Q.push(e.v);

                    vis[e.v] = ;

                }

            }

        }

    }

}

int main()

{

    int T,A,B;

    while(~scanf("%d%d%d", &n, &m, &k))

    {

        if(n==&&m==&&k==)

        break;

        mem(way, );

        mem(bz, );

        mem(Node,);

        mem(head,-);

        mem(head1, -);

        cnt = ;

        for(int i=; i<m; i++)

        {

            scanf("%d%d",&from[i],&to[i]);

            if(!bz[from[i]][to[i]])

            {

                add(from[i],to[i],,i), bz[from[i]][to[i]] = ;

                way[from[i]][to[i]] = ;

            }

        }

        s = , t = n;

        spfa(s);

        mem(Node,);

        for(int i=; i<=n; i++)

            dis1[i] = d[i];

        mem(head,-);

        for(int i=; i<m; i++)

            add(to[i],from[i],,i);

        spfa(t);

        for(int i=; i<=n; i++)

            dis2[i] = d[i];

        mem(bz, );

        s =  + n, t = n;

        for(int i = ; i <= n; i++)

        {

            for(int j = ; j <= n; j++)

            {

                if(way[i][j] && dis1[i] + dis2[j] +  <= k)

                    add_edge(i, j, INF);

            }

            add_edge(i, i + n, );

        }

        printf("%d\n",Dinic());

    }

    return ;

}