HDU 3488--Tour（KM or 费用流）

2023-08-09 16:43:58

因为每个点只能经过一次所以考虑拆点

这题有坑，有重边。。

KM算法

把一个点拆成入点和出点入点在X部，出点在Y步。

如果u，v之间有路径，就在X部的u点连接Y部的v点

求完美匹配。

当完美匹配的时候，每个点都有一个入度和一个出度，可知成环。

因为完美匹配求得是最大匹配

记得把每条边权值取相反数

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int MAXN = ;

const int INF = 0x3f3f3f3f;

int G[MAXN][MAXN];

int vx[MAXN], vy[MAXN];

bool visx[MAXN], visy[MAXN];

int match[MAXN];

int slack[MAXN];

int N, M;

bool dfs(int x)

{

    visx[x] = true;

    for (int y = ; y < N; ++y) {

        if (visy[y]) continue;

        int gap = vx[x] + vy[y] - G[x][y];

        if (gap == ) {

            visy[y] = true;

            if (match[y] == - || dfs( match[y] )) {

                match[y] = x;

                return true;

            }

        } else {

            slack[y] = min(slack[y], gap);

        }

    }

    return false;

}

int KM()

{

    memset(match, -, sizeof match);

    memset(vy, , sizeof vy);

    for (int i = ; i < N; ++i) {

        vx[i] = G[i][];

        for (int j = ; j < N; ++j) {

            vx[i] = max(vx[i], G[i][j]);

        }

    }

    for (int i = ; i < N; ++i) {

        fill(slack, slack + N, INF);

        while () {

            memset(visx, false, sizeof visx);

            memset(visy, false, sizeof visy);

            if (dfs(i)) break;

            int d = INF;

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

                if (!visy[j]) d = min(d, slack[j]);

            for (int j = ; j < N; ++j) {

                if (visx[j]) vx[j] -= d;

                if (visy[j]) vy[j] += d;

                else slack[j] -= d;

            }

        }

    }

    int res = ;

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

        res += G[ match[i] ][i];

    return res;

}

int Scan() {

    int res = , flag = ;

    char ch;

    if((ch = getchar()) == '-') flag = ;

    else if(ch >= '' && ch <= '') res = ch - '';

    while((ch = getchar()) >= '' && ch <= '')

        res = res *  + (ch - '');

    return flag ? -res : res;

}

int main()

{

    int T = Scan();

    while (T--) {

        N = Scan(), M = Scan();

        for (int i = ; i <= N; ++i) {

            for (int j = ; j <= N; ++j) {

                G[i][j] = -INF;

            }

        }

        int u, v, w;

        while (M--) {

            u = Scan()-, v = Scan()-, w = Scan();

            G[u][v] = max(G[u][v], -w);

        }

        printf("%d\n", -KM());

    }

    return ;

}

费用流

就是把上面的完美匹配用网络流来求。。

和完美匹配一样

如果u，v之间有路径，就u的入点连v的出点，然后所有入点连起点，所有出点连汇点，求最大流最小花费即可。

费用流比起KM慢了几倍。。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <string>

#include <vector>

#include <bitset>

#include <cstdio>

#include <queue>

#include <stack>

#include <cmath>

#include <list>

#include <map>

#include <set>

#define pk(x) printf("%d\n", x)

using namespace std;

#define PI acos(-1.0)

#define EPS 1E-6

#define clr(x,c) memset(x,c,sizeof(x))

//#pragma comment(linker, "/STACK:102400000,102400000")

typedef long long ll;

#define CLR(x, v, n) memset(x, v, sizeof(x[0])*n)

const int N = ;

const int M = ;

const int INF = 0x3f3f3f3f;

struct Edge {

    int to, next, cap, flow, cost;

    void init(int _to, int _cap, int _cost, int _next) {

        to = _to; cap = _cap; cost = _cost; next = _next; flow = ;

    }

} edge[M];

int head[N], cntE;

int pre[N], dis[N];

bool vis[N];

int src, sink, tot;

void dn(int &x, int y) { if(x>y) x=y; }

void init() {

    cntE = ;

    memset(head, -, sizeof head);

}

void addedge(int u, int v, int cap, int cost) {

    edge[cntE].init(v, cap, cost, head[u]); head[u] = cntE++;

    edge[cntE].init(u, , -cost, head[v]); head[v] = cntE++;

}

bool spfa() {

    queue<int> q;

    fill(dis, dis+tot, INF); CLR(vis, false, tot); CLR(pre, -, tot);

    dis[src] = ; vis[src] = true;

    q.push(src);

    while (q.size()) {

        int u = q.front(); q.pop(); vis[u] = false;

        for (int i = head[u]; ~i; i = edge[i].next) {

            int v = edge[i].to;

            if (edge[i].cap > edge[i].flow && dis[u]+edge[i].cost < dis[v]) {

                dis[v] = dis[u]+edge[i].cost;

                pre[v] = i;

                if (!vis[v]) {

                    vis[v] = true;

                    q.push(v);

                }

            }

        }

    }

    if (pre[sink] == -) return false;

    return true;

}

int MCMF() {

    int flow = ;

    int cost = ;

    while (spfa()) {

        int f = INF;

        for (int i = pre[sink]; ~i; i = pre[edge[i^].to]) {

            dn(f, edge[i].cap - edge[i].flow);

        }

        for (int i = pre[sink]; ~i; i = pre[edge[i^].to]) {

            edge[i].flow += f;

            edge[i^].flow -= f;

            cost += edge[i].cost * f;

        }

        flow += f;

    }

    //return flow;

    return cost;

}

int Scan() {

    int res = , flag = ;

    char ch;

    if((ch = getchar()) == '-') flag = ;

    else if(ch >= '' && ch <= '') res = ch - '';

    while((ch = getchar()) >= '' && ch <= '')

        res = res *  + (ch - '');

    return flag ? -res : res;

}

int n, m;

int G[][];

int main()

{

    int T = Scan();

    while (T--) {

        clr(head, -);

        cntE = ;

        n = Scan(), m = Scan();

        int u, v, w;

        src = , sink = n*+, tot = n*+;;

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

            addedge(src, i, , );

            addedge(i+n, sink, , );

        }

        for (int i = ; i <= n; ++i) for (int j = ; j <= n; ++j) G[i][j] = INF;

        while (m--) {

            u = Scan(), v = Scan(), w = Scan();

            G[u][v] = min(G[u][v], w);

        }

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

            if (G[i][j] != INF) {

                addedge(i, j+n, , G[i][j]);

            }

        }

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

    }

    return ;

}

上面的费用流太慢辣，又找了个快点的。嘿嘿XD

#include <algorithm>

#include <iostream>

#include <cstring>

#include <string>

#include <vector>

#include <bitset>

#include <cstdio>

#include <queue>

#include <stack>

#include <cmath>

#include <list>

#include <map>

#include <set>

#define pk(x) printf("%d\n", x)

using namespace std;

#define PI acos(-1.0)

#define EPS 1E-6

#define clr(x,c) memset(x,c,sizeof(x))

//#pragma comment(linker, "/STACK:102400000,102400000")

typedef long long ll;

const int MAXV = ;

const int INF = <<;

struct Edge { int to, cap, cost, rev; };

vector<Edge> G[MAXV];

int dist[MAXV], prv[MAXV], pre[MAXV], in[MAXV];

queue<int> que;

void addedge(int from, int to, int cap, int cost) {

    G[from].push_back((Edge){to, cap, cost, G[to].size()});

    G[to].push_back((Edge){from, , -cost, G[from].size()-});

}

int min_cost_max_flow(int s, int t) { //, int f) {

    int res = ;

    int f = ;

    while () { //f > 0) {

        for (int i = ; i <= t; ++i) dist[i] = INF, in[i] = ;

        dist[s] = ;

        while (!que.empty()) que.pop();

        in[s] = ;

        que.push(s);

        while (!que.empty()) {

            int u = que.front(); que.pop(); in[u] = ;

            for (int i = ; i < G[u].size(); ++i) {

                Edge &e = G[u][i];

                if (e.cap >  && dist[e.to] > dist[u] + e.cost) {

                    dist[e.to] = dist[u] + e.cost;

                    prv[e.to] = u;

                    pre[e.to] = i;

                    if (in[e.to] == ) {

                        in[e.to] = ;

                        que.push(e.to);

                    }

                }

            }

        }

        if (dist[t] == INF) break; //return -1;

        int d = INF; // d = f;

        for (int v = t; v != s; v = prv[v]) {

            d = min(d, G[prv[v]][pre[v]].cap);

        }

        f += d;

        res += d * dist[t];

        for (int v = t; v != s; v = prv[v]) {

            Edge &e = G[prv[v]][pre[v]];

            e.cap -= d;

            G[v][e.rev].cap += d;

        }

    }

    return res;

}

int Scan() {

    int res = , flag = ;

    char ch;

    if((ch = getchar()) == '-') flag = ;

    else if(ch >= '' && ch <= '') res = ch - '';

    while((ch = getchar()) >= '' && ch <= '')

        res = res *  + (ch - '');

    return flag ? -res : res;

}

int n, m;

int mp[][];

int main()

{

    int T = Scan();

    while (T--) {

        n = Scan(), m = Scan();

        int u, v, w;

        int src = , sink = n*+;

        for (int i = ; i <= sink; ++i) G[i].clear();

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

            addedge(src, i, , );

            addedge(i+n, sink, , );

        }

        for (int i = ; i <= n; ++i) for (int j = ; j <= n; ++j) mp[i][j] = INF;

        while (m--) {

            u = Scan(), v = Scan(), w = Scan();

            mp[u][v] = min(mp[u][v], w);

        }

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

            if (mp[i][j] != INF) {

                addedge(i, j+n, , mp[i][j]);

            }

        }

        printf("%d\n", min_cost_max_flow(src, sink));

    }

    return ;

}

码农公寓

相关文章