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