Problem Jump （HDU4862）
题目大意
给定一个n*m的矩形(n,m≤10),每个矩形中有一个0~9的数字。
一共可以进行k次游戏，每次游戏可以任意选取一个没有经过的格子为起点，并且跳任意多步，每步可以向右方和下方跳。每次跳需要消耗两点间的曼哈顿距离减一的能量，若每次跳的起点和终点的数字相同，可以获得该数字的能量。（能量可以为负）
询问k次或更少次游戏后是否可以经过所有的格子，若可以求出最大的剩余能量。
解题分析
带权值的最小K路径覆盖。
（最小路径覆盖数=总节点数-最大匹配数)
将n*m个点，每个点拆成两个，X，Y。
由S向X连容量为1费用为0的边，Y向T连容量为1费用为0的边，X向可到达的Y连容量为1费用为所消耗能量（加上所得）。
这样直接跑可求出最大匹配数。所有未流满的Y点数量即为最小路径覆盖数。
考虑如何实现K路径覆盖。
新建一个点Q,由S向Q连容量为k费用为0的边，有Q向Y连容量为1费用为0的边。即表示可以新增的起点数为k。
这样跑一遍最小费用最大流，若不是满流则说明无解。
参考程序
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std; #define V 2008
#define E 1000008
#define INF 200000000
int n,m,k,S,T,Que,num;
int a[V][V],mark[V][V]; int pd[V],dis[V],pre[V];
struct line{
int u,v,c,w,nt;
}eg[E];
int lt[V],sum; void adt(int u,int v,int c,int w) {
eg[++sum].u=u; eg[sum].v=v; eg[sum].c=c;
eg[sum].w=w; eg[sum].nt=lt[u]; lt[u]=sum;
} void add(int u,int v,int c,int w) {
adt(u,v,c,w); adt(v,u,,-w);
//printf("%d %d %d %d\n",u,v,c,w);
} void init(){ sum=; num=;
memset(lt,,sizeof(lt)); char s[V];
scanf("%d %d %d",&n,&m,&k);
for (int i=;i<=n;i++){
scanf("%s",s+);
for (int j=;j<=m;j++)
{
a[i][j]=s[j]-'';
mark[i][j]=++num;
}
} S=; T=num*+;
add(S,T-,k,);
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
{
add(S,mark[i][j],,);
add(mark[i][j]+num,T,,);
add(T-,mark[i][j]+num,,);
}
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
for (int k=;k<=n;k++)
for (int l=;l<=m;l++)
if (i==k && l>j || j==l && k>i)
{
int x=abs(i-k)+abs(j-l)-;
if (a[i][j]==a[k][l]) x-=a[i][j];
add(mark[i][j],mark[k][l]+num,,x);
}
n=T;
} bool spfa() {
queue <int> Q;
for (int i=;i<=n;i++) {
dis[i]=INF;
pd[i]=;
pre[i]=-;
}
dis[S]=; pd[S]=; Q.push(S);
while (!Q.empty()) {
int u = Q.front();
for (int i=lt[u];i;i=eg[i].nt)
if (eg[i].c>) {
int v=eg[i].v;
if (dis[u]+eg[i].w<dis[v]) {
dis[v]=dis[u]+eg[i].w;
pre[v]=i;
if (!pd[v]) {
Q.push(v);
pd[v]=;
}
}
}
pd[u]=;
Q.pop();
}
return dis[T]!=INF;
} void minCmaxF(){
int minC=,maxF=,flow;
while (spfa()) {
flow=INF;
for (int i=pre[T];~i;i=pre[eg[i].u])
flow=min(flow,eg[i].c);
for (int i=pre[T];~i;i=pre[eg[i].u]) {
eg[i].c-=flow;
eg[i^].c+=flow;
}
maxF+=flow;
minC+=flow*dis[T];
}
if (maxF==num) printf("%d\n",-minC); else printf("-1\n"); } int main(){
scanf("%d",&Que);
for (int tt=;tt<=Que;tt++){
init();
printf("Case %d : ",tt );
minCmaxF();
}
}