题意：现有m门课程需要复习，已知每门课程的基础分和学分，共有n天可以复习，每天分为k个时间段，每个时间段可以复习一门课程，并使这门课程的分数加一，问在不挂科的情况下最高的绩点。
思路：（没做过费用流的转这里：http://www.cnblogs.com/L-King/p/5316359.html），首先我们得保证每门课程都达到60分，所以对每一门未到60分的课程添加一条从S（即源点）出发的弧，容量为60-该课程的分数，花费为INF，因此在执行费用流的时候会优先增广此弧。此时，我们已经保证了在条件允许的情况下，每门课程都达到60分以上。接下来就是剩下的分数的分配，设f(x)为x对应的p；可解得f(x)以及f'(x)都是减函数(x>=60)，即f(x+1)-f(x)<f(x)-f(x-1)，因此可以对每一分连接一条容量为1，费用为f(x)-f(x-1)的弧。最后就是每门课程与对应的天连接一条容量为k，费用为0的弧，每一天与T(即汇点)连接一条容量为k，费用为0的弧。最后跑一下费用流，然后判断是否有课程未达到60分。
代码：
#include<stdio.h>
#include<string.h>
#define min(x,y) (x)<(y)?(x):(y) const int N=,M=,INF=0x3f3f3f3f;
struct node
{
int u,v,c,next;
double w;
}e[M];
int head[N],q[M],p[N],pre[N];
int s,t,l,r,cnt;
double d[N];
int w[N],b[N],f[N];
void add(int u,int v,int c,double w)
{
e[cnt].u=u,e[cnt].v=v,e[cnt].c=c,e[cnt].w=w;
e[cnt].next=head[u],head[u]=cnt++;
e[cnt].u=v,e[cnt].v=u,e[cnt].c=,e[cnt].w=-w;
e[cnt].next=head[v],head[v]=cnt++;
}
void init()
{
memset(head,-,sizeof(head));
cnt=;
} int spfa()
{
int i,u,v;
double w;
memset(pre,-,sizeof(pre));
memset(p,,sizeof(p));
memset(f,,sizeof(f));
for(i=;i<=t;i++) d[i]=-1.0*INF;
l=r=;d[s]=;f[s]=INF;q[++r]=s;
while(l<r)
{
p[u=q[++l]]=;
for(i=head[u];i!=-;i=e[i].next)
{
v=e[i].v,w=e[i].w;
if(e[i].c&&d[v]<d[u]+w)
{
d[v]=d[u]+w;
f[v]=min(f[u],e[i].c);
pre[v]=i;
if(!p[v])
{
q[++r]=v;
p[v]=;
}
}
}
}
return f[t];
} double getp(int x,int w)
{
return (4.0-3.0*(-x)*(-x)/)*w;
}
void MicMaf()
{
int m;
while(m=spfa())
{
for(int i=pre[t];i!=-;i=pre[e[i].u])
{
e[i].c-=m;
e[i^].c+=m;
}
}
}
int main()
{
int n,m,k,i,j,x;
while(scanf("%d%d%d",&n,&k,&m),n||m||k)
{
init();s=,t=n+m+;
for(i=;i<=m;i++) scanf("%d",&w[i]);
for(i=;i<=m;i++) scanf("%d",&b[i]);
for(i=;i<=n;i++)
{
add(i+m,t,k,);
for(j=;j<=m;j++)
{
scanf("%d",&x);
if(x) add(j,i+m,k,);
}
}
double pre,cur;
for(i=;i<=m;i++)
{
if(b[i]<)
{
add(s,i,-b[i],1.0*INF);
pre=getp(,w[i]);
for(j=;j<=;j++)
{
cur=getp(j,w[i]);
add(s,i,,cur-pre);
pre=cur;
}
}
else
{
pre=getp(b[i],w[i]);
for(j=b[i]+;j<=;j++)
{
cur=getp(j,w[i]);
add(s,i,,cur-pre);
pre=cur;
}
}
}
MicMaf();
for(i=head[s];i!=-;i=e[i].next)
b[e[i].v]+=e[i^].c;
int sum=;double ans=;
for(i=;i<=m;i++)
sum+=w[i];
for(i=;i<=m;i++)
{
if(b[i]<) break;
ans+=getp(b[i],w[i])/sum;
}
if(i<=m) ans=;
printf("%.6f\n",ans);
}
return ;
}
参考文章：http://www.cnblogs.com/jianglangcaijin/archive/2012/10/06/2713375.html