【CodeChef】Course Selection


最小割。考虑建图。

因为要求最小代价,所以我们把加分变成扣分,令\(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\)之前上,显然这条割边是无效的

然后就是跑最大流了。

 

You may also like

圆方树学习笔记

Codeforces Round #621

Codeforces Round #619

LEAVE A COMMENT

Statistics

  • 0
  • 21,615

Categories

Archive

Comments