HDU4862 最小费用流 多校联赛1

  这道题的意思是给你一个不超过10*10的矩阵, 一个人可以选择一个点开始走动, 每次可以从一个点跳到他右边或者下边的点, 跳过的点就不能在跳了, 定义跳跃一次的花费为abs(x2-x1) + abs(y2-y1) - 1,如果跳跃前后格子的数字相等那么这个人就可以得到格子数的能量, 这个人最多跳跃K次, 问你他能不能跳完所有的格子, 假设能跳完那么他能得到的最大的能量是多少? 对于这个题我们考虑将每个格子看成一个点, 并且将每个点拆成两个点,建立二分图, x部包含N*M个点, y部也包含N*M个点, 如果能从u点跳到v点, 那么从x部的x连到y部的v点一条边, 容量inf, 价值为行走话费-获得的能量, 建立一个源点s连到x部, 容量为1,花费为0, 再建立一个汇点t,从y部连接到t容量为1,花费为0, 由于有最多选K个起点的限制, 我们再增加一个点ex , 源点s 连接 ex, 容量为K,花费为0, ex连接每一个y部容量为1, 花费为0, 这个求出最小费用流, 判断流量是不是等于N*M即可, 等于的话-cost就是所能获得的最大能量。代码如下:

#include <bits/stdc++.h>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 350;

struct Edge { int from, to, cap, flow, cost; };
vector<Edge> edges;
vector<int> G[maxn];
int inque[maxn];   //spfa
int d[maxn];    //源点到当前点的最短路
int p[maxn];    //入弧编号
int a[maxn];    //可改进量

void init(int n)
{
    for(int i=0; i<=n; i++) G[i].clear();
    edges.clear();
}

void add_edge(int from, int to, int cap, int cost)
{
    edges.push_back((Edge){from, to, cap, 0, cost});
    edges.push_back((Edge){to, from, 0, 0, -cost});
    int m = edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
}

bool spfa(int s, int t, int &flow, long long &cost)
{
    memset(d, 0x3f, sizeof(d));
    memset(inque, 0, sizeof(inque));
    d[s] = 0; inque[s] = 1;
    a[s] = inf; p[s] = 0;
    queue<int> que;
    que.push(s);
    while(!que.empty()){
        int u = que.front(); que.pop();
        inque[u] = 0;
        for(int i=0; i<G[u].size(); i++){
            Edge e = edges[G[u][i]];
            if(e.cap>e.flow && d[e.to]>d[u]+e.cost){
                d[e.to] = d[u] + e.cost;
                if(!inque[e.to]) que.push(e.to), inque[e.to]=1;
                p[e.to] = G[u][i];   //e.to的入弧编号
                a[e.to] = min(a[u], e.cap-e.flow);   //更新可改进量
            }
        }
    }
    if(d[t] == inf) return false;
    flow += a[t];
    cost += (long long)a[t]*(long long)d[t];
    for(int u=t; u!=s; u=edges[p[u]].from){
        edges[p[u]].flow += a[t];
        edges[p[u]^1].flow -= a[t];
    }
    return true;
}

int MCMF(int s, int t, long long &cost)
{
    int flow = 0; cost = 0;
    while(spfa(s, t, flow, cost));
    return flow;
}

int N, M, K;  //N个顶点
char mat[20][20];

int main()
{
    int T;
    scanf("%d", &T);
    int kase = 0;
    while(T--){
        scanf("%d%d%d", &N, &M, &K);
        for(int i=0; i<N; i++) scanf("%s", mat[i]);
//        init(2*N*M+5);
//        // 0 - N*M - 1   u
//        // N*M - 2*N*M-1 v
//        // s:2*N*M t 2*N*M+1 ex 2*N*M+2
//        int s = 2*N*M, t = 2*N*M+1, ex = 2*N*M+2;
//        add_edge(s, ex, K, 0);
//        for(int i=0; i<N; i++) for(int j=0; j<M; j++) {
//            //向右
//            int u = i*M + j;
//            for(int k=j+1; k<M; k++){   //i, j -> i, k
//                int v = i*M + k;
//                int cost = k-j-1-(mat[i][k]==mat[i][j]?mat[i][j]-'0':0);
//                add_edge(u, v+N*M, 1, cost);
//            }
//            //向下
//            for(int k=i+1; k<N; k++){   //i, j -> k, j
//                int v = k*M+j;
//                int cost = k-i+1-(mat[k][j]==mat[i][j]?mat[i][j]-'0':0);
//                add_edge(u, v+N*M, 1, cost);
//            }
//        }
//        for(int i=0; i<N*M; i++) add_edge(s, i, 1, 0);
//        for(int i=N*M; i<2*N*M; i++) add_edge(i, t, 1, 0), add_edge(ex, i, 1, 0);
        init(2*N*M+3);
        int s = 2*N*M, t=2*N*M+2;
        int ex = 2*N*M+1;
        add_edge(s, ex, K, 0);
        for(int i=0; i<N; i++) for(int j=0; j<M; j++)
        {
            add_edge(s, 2*(i*M+j), 1, 0);
            add_edge(2*(i*M+j)+1, t, 1, 0);
            add_edge(ex, 2*(i*M+j)+1, 1, 0);
            for(int y=j+1; y<M; y++)
            {
                int cost = y-j-1-(mat[i][j]==mat[i][y]?mat[i][j]-'0':0);
                add_edge(2*(i*M+j), 2*(i*M+y)+1, inf, cost);
            }
            for(int x=i+1; x<N; x++)
            {
                int cost = x-i-1-(mat[i][j]==mat[x][j]?mat[i][j]-'0':0);
                add_edge(2*(i*M+j), 2*(x*M+j)+1, inf, cost);
            }
        }
        long long cost;
        int flow = MCMF(s, t, cost);
        if(N*M != flow)
            printf("Case %d : -1
", ++kase);
        else
            printf("Case %d : %lld
", ++kase, -cost);

    }
    return 0;
}
原文地址:https://www.cnblogs.com/xingxing1024/p/5279862.html