题意：现有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=111,M=44444,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=0,e[cnt].w=-w; e[cnt].next=head[v],head[v]=cnt++; } void init() { memset(head,-1,sizeof(head)); cnt=0; } int spfa() { int i,u,v; double w; memset(pre,-1,sizeof(pre)); memset(p,0,sizeof(p)); memset(f,0,sizeof(f)); for(i=0;i<=t;i++) d[i]=-1.0*INF; l=r=0;d[s]=0;f[s]=INF;q[++r]=s; while(l<r) { p[u=q[++l]]=0; for(i=head[u];i!=-1;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]=1; } } } } return f[t]; } double getp(int x,int w) { return (4.0-3.0*(100-x)*(100-x)/1600)*w; } void MicMaf() { int m; while(m=spfa()) { for(int i=pre[t];i!=-1;i=pre[e[i].u]) { e[i].c-=m; e[i^1].c+=m; } } } int main() { int n,m,k,i,j,x; while(scanf("%d%d%d",&n,&k,&m),n||m||k) { init();s=0,t=n+m+1; for(i=1;i<=m;i++) scanf("%d",&w[i]); for(i=1;i<=m;i++) scanf("%d",&b[i]); for(i=1;i<=n;i++) { add(i+m,t,k,0); for(j=1;j<=m;j++) { scanf("%d",&x); if(x) add(j,i+m,k,0); } } double pre,cur; for(i=1;i<=m;i++) { if(b[i]<60) { add(s,i,60-b[i],1.0*INF); pre=getp(60,w[i]); for(j=61;j<=100;j++) { cur=getp(j,w[i]); add(s,i,1,cur-pre); pre=cur; } } else { pre=getp(b[i],w[i]); for(j=b[i]+1;j<=100;j++) { cur=getp(j,w[i]); add(s,i,1,cur-pre); pre=cur; } } } MicMaf(); for(i=head[s];i!=-1;i=e[i].next) b[e[i].v]+=e[i^1].c; int sum=0;double ans=0; for(i=1;i<=m;i++) sum+=w[i]; for(i=1;i<=m;i++) { if(b[i]<60) break; ans+=getp(b[i],w[i])/sum; } if(i<=m) ans=0; printf("%.6f ",ans); } return 0; }
参考文章：http://www.cnblogs.com/jianglangcaijin/archive/2012/10/06/2713375.html