题意：
题目链接
有N个程序需要运行，同一个程序在不同的运行空间大小中运行时间不同(一个程序在2G的内存下运行5s，5G的内存下运行2s .etc)
给出M个运行区域，每个区域有各自的空间，同一时间一个区域只能运行一个程序
求如何安排使得所有程序的结束时间之和最小 N<=10 M<=50
（这样说好像也说不太清楚，其实看样例最好懂了/xyx）
思路：
这道题的建模极为经典
对于一个运行区域，设每个程序依次用时t1,t2....tk
那么这个区域的总用时为ri=kt1+(k-1)t2+....+tk
容易发现，倒数第i个的实际贡献是itk
于是从每一个程序出发向每个运行区域（共nm个代表这个区域的倒数第若干个运行）连边，边权为序数*程序用时
然后就是一个二分图带权最小匹配了
code:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
using namespace std;
int m,n;
int mem[15];
int ep1[55],ep2[15][55],lk[55][15][55],match[15][55],slack[15][55],val[15][55];
bool vis1[55],vis2[15][55];
pair<int,int>fm[55];
inline int read()
{
int s=0,w=1; char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
return s*w;
}
inline void _init()
{
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
for(int k=1;k<=n;++k)
lk[i][j][k]=-1e9;
for(int i=1;i<=m;++i)mem[i]=read();
for(int i=1;i<=n;++i)
{
int k=read();
int pre_s=read(),pre_t=read();
for(int j=2;j<=k;++j)
{
int s=read(),t=read();
for(int e=1;e<=m;++e)
if(mem[e]>=pre_s&&mem[e]<s)
for(int p=1;p<=n;++p)
lk[i][e][p]=-pre_t*p;
pre_s=s,pre_t=t;
}
for(int e=1;e<=m;++e)
if(mem[e]>=pre_s)
for(int p=1;p<=n;++p)
lk[i][e][p]=-pre_t*p;
}
}
bool dfs(int x)
{
vis1[x]=1;
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
{
if(vis2[i][j]) continue;
int gap=ep1[x]+ep2[i][j]-lk[x][i][j];
if(!gap)
{
vis2[i][j]=1;
if(match[i][j]==-1||dfs(match[i][j]))
{
match[i][j]=x;
return true;
}
}
else slack[i][j]=min(slack[i][j],gap);
}
return false;
}
inline void KM()
{
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
match[i][j]=-1,ep2[i][j]=0;
for(int i=1;i<=n;++i)
{
ep1[i]=-1e9;
for(int j=1;j<=m;++j)
for(int k=1;k<=n;++k)
ep1[i]=max(ep1[i],lk[i][j][k]);
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
for(int k=1;k<=n;++k)
slack[j][k]=1e9;
while(1)
{
for(int j=1;j<=n;++j)vis1[j]=0;
for(int j=1;j<=m;++j)
for(int k=1;k<=n;++k)
vis2[j][k]=0;
if(dfs(i)) break;
int d=1e9;
for(int j=1;j<=m;++j)
for(int k=1;k<=n;++k)
if(!vis2[j][k])
d=min(d,slack[j][k]);
for(int j=1;j<=n;++j)
if(vis1[j]) ep1[j]-=d;
for(int j=1;j<=m;++j)
for(int k=1;k<=n;++k)
{
if(vis2[j][k]) ep2[j][k]+=d;
else slack[j][k]-=d;
}
}
}
}
inline void _print()
{
int ans=0;
for(int i=1;i<=n;++i)
ans-=ep1[i];
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
ans-=ep2[i][j];
printf("Average turnaround time = %.2f
",(double)ans/n);
memset(val,0,sizeof(val));
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
if(match[i][j]!=-1)
{
fm[match[i][j]]=make_pair(i,j);
val[i][j]=lk[match[i][j]][i][j]/j;
}
for(int i=1;i<=m;++i)
for(int j=n-1;j;--j)
val[i][j]+=val[i][j+1];
for(int i=1;i<=n;++i)
{
int &u=fm[i].first,&v=fm[i].second;
printf("Program %d runs in region %d from %d to %d
",i,u,-val[u][v]+lk[i][u][v]/v,-val[u][v]);
}
puts("");
}
int main()
{
for(int q=1;;++q)
{
m=read(),n=read();
if(!m && !n) break;
_init();KM();
printf("Case %d
",q);
_print();
}
return 0;
}
代码太丑，巨佬勿喷/xyx