最小割。考虑建图。

因为要求最小代价,所以我们把加分变成扣分,令\(y[i][j]=100-x[i][j]\),如果\(x[i][j]=-1\)即不存在这样的课,那么我们令\(y[i][j]=INF\)。

我们设图中的点为\((i,j)\)表示在\(j\)学期的课程\(i\)。

对于每学期的课,如下建图:

  • 源点\(S->(i,1)\),代价为\(y[i][1]\)
  • \((i,j)->(i,j+1)(1\le j < m)\),代价为\(y[i][j+1]\)
  • \((i,m)->\)汇点\(T\),代价为\(INF\)

显然,要割掉这条链上的至少一条边才能使得图不联通,割掉的边即为上课的时间。

若课程\(x\)为课程\(y\)的前置课,如下建图:

  • 源点\(S->(y,1)\),代价为\(INF\),表示不允许在第一学期上课\(y\)
  • \((x,i)->(y,i+1)(1\le i < m)\),代价为\(INF\),表示不允许\(y\)在\(x\)之前上,如果\(y\)在\(x\)之前上,显然这条割边是无效的

然后就是跑最大流了。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注