HDU 4862（费用流）

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。

　　这样跑一遍最小费用最大流，若不是满流则说明无解。

参考程序

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <queue>
  5 using namespace std;
  6 
  7 #define V 2008
  8 #define E 1000008
  9 #define INF 200000000
 10 int n,m,k,S,T,Que,num;
 11 int a[V][V],mark[V][V];
 12 
 13 int pd[V],dis[V],pre[V];
 14 struct line{
 15     int u,v,c,w,nt;
 16 }eg[E];
 17 int lt[V],sum;
 18 
 19 void adt(int u,int v,int c,int w) {
 20     eg[++sum].u=u; eg[sum].v=v; eg[sum].c=c; 
 21     eg[sum].w=w; eg[sum].nt=lt[u]; lt[u]=sum;
 22 }
 23 
 24 void add(int u,int v,int c,int w) {
 25     adt(u,v,c,w); adt(v,u,0,-w);
 26     //printf("%d %d %d %d
",u,v,c,w);
 27 }
 28 
 29 void init(){
 30 
 31     sum=1; num=0;
 32     memset(lt,0,sizeof(lt));
 33 
 34     char  s[V];
 35     scanf("%d %d %d",&n,&m,&k);
 36     for (int i=1;i<=n;i++){
 37         scanf("%s",s+1);
 38         for (int j=1;j<=m;j++)
 39         {
 40             a[i][j]=s[j]-'0';
 41             mark[i][j]=++num;
 42         }
 43     }
 44 
 45     S=0; T=num*2+2;
 46     add(S,T-1,k,0);
 47     for (int i=1;i<=n;i++)
 48         for (int j=1;j<=m;j++)
 49         {
 50             add(S,mark[i][j],1,0);
 51             add(mark[i][j]+num,T,1,0);    
 52             add(T-1,mark[i][j]+num,1,0);
 53         }
 54     for (int i=1;i<=n;i++)
 55         for (int j=1;j<=m;j++)
 56             for (int k=1;k<=n;k++)
 57                 for (int l=1;l<=m;l++)
 58                     if (i==k && l>j || j==l && k>i)
 59                     {   
 60                         int x=abs(i-k)+abs(j-l)-1;
 61                         if (a[i][j]==a[k][l]) x-=a[i][j];
 62                         add(mark[i][j],mark[k][l]+num,1,x);
 63                     }
 64     n=T;
 65 }
 66 
 67 bool spfa() {
 68     queue <int> Q;
 69     for (int i=0;i<=n;i++) {
 70         dis[i]=INF;
 71         pd[i]=0;
 72         pre[i]=-1;
 73     }
 74     dis[S]=0; pd[S]=1; Q.push(S);
 75     while (!Q.empty()) {
 76         int u = Q.front();
 77         for (int i=lt[u];i;i=eg[i].nt) 
 78             if (eg[i].c>0) {
 79                 int v=eg[i].v;
 80                 if (dis[u]+eg[i].w<dis[v]) {
 81                     dis[v]=dis[u]+eg[i].w;
 82                     pre[v]=i;
 83                     if (!pd[v]) {
 84                         Q.push(v);
 85                         pd[v]=1;
 86                     }
 87                 }
 88             }
 89         pd[u]=0;
 90         Q.pop();
 91     }
 92     return dis[T]!=INF;
 93 }
 94 
 95 void minCmaxF(){
 96     int minC=0,maxF=0,flow;
 97     while (spfa()) {
 98         flow=INF;
 99         for (int i=pre[T];~i;i=pre[eg[i].u])
100             flow=min(flow,eg[i].c);
101         for (int i=pre[T];~i;i=pre[eg[i].u]) {
102             eg[i].c-=flow;
103             eg[i^1].c+=flow;
104         }
105         maxF+=flow;
106         minC+=flow*dis[T];
107     }
108    if (maxF==num) printf("%d
",-minC); else printf("-1
");
109    
110 }
111 
112 int main(){
113     scanf("%d",&Que);
114     for (int tt=1;tt<=Que;tt++){
115         init();
116         printf("Case %d : ",tt  );
117         minCmaxF();
118     }
119 }

View Code