112. 作业之地理篇 最小费用最大流模板题

发布时间:2017-7-1 11:14:53编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"112. 作业之地理篇 最小费用最大流模板题 ",主要涉及到112. 作业之地理篇 最小费用最大流模板题 方面的内容,对于112. 作业之地理篇 最小费用最大流模板题 感兴趣的同学可以参考一下。

https://scut.online/p/112

题面好像看不了吧,

思路是把相邻的点都建立一条边,然后跑最小费用最大流。把点hash成两部分,然后需要建立双向边,这样以后匹配数 / 2就是原图的最大匹配。

最小费用最大流感觉就是,用spfa代替了原来的bfs增广路,spfa的同时保证了cost最小,然后路径本来就是随意的,因为有了残余网络。可以让水流流回去。

#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;const int maxn = 30 * 30 * 4;struct Edge {    int u, v, w, cost, tonext;}e[maxn * 2];int first[maxn], num;int n, m;void addEdge(int u, int v, int w, int cost) {    e[num].u = u, e[num].v = v, e[num].w = w, e[num].cost = cost, e[num].tonext = first[u];    first[u] = num++;}int x[maxn], y[maxn], DFN;int getID(int x, int y) {    return (x - 1) * m + y;}int flow[maxn], pre[maxn];int dis[maxn], tim[maxn];bool in[maxn];bool spfa(int bx, int n) {    for (int i = 0; i <= n; ++i) {        dis[i] = inf;        tim[i] = 0;        in[i] = false;        flow[i] = 0;    }    queue<int> que;    while (!que.empty()) que.pop();    que.push(bx), in[bx] = true, dis[bx] = 0, tim[bx]++, flow[bx] = inf;    pre[bx] = -inf;    while (!que.empty()) {        int u = que.front();        que.pop();        for (int i = first[u]; ~i; i = e[i].tonext) {            if (e[i].w > 0 && dis[e[i].v] > dis[e[i].u] + e[i].cost) { //²»Óñê¼Çflow                dis[e[i].v] = dis[e[i].u] + e[i].cost;                pre[e[i].v] = i;                flow[e[i].v] = min(e[i].w, flow[u]);                if (!in[e[i].v]) {                    que.push(e[i].v);                    in[e[i].v] = true;                    tim[e[i].v]++;                }            }        }        in[u] = false;    }    if (flow[n] == 0) return false;    else return true;}LL ans;int maxFlow(int be, int en) {    int sumFlow = 0;    while (spfa(0, en)) {//        cout << dis[en] << endl;        ans += 1LL * dis[en] * flow[en];        int res = flow[en];        int edgeID = pre[en];        while (edgeID != -inf) {            e[edgeID].w -= res;            e[edgeID ^ 1].w += res;            edgeID = pre[e[edgeID].u];        }        sumFlow += res;    }    return sumFlow;}set< pair<int, int> > ss;void work() {    memset(first, -1, sizeof first);    num = 0, ++DFN;    ss.clear();    int q;    scanf("%d", &q);    for (int i = 1; i <= q; ++i) {        int xi, yi;        scanf("%d%d", &xi, &yi);        ss.insert(make_pair(xi, yi));    }    for (int i = 1; i <= n; ++i) {        for (int j = 1; j <= m - 1; ++j) {            int val;            scanf("%d", &val);            if (ss.count(make_pair(i, j)) || ss.count(make_pair(i, j + 1))) continue;            addEdge(getID(i, j), getID(i, j + 1) + n * m, 1, val);            addEdge(getID(i, j + 1) + n * m, getID(i, j), 0, -val);            addEdge(getID(i, j + 1), getID(i, j) + n * m, 1, val);            addEdge(getID(i, j) + n * m, getID(i, j + 1), 0, -val);        }    }    for (int i = 1; i <= n - 1; ++i) {        for (int j = 1; j <= m; ++j) {            int val;            scanf("%d", &val);            if (ss.count(make_pair(i, j)) || ss.count(make_pair(i + 1, j))) continue;            addEdge(getID(i, j), getID(i + 1, j) + n * m, 1, val);            addEdge(getID(i + 1, j) + n * m, getID(i, j), 0, -val);            addEdge(getID(i + 1, j), getID(i, j) + n * m, 1, val);            addEdge(getID(i, j) + n * m, getID(i + 1, j), 0, -val);        }    }    if ((n * m - q) & 1) {        printf("-1\n");        return;    }    for (int i = 1; i <= n * m; ++i) {        addEdge(0, i, 1, 0);        addEdge(i, 0, 0, 0);        addEdge(n * m + i, 2 * n * m + 1, 1, 0);        addEdge(2 * n * m + 1, n * m + i, 0, 0);    }//    for (int i = first[5]; ~i; i = e[i].tonext) {//        printf("%d %d %d %d\n", e[i].u, e[i].v, e[i].w, e[i].cost);//    }    ans = 0;    int res = maxFlow(0, 2 * n * m + 1);//    cout << res << endl;    if (res != (n * m - q)) {        printf("-1\n");    } else printf("%lld\n", ans / 2);}int main() {#ifdef local    freopen("data.txt", "r", stdin);//    freopen("data.txt", "w", stdout);#endif    while (scanf("%d%d", &n, &m) > 0) work();    return 0;}
View Code


上一篇:Esxi 6.0虚拟机迁移Linux遇到网络配置错误
下一篇:02.SQLServer性能优化之---水平分库扩展

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款