HDU 4862 Jump（更多的联合培训学校1）（最小费用最大流）

职务地址：HDU4862

最小费用流做的还是太少。

建图想不出来。

。

直接引用官方题解的话吧。。。

最小K路径覆盖的模型。用费用流或者KM算法解决，构造二部图，X部有N*M个节点。源点向X部每一个节点连一条边，流量1，费用0，Y部有N*M个节点，每一个节点向汇点连一条边。流量1，费用0。假设X部的节点x能够在一步之内到达Y部的节点y，那么就连边x->y，费用为从x格子到y格子的花费能量减去得到的能量。流量1，再在X部添加一个新的节点，表示能够从随意节点出发K次，源点向其连边，费用0。流量K。这个点向Y部每一个点连边，费用0，流量1，最这个图跑最小费用最大流，假设满流就是存在解。反之不存在，最小费用的相反数就是能够获得的最大能量

代码例如以下：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int head[500], source, sink, cnt, flow, cost;
int cur[500], d[500], vis[500], mp[20][20];
struct node
{
    int u, v, cap, cost, next;
} edge[1000000];
void add(int u, int v, int cap, int cost)
{
    edge[cnt].v=v;
    edge[cnt].cap=cap;
    edge[cnt].cost=cost;
    edge[cnt].next=head[u];
    head[u]=cnt++;

    edge[cnt].v=u;
    edge[cnt].cap=0;
    edge[cnt].cost=-cost;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
int spfa()
{
    memset(d,INF,sizeof(d));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(source);
    d[source]=0;
    cur[source]=-1;
    int minflow=INF, i;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(i=head[u]; i!=-1; i=edge[i].next)
        {
            int v=edge[i].v;
            if(d[v]>d[u]+edge[i].cost&&edge[i].cap)
            {
                d[v]=d[u]+edge[i].cost;
                minflow=min(minflow,edge[i].cap);
                cur[v]=i;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(d[sink]==INF) return 0;
    flow+=minflow;
    cost-=minflow*d[sink];
    for(i=cur[sink]; i!=-1; i=cur[edge[i^1].v])
    {
        edge[i].cap-=minflow;
        edge[i^1].cap+=minflow;
    }
    return 1;
}
void mcmf(int sum)
{
    while(spfa());
    if(flow==sum)
        printf("%d
",cost);
    else
        printf("-1
");
}
int main()
{
    int t, n, m, i, j, k, h, num=0;
    char s[30];
    scanf("%d",&t);
    while(t--)
    {
        num++;
        scanf("%d%d%d",&n,&m,&k);
        for(i=0; i<n; i++)
        {
            scanf("%s",s);
            for(j=0; j<m; j++)
            {
                mp[i][j]=s[j]-'0';
            }
        }
        source=0;
        sink=2*n*m+2;
        cnt=0;
        memset(head,-1,sizeof(head));
        flow=0;
        cost=0;
        for(i=1; i<=n*m; i++)
        {
            add(source,i,1,0);
            add(i+n*m+1,sink,1,0);
            add(n*m+1,i+n*m+1,1,0);
        }
        add(source,n*m+1,k,0);
        int z;
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                for(h=j+1; h<m; h++)
                {
                    z=0;
                    if(mp[i][j]==mp[i][h])
                        z=mp[i][j];
                    add(i*m+j+1,n*m+1+i*m+h+1,1,h-j-1-z);
                }
                for(h=i+1; h<n; h++)
                {
                    int z=0;
                    if(mp[i][j]==mp[h][j])
                        z=mp[i][j];
                    add(i*m+j+1,n*m+1+h*m+j+1,1,h-i-1-z);
                }
            }
        }
        printf("Case %d : ",num);
        mcmf(n*m);
    }
    return 0;
}