代码求调,60pts
查看原帖
代码求调,60pts
109114
_l_l_¯l¯l¯楼主2022/1/24 14:35

rt

#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <string>
#include <iostream>
#include <cstring>
//#pragma GCC optimize("Ofast")
#include <algorithm>
#define inf 0x3fffffff
//#define int long long
using namespace std;
#define min(a, b) (a < b ? a : b)
template<int nod, int edg> class EKMCMF {
    int n;
    struct edge {
        int next, to, fl, v;
    } e[edg << 2];
    int head[nod], cnt = 1;
    int dist[nod], pre[nod], vis[nod], minn[nod];
    queue<int>Q;
    int s, t, val, flag[nod], check;
    string ss[nod];
    inline void add_edge(int from, int to, int fl, int v) {
        e[++cnt].to = to;
        e[cnt].next = head[from];
        e[cnt].fl = fl;
        e[cnt].v = v;
        head[from] = cnt;
    }
    void update(int x, int flow) {
        e[pre[x]].fl -= flow;
        e[pre[x] ^ 1].fl += flow;

        if (e[pre[x] ^ 1].to)
            update(e[pre[x] ^ 1].to, flow);
    }
    inline int spfa() {
        memset(vis, 0, sizeof(vis));

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

        for (register int i = 1; i <= t; i++)
            dist[i] = -inf;

        minn[s] = inf;
        dist[s] = 0;
        Q.push(s);
        vis[s] = 1;

        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            vis[x] = 0;

            for (register int i = head[x]; i; i = e[i].next) {
                if (dist[e[i].to] < dist[x] + e[i].v && e[i].fl) {
                    dist[e[i].to] = dist[x] + e[i].v;
                    pre[e[i].to] = i;
                    minn[e[i].to] = min(minn[x], e[i].fl);

                    if (!vis[e[i].to]) {
                        vis[e[i].to] = 1;
                        Q.push(e[i].to);
                    }
                }
            }
        }

        if (dist[t] == -inf)
            return -inf;

        update(t, minn[t]);
        val += minn[t];
        return minn[t] * dist[t];
    }
public:
    inline void add(int from, int to, int fl, int v) {
//        printf("%d %d\n", from, to);
        add_edge(from, to, fl, v);
        add_edge(to, from, 0, -v);
    }
    inline pair<int, int> EK(int n_, int s_, int t_) {
        n = n_;
        s = s_;
        t = t_;
        int sum = 0;

        while (1) {
            int x = spfa();

            if (x == -inf)
                return make_pair(val, sum);

            sum += x;
        }
    }
    inline void find_reverse_path(int x, int tims) {
        if (x == 1)
            return;

        for (int i = head[x]; i; i = e[i].next) {
            if ((i & 1) && e[i].fl) {
                find_reverse_path(e[i].to, tims);

                // check the way(south or east)
                if (x == e[i].to + 1 && (x & 1)) {
                    printf("%d 1\n", tims);
                } else if (x & 1) {
                    printf("%d 0\n", tims);
                }

                e[i].fl--;
                e[i ^ 1].fl++;
                break;
            }
        }
    }
};
EKMCMF<100000, 100000> mcmf1;
int arrid[400][400][7];
signed main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int tmptot = 0;
    int sum1 = 0, sum2 = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%1d", &arrid[i][j][0]);
            sum1 += arrid[i][j][0];
            arrid[i][j][3] = ++tmptot;
            arrid[i][j][4] = ++tmptot;
            arrid[i][j][5] = ++tmptot;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%1d", &arrid[i][j][1]);
            sum2 += arrid[i][j][1];

            if (arrid[i][j][0]) {
                mcmf1.add(tmptot + 1, arrid[i][j][4], 1, 0);
            }

            if (arrid[i][j][1]) {
                mcmf1.add(arrid[i][j][4], tmptot + 2, 1, 0);
            }
        }
    }

    if (sum1 != sum2)
        return puts("-1"), 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%1d", &arrid[i][j][2]);

            if (arrid[i][j][0] && arrid[i][j][1] == 0) {
                mcmf1.add(arrid[i][j][3], arrid[i][j][4], arrid[i][j][2] << 1, 0);
                mcmf1.add(arrid[i][j][4], arrid[i][j][5], arrid[i][j][2] + 1 << 1, 0);
            } else if (arrid[i][j][0]) {
                mcmf1.add(arrid[i][j][3], arrid[i][j][4], arrid[i][j][2] << 1, 0);
                mcmf1.add(arrid[i][j][4], arrid[i][j][5], arrid[i][j][2] << 1, 0);
            } else if (arrid[i][j][1]) {
                mcmf1.add(arrid[i][j][3], arrid[i][j][4], arrid[i][j][2] + 1 << 1, 0);
                mcmf1.add(arrid[i][j][4], arrid[i][j][5], arrid[i][j][2] << 1, 0);
            } else {
                mcmf1.add(arrid[i][j][3], arrid[i][j][4], arrid[i][j][2] << 1, 0);
                mcmf1.add(arrid[i][j][4], arrid[i][j][5], arrid[i][j][2] << 1, 0);
            }
        }
    }

    // -
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++) {
            mcmf1.add(arrid[i][j][5], arrid[i][j + 1][3], 114514, -1);
            mcmf1.add(arrid[i][j + 1][5], arrid[i][j][3], 114514, -1);
        }
    }

    // |
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= m; j++) {
            mcmf1.add(arrid[i][j][5], arrid[i + 1][j][3], 114514, -1);
            mcmf1.add(arrid[i + 1][j][5], arrid[i][j][3], 114514, -1);
        }
    }

    // /
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < m; j++) {
            mcmf1.add(arrid[i][j][5], arrid[i - 1][j + 1][3], 114514, -1);
            mcmf1.add(arrid[i - 1][j + 1][5], arrid[i][j][3], 114514, -1);
        }
    }

    /* \ */
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            mcmf1.add(arrid[i][j][5], arrid[i + 1][j + 1][3], 114514, -1);
            mcmf1.add(arrid[i + 1][j + 1][5], arrid[i][j][3], 114514, -1);
        }
    }
	pair<int, int> p = mcmf1.EK(tmptot + 2, tmptot + 1, tmptot + 2);
	if (p.first != sum2) return puts("-1"), 0;
    printf("%d\n", -p.second);
    return 0;
}
2022/1/24 14:35
加载中...