http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2414
An interesting game
Time Limit: 2000MS Memory limit: 65536K
题目描述
Xiao Ming recently designs a little game, in front of player there are N small hillsides put in order, now Xiao Ming wants to increase some hillsides to block the player, so he prepared another M hillsides, but he does not hope it will be too difficult,so only K in M hillsides are selected to add at most. Paying attention to the original N hillsides, between each two can add only one hillside. Xiao Ming expects players from the starting place to reach the destination in turn and passes all the hillsides to make his distance travelled longest. Please help Xiao Ming how to add the hillsides that he prepared. Note: The distance between two hillsides is the absolute value of their height difference.
输入
The first line of input is T, (1 <= T <= 100) the number of test cases. Each test case starts with three integers N,M,K (2 <= N <= 1000, 1 <= M <= 1000, 1 <= K <= M and 1 <= K < N), which means that the number of original hillsides, the number of hillsides Xiao Ming prepared and The number of most Xiao Ming can choose from he prepared. Then follow two lines, the first line contains N integers Xi (0 <= Xi <= 30), denoting the height of each original hillside, Note: The first integer is player's starting place and the last integer is player's destination. The second line contains M integers Yi (0 <= Yi <= 30), denoting the height of prepared each hillsides.
输出
For every test case, you should output "Case k: " first in a single line, where k indicates the case number and starts from 1. Then print the distance player can travel longest.
示例输入
3 2 1 1 6 9 8 2 1 1 6 9 15 3 2 1 5 9 15 21 22
示例输出
Case 1: 3 Case 2: 15 Case 3: 36
提示
来源
2012年"浪潮杯"山东省第三届ACM大学生程序设计竞赛
示例程序
比赛的时候没有往图这方面考虑
比赛结束后发现是匹配问题，然后就从这开始，一直悲剧了
这个题目我写了两种解法
1，构造二分图，求二分图的最大权匹配，然后贪掉小的边，复杂度 （n^3）超时
2，最大费用可行流，加一条限制边，变为最小费用流问题
两个模型不写了，这几天搞这个题无力了
贴下代码，小小的参考了下段神的代码，
本来写的是邻接矩阵的，结果无奈到死，一直改不出来，我想是不是那个没法处理负权边呢？我也不知道 是不是
然后就改成了邻接表的
代码1 KM
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define pp printf("here\n")
#define maxn 1005
#define inf 0xfffffff
using namespace std;
int map[maxn][maxn],w[maxn][maxn],f[maxn],a[maxn];
int b[maxn],x[maxn],y[maxn],pre[maxn];
bool visx[maxn],visy[maxn];
int n,m,k,num;
int ans,slack;
int count1=0;
int lx[maxn],ly[maxn];
int maty[maxn],matx[maxn];
int fx[maxn],fy[maxn];
int nx,ny;
struct node
{
int u,val;
} edge[maxn];
int abs1(int x)
{
if(x<0) return -x;
else return x;
}
int cmp(node t1,node t2)
{
return t1.val<t2.val;
}
int path(int u)
{
fx[u] = 1;
for (int v = 1; v <= ny; v++)
if (lx[u] + ly[v] == w[u][v] && fy[v] < 0)
{
fy[v] = 1;
if (maty[v] < 0 || path(maty[v]))
{
matx[u] = v;
maty[v] = u;
return 1;
}
}
return 0;
}
int km()
{
int i,j,k,ret = 0;
memset(ly, 0, sizeof(ly));
for (i = 1; i <= nx; i++)
{
lx[i] = -inf;
for (j = 1; j <= ny; j++)
if (w[i][j] > lx[i]) lx[i] = w[i][j];
}
memset(matx, -1, sizeof(matx));
memset(maty, -1, sizeof(maty));
for (i = 1; i <= nx; i++)
{
memset(fx, -1, sizeof(fx));
memset(fy, -1, sizeof(fy));
if (!path(i))
{
i--;
int p = inf;
for (k = 1; k <= nx; k++)
{
if (fx[k] > 0)
for (j = 1; j <= ny; j++)
if (fy[j] < 0 && lx[k] + ly[j] - w[k][j] < p)
p=lx[k]+ly[j]-w[k][j];
}
for (j = 1; j <= ny; j++)
ly[j] += fy[j]<0 ? 0 : p;
for (j = 1; j <= nx; j++)
lx[j] -= fx[j]<0 ? 0 : p;
}
}
}
void work()
{
int i,j;
num=0;
for(i=1; i<=m; i++)
{
edge[num].u=pre[i];
edge[num].val=map[maty[i]][i];
ans+=edge[num].val;
num++;
}
sort(edge,edge+num,cmp);
//for(i=0;i<num;i++)
//printf("%d ",edge[i].val);printf("\n");
//for(i=0;i<num;i++) printf("%d %d\n",edge[i].u,edge[i].val);
for(i=0; i<m-k; i++)
ans=ans-edge[i].val;
}
int main()
{
int times,t,i,j,w;
scanf("%d",&t);
for(times=1; times<=t; times++)
{
scanf("%d%d%d",&n,&m,&k);
memset(a,0,sizeof(a));
memset(map,0,sizeof(map));
memset(f,0,sizeof(f));
ans=0;
for(i=1; i<=n; i++)
{
scanf("%d",&a[i]);
if(i!=1)
{
f[i-1]=abs1(a[i]-a[i-1]);
ans+=f[i-1];
}
}
for(i=1; i<=m; i++) scanf("%d",&b[i]);
//printf("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n");
for(i=1; i<=n-1; i++)
for(j=1; j<=m; j++)
{
w=abs1(a[i]-b[j])+abs1(a[i+1]-b[j])-f[i];
map[i][j]=w;
//printf("%d %d %d\n",i,j,w);
}
//printf("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n");
nx=n-1;
ny=m;
km();
work();
printf("Case %d: %d\n",times,ans);
}
return 0;
}
2 最小费用流，（最小费用路的做法，spfa+mincost）
#include<cstdio>
#include<cstring>
#define maxn 1500
#define maxm 150000
#define inf 0x7fffffff
int h[maxn],a[50],f[maxn];
int n,m,k,s,t;
int sum,ans,nn;
bool vis[maxn];
bool mmm;
int pre[maxn];
struct node
{
int v,next,cap,cost;
}edge[maxm+1];
int head[maxn],num;
void add(int u,int v,int cap,int cost)
{
edge[num].v=v;
edge[num].cap=cap;
edge[num].cost=cost;
edge[num].next=head[u];
head[u]=num++;
edge[num].v=u;
edge[num].cap=0;
edge[num].cost=-cost;
edge[num].next=head[v];
head[v]=num++;
}
int abs(int x)
{
if(x<0) return -x;
return x;
}
int min(int a,int b)
{
return a<b?a:b;
}
bool spfa()
{
int q[maxm+1],head1,tail,dist[maxn],i;
memset(dist,0x6f,sizeof(dist));
memset(vis,0,sizeof(vis));
head1=0;tail=1;
q[tail]=s;
vis[s]=1;
dist[s]=0;
while(head1!=tail)
{
head1=head1%maxm+1;
int u=q[head1];
for(i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(dist[v]>dist[u]+edge[i].cost&&edge[i].cap>0)
{
dist[v]=dist[u]+edge[i].cost;
pre[v]=i;
if(!vis[v])
{
tail=tail%maxm+1;
q[tail]=v;
vis[v]=1;
}
}
}
vis[u]=1;
}
if(dist[t]<0) return true;
else return false;
}
void mincost()
{
int i;
i=t;
while(i!=s)
{
ans+=edge[pre[i]].cost;
edge[pre[i]].cap--;
if(edge[pre[i]].cap==0) mmm=true;
edge[pre[i]^1].cap++;
if(edge[pre[i]^1].cap==1) mmm=true;
i=edge[pre[i]^1].v;
}
}
void work()
{
ans=0;
mmm=true;
while(!mmm||spfa())
{
mmm=false;
mincost();
}
sum=sum-ans;
}
int main()
{
int times,i,j,t1,x;
scanf("%d",&t1);
for(times=1; times<=t1; times++)
{
scanf("%d%d%d",&n,&m,&k);
sum=0;
for(i=1; i<=n; i++)
{
scanf("%d",&h[i]);
if(i!=1)
{
f[i-1]=abs(h[i]-h[i-1]);
sum=sum+f[i-1];
}
}
memset(a,0,sizeof(a));
for(i=1; i<=m; i++)
{
scanf("%d",&x);
a[x]++;
}
s=0;
nn=33+n;
//源汇2个，k限制1个，附加节点31（0-30），两相邻h的合并顶点n-1 总共33+n个节点
t=32+n;
//////构图
num=0;
memset(head,-1,sizeof(head));
add(0,1,k,0);
for(i=0; i<=30; i++)
{
add(1,i+2,a[i],0);
}
for(i=0; i<=30; i++)
if(a[i]!=0)
for(j=1; j<=n-1; j++)
if(f[j]<(abs(h[j]-i)+abs(h[j+1]-i)))
{
int ww=f[j]-(abs(h[j]-i)+abs(h[j+1]-i));//设为负权，求最小费用流
add(i+2,j+32,1,ww);
}
for(i=1; i<=n-1; i++)
{
add(i+32,t,1,0);
}
work();
printf("Case %d: %d\n",times,sum);
}
return 0;
}