【题解】CQOI2012交换棋子

感受到网络流的强大了……这道题目的关键在于：

　　前后颜色不变的，流入流出的次数相等；原本是黑色的最后变成了白色，流出比流入次数多1；原本是白色最后变成黑色，流入比流出次数多一。所以我们将每一点拆成3个点，分别代表流入点，原点与流出点。最开始为黑色的点与源点连流量为1，费用为0的边，最后为黑色的点与汇点连流量为1，费用为0的边。

#include<bits/stdc++.h>

using namespace std;

#define maxn 300

#define maxm 8000

#define INF 99999

int n, m, size, tem, a[maxn][maxn], b[maxn][maxn], c[maxn][maxn], head[maxm];

int cnp, fans, ans, cost, dis[maxm], pre[maxm], flow[maxm];

int dx[] = {, , , , , , -, -, -};

int dy[] = {, , -, , , -, , , -};

int s = , t;

bool vis[maxm];

deque <int> q;

struct edge

{

    int to, last, f, c;

}E[maxn * ];

void add(int u, int v, int f, int c)

{

    E[cnp].to = v, E[cnp].last = head[u], E[cnp].f = f, E[cnp].c = c; head[u] = cnp ++;

    E[cnp].to = u, E[cnp].last = head[v], E[cnp].f = , E[cnp].c = -c; head[v] = cnp ++;

}

int Get_id(int x, int y)

{

    return (x - ) * m + y;

}

void init()

{

    memset(head, -, sizeof(head));

}

int SPFA()

{

    q.push_back(s);

    flow[s] = INF;

    for(int i = ; i <= n * m *  + ; i ++) dis[i] = INF;

    while(!q.empty())

    {

        int u = q.front();

        q.pop_front();

        vis[u] = false;

        for(int i = head[u]; i != -; i = E[i].last)

        {

            int v = E[i].to;

            if(E[i].f && dis[v] > dis[u] + E[i].c)

            {

                dis[v] = dis[u] + E[i].c, pre[v] = i;

                flow[v] = min(flow[u], E[i].f);

                if(!vis[v])

                {

                    vis[v] = true;

                    if(!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);

                    else q.push_front(v);

                }

            }

        }

    }

    if(dis[t] >= INF) return false;

    else return true;

}

void Max_flow()

{

    while(SPFA())

    {

        int v = pre[t];

        while()

        {

            E[v].f -= flow[t];

            E[v ^ ].f += flow[t];

            if(E[v ^ ].to == s) break;

            v = pre[E[v ^ ].to];

        }

        ans += flow[t];

        cost += flow[t] * dis[t];

    }

}

void Get_input()

{

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

    {

        string s; cin >> s;

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

            a[i][j + ] = s[j] - '';

    }

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

    {

        string s; cin >> s;

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

            b[i][j + ] = s[j] - '';

    }

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

    {

        string s; cin >> s;

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

            c[i][j + ] = s[j] - '';

    }

}

void Connect()

{

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

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

        {

            int u = Get_id(i, j);

            if(a[i][j]) tem ++, add(s, u, , );

            if(b[i][j]) fans ++, add(u, t, , );

            if(a[i][j] == b[i][j])

            {

                add(u + size, u, c[i][j] / , );

                add(u, u +  * size, c[i][j] / , );

            }

            else if(b[i][j])

            {

                add(u + size, u, (c[i][j] + ) / , );

                add(u, u +  * size, c[i][j] / , );

            }

            else if(a[i][j])

            {

                add(u + size, u, c[i][j] / , );

                add(u, u +  * size, (c[i][j] + ) / , );

            }

            for(int k = ; k <= ; k ++)

            {

                int x = i + dx[k], y = j + dy[k];

                if(x <  || x > n || y <  || y > m) continue;

                add(u +  * size, Get_id(x, y) + size, INF, );

            }

        }

}

int main()

{

    scanf("%d%d", &n, &m);

    init();

    t = n * m *  + , size = n * m;

    Get_input();

    Connect();

    if(tem != fans)

    {

        printf("-1\n");

        return ;

    }

    Max_flow();

    if(ans == fans) printf("%d", cost >> );

    else printf("-1\n");

    return ;

}

巴特西

【题解】CQOI2012交换棋子

最新文章

热门文章