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大學(xué)生程序設(shè)計(jì)競賽
示例程序
比賽的時(shí)候沒有往圖這方面考慮
比賽結(jié)束后發(fā)現(xiàn)是匹配問題，然后就從這開始，一直悲劇了
這個(gè)題目我寫了兩種解法
1，構(gòu)造二分圖，求二分圖的最大權(quán)匹配，然后貪掉小的邊，復(fù)雜度 （n^3）超時(shí)
2，最大費(fèi)用可行流，加一條限制邊，變?yōu)樽钚≠M(fèi)用流問題
兩個(gè)模型不寫了，這幾天搞這個(gè)題無力了
貼下代碼，小小的參考了下段神的代碼，
本來寫的是鄰接矩陣的，結(jié)果無奈到死，一直改不出來，我想是不是那個(gè)沒法處理負(fù)權(quán)邊呢？我也不知道 是不是
然后就改成了鄰接表的
代碼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 最小費(fèi)用流，（最小費(fèi)用路的做法，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個(gè)，k限制1個(gè)，附加節(jié)點(diǎn)31（0-30），兩相鄰h的合并頂點(diǎn)n-1 總共33+n個(gè)節(jié)點(diǎn)
t=32+n;
//////構(gòu)圖
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));//設(shè)為負(fù)權(quán)，求最小費(fè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;
}