HDU 2485

私はまだ最小割の内包を理解していないようです...この問題は少なくともいくつかの頂点を除いて、図のソース点と集約点が連通しないようにすることを求めている.最小分割の定義を考えてみると、図中の各エッジの流量が1であれば、最小分割は最小のエッジを除去し、図のソース点と集約点が連通しないようにする.この問題の各頂点を2つの頂点に分割し、真ん中を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 __int64

using namespace std;

typedef int typef;
typedef int typec;
#define inff 0x0fffffff
#define infc 0x0fffffff
#define N 100
#define E 10000

struct 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
", D.flow);
    }
    return 0;
}