hdu 4862 jump 最小k路径覆盖 km算法建模

【题意】：给你一个n*m的矩阵，填充着0-9的数字，每次能从一个点出发，到它的右边或者下边的点，花费为|x1-x2|+|y1-y2|-1，

如果跳跃的起点和终点的数字相同，则获得这个数字的收益，不能走已经走过的点

有K次重新选择起点的机会

如果可以走遍所有点，则输出最大的价值(收益-花费)，否则，输出-1

【思路】当二部图里的两部分子集相同的时候可以用km来求路径（路径没有重边和重复的点）和连通性。1配2 2配3 3配4 代表的就是路径1->2>3-> 4 所以关键就是建模了。

1.若点i 点j可以直接到达，就在i,j之间建边权值为：得到的能量-消耗的；

2.再增加k个点同每一个点建边权值为0，表示有K次重新选择起点的机会，每次可以可以从任意一个点开始；

3.同时每个点也分别和这k个点建边权值为0 表示一次可以只选一个点；

4.新增的点和自己有一条连边权值为0 表示放弃这次重新选起点的机会。

用km 算法求得的权值和<0 说明没有完美匹配（不能在k次以内完全覆盖）输出-1 ，否则输出结果。

  1 #include<iostream>
  2 #include<vector>
  3 #include<string.h>
  4 #include<queue>
  5 #include<math.h>
  6 #include<stdio.h>
  7 #define INF 9999999
  8 using namespace std;
  9 #define maxx 220
 10 int link[maxx],lx[maxx],ly[maxx],w[maxx][maxx];
 11 bool s[maxx],t[maxx];
 12 char str[maxx][maxx];
 13 
 14 void init(int n)
 15 {
 16     for(int i=0; i<n; i++)
 17         for(int j=0; j<n; j++)
 18             w[i][j]=-INF;
 19 }
 20 
 21 void add(int s,int t,int c)
 22 {
 23     w[s][t]=c;
 24 }
 25 
 26 int dfs(int x,int n)
 27 {
 28     s[x]=true;
 29     for(int i=0; i<n; i++)
 30         if(t[i]==false&&lx[x]+ly[i]==w[x][i])//&&w[x][i]!=-INF
 31         {
 32             t[i]=true;
 33             if(link[i]==-1||dfs(link[i],n))
 34             {
 35                 link[i]=x;
 36                 return 1;
 37             }
 38         }
 39     return 0;
 40 }
 41 
 42 void update(int n)
 43 {
 44     int a=INF;
 45     for(int i=0; i<n; i++)
 46         if(s[i])
 47             for(int j=0; j<n; j++)
 48                 if(!t[j])
 49                     a=min(a,lx[i]+ly[j]-w[i][j]);
 50     for(int i=0; i<n; i++)
 51     {
 52         if(s[i]) lx[i]-=a;
 53         if(t[i]) ly[i]+=a;
 54     }
 55 }
 56 
 57 int km(int n)
 58 {
 59     bool flag=false;
 60     memset(link,-1,sizeof(link));
 61     for(int i=0; i<n; i++)
 62     {
 63         lx[i]=ly[i]=0;
 64         for(int j=0; j<n; j++)
 65             lx[i]=max(lx[i],w[i][j]);
 66     }
 67     for(int i=0; i<n; i++)
 68     {
 69         while(1)
 70         {
 71             memset(s,false,sizeof(s));
 72             memset(t,false,sizeof(t));
 73             if(dfs(i,n))
 74                 break;
 75             else update(n);
 76         }
 77     }
 78     int ans=0;
 79     for(int i=0; i<n; i++)
 80         ans+=w[link[i]][i];
 81     return ans;
 82 
 83 }
 84 
 85 int main()
 86 {
 87     int i,j,n,m,t,k,cas=1;
 88     scanf("%d",&t);
 89     while(t--)
 90     {
 91         scanf("%d%d%d",&n,&m,&k);
 92         for(int i=0; i<n; i++)
 93             scanf("%s",str[i]);
 94         init(n*m+k);
 95         for(int i=0; i<n; i++)
 96             for(int j=0; j<m; j++)
 97             {
 98                 for(int p=i+1; p<n; p++)
 99                 {
100                     int temp=0;
101 
102                     if(str[i][j]==str[p][j])
103                         temp=str[i][j]-'0';
104                     temp-=(p-i-1);
105 
106                     add(i*m+j,p*m+j,temp);            // 1
107                 }
108                 for(int q=j+1; q<m; q++)
109                 {
110                     int temp=0;
111 
112                     if(str[i][j]==str[i][q])
113                         temp=str[i][j]-'0';
114                     temp-=(q-j-1);
115 
116                     add(i*m+j,i*m+q,temp);              //  1
117                 }
118             }
119         for(int p=n*m; p<n*m+k; p++) //  X中新增的k个点
120         {
121             for(int i=0; i<n; i++)
122                 for(int j=0; j<m; j++)
123                     {
124                         add(i*m+j,p,0);             //  2
125                         add(p,i*m+j,0);            //  3
126                     }
127             add(p,p,0);                          //4
128         }
129         printf("Case %d : ",cas++);
130         int ans;
131         ans=km(n*m+k);
132         if(ans<0)
133             printf("-1
");
134         else
135             printf("%d
",ans);
136     }
137 
138 }

hdu 4862 jump 最小k路径覆盖 km算法 建模

hdu 4862 jump 最小k路径覆盖 km算法建模