题目描述：有向图，n个点，好多边。走每条边耗时都是1。

敌人要从1号点走到n号点。

如果你拆除一个点，那么所有和这个点相连接的边都会拆除。

问你最少拆除几个点，可以是敌人在k时间内走不到n。

解题报告：

首先找出所有k时间内能走到n的路径上的点：

Floyd得到任意点对的最小值（两次spfa也可以）

比如点i，如果1到i的最短时间 + i到n的最短时间小于等于k，那么i就是路径上的点。

找到所有这样的点后，每个点拆成两个点i1，和i2，i1和i2之间连接

如果i到j有边，连接i2到j1

如果s到i有边，连接s到i1。

如果i到n有边，连接i2到n

所有边的容量都为1。

最大流（实际意义是最小割）就是答案。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n, m, kk, cap[120][120];
int g2[60][60];
bool g[60][60], vst[60];
int num[60], cnt;
int pre[120], que2[120];
bool find(int n, int s, int t)
{
    int i, tmp;
    memset(pre, -1, sizeof(pre));
    int head = 0, tail = 0;
    que2[tail++] = s; pre[s] = s;
    while(head < tail)
    {
        tmp = que2[head++];
        for(int i = 1; i <= n; i++)
            if (pre[i] == -1 && cap[tmp][i] > 0)
            {
                pre[i] = tmp;
                if (i == t) return true;
                que2[tail++] = i;
            }
    }
    return false;
}
int maxflow(int n, int s, int t)
{
    int flow = 0;
    while(find(n, s, t))
    {
        int min = 0x7fffffff;
        for(int i = t; i != s; i = pre[i])
            if (min > cap[pre[i]][i])
                min = cap[pre[i]][i];
        for(int i = t; i != s; i = pre[i])
        {
            cap[pre[i]][i] -= min;
            cap[i][pre[i]] += min;
        }
        flow += min;
    }
    return flow;
}
int main()
{
    while(scanf("%d%d%d", &n, &m, &kk) && (n ||m || kk))
    {
        memset(g, 0, sizeof(g));
        memset(g2, -1, sizeof(g2));
        for(int i = 0; i < m; i++)
        {
            int a, b;scanf("%d%d", &a, &b);
            g2[a][b] = g[a][b] = 1;
        }
        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    if (g2[i][k] != -1 && g2[k][j] != -1 && (g2[i][j] == -1 || g2[i][k] + g2[k][j] < g2[i][j]))
                        g2[i][j] = g2[i][k] + g2[k][j];
        cnt = 0;
        for(int i = 2; i < n ;i++)
            if (g2[1][i] != -1 && g2[i][n] != -1 && g2[1][i] + g2[i][n] <= kk)
                num[cnt++] = i;
        if (cnt > 0)
        {
            num[cnt++] = 1;
            num[cnt++] = n;
            memset(cap, 0, sizeof(cap));
            int s = 1, t = n; int nn = n;
            for(int i = 0; i < cnt; i++)
            {
                if (num[i] != s && num[i] != t)
                {
                    cap[num[i]][num[i] + n] = 1;
                    if (num[i] + n > nn) nn = num[i] + n;
                }
                else continue;
                if (g[s][num[i]] > 0)
                    cap[s][num[i]] = 1;
                if (g[num[i]][s] > 0)
                    cap[num[i] + n][s] = 1;
            }
            for(int i = 0; i < cnt; i++)
            {
                if (num[i] == s || num[i] == t) continue;
                if (g[num[i]][t] > 0)
                    cap[num[i] + n][t] = 1;
                if (g[t][num[i]] > 0)
                    cap[t][num[i]] = 1;
            }
            for(int i = 0; i < cnt; i++)
                for(int j = 0; j < cnt; j++)
                    if (num[i] != s && num[j] != s && num[i] != t && num[j] != t && g[num[i]][num[j]] > 0)
                        cap[num[i] + n][num[j]] = 1;
            printf("%d\n", maxflow(nn, s, t));
        }
        else printf("0\n");
    }
    return 0;
}