看来我还是不理解最小割的内涵...这题求的是最少去掉几个顶点，使得图的源点和汇点不连通。想想最小割的定义，如果图中每条边的流量都是1，那么最小割就变成了去掉最少的边，使得图的源点和汇点不连通。把这题中每个顶点拆分成两个顶点，中间用一条流量为1的边连接...这样，模型就满足最小割模型了。还有一个限制是路径长度大于k的路径可以不用考虑。这里只需按最小费用流建图，每条边的费用是1，当路径费用大于k的时候终止最大流过程即可。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <memory.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>
#include <sstream>#define ll __int64using namespace std;typedef int typef;
typedef int typec;
#define inff 0x0fffffff
#define infc 0x0fffffff
#define N 100
#define E 10000struct network
{int nv, ne, pnt[E], nxt[E];int vis[N], que[N], head[N], pv[N], pe[N];typef flow, cap[E]; typec cost, dis[E], d[N];void addedge(int u, int v, typef c, typec w) {pnt[ne] = v; cap[ne] = c;dis[ne] = w; nxt[ne] = head[u]; head[u] = ne++;pnt[ne] = u; cap[ne] = 0;dis[ne] = -w; nxt[ne] = head[v]; head[v] = ne++;}int mincost(int src, int sink, int limit) {int i, k, f, r; typef mxf;for(flow = 0, cost = 0; ; ) {memset(pv, -1, sizeof(pv));memset(vis, 0, sizeof(vis));for(i = 0; i < nv; ++i) d[i] = infc;d[src] = 0; pv[src] = src; vis[src] = 1;for(f = 0, r = 1, que[0] = src; r != f; ) {i = que[f++]; vis[i] = 0;if(N == f) f = 0;for(k = head[i]; k != -1; k = nxt[k])if(cap[k] && dis[k]+d[i] < d[pnt[k]]) {d[pnt[k]] = dis[k] + d[i];if(0 == vis[pnt[k]]) {vis[pnt[k]] = 1;que[r++] = pnt[k];if(N == r) r = 0;}pv[pnt[k]] = i; pe[pnt[k]] = k;}}if(-1 == pv[sink]) break;if (d[sink] > limit) break;for(k = sink, mxf = inff; k != src; k = pv[k])if(cap[pe[k]] < mxf) mxf = cap[pe[k]];flow += mxf; cost += d[sink] * mxf;for(k = sink; k != src; k = pv[k]) {cap[pe[k]] -= mxf; cap[pe[k]^1] += mxf;}}return cost;}void init(int v) {nv = v; ne = 0;memset(head, -1, 4 * v);}
} D;int main() {int n, m, k, x, y;while (scanf("%d %d %d", &n, &m, &k), n || m || k) {D.init(n * 2);for (int i = 0; i < n; i++)D.addedge(i * 2, i * 2 + 1, 1, 0);for (int i = 0; i < m; i++) {scanf("%d %d", &x, &y);x--, y--;D.addedge(x * 2 + 1, y * 2, 1, 1);}D.mincost(1, (n - 1) * 2, k);printf("%d\n", D.flow);}return 0;
}