再来一道难一点的题

n个人应征n个工作，每个人只能干一件工作，每件工作只能一个人来做。第i个人做第j 件工作可以产生v(i,j)的收益（保证大于0），问怎样安排工作能使得n个人产生的总受益最大。输出这个最大收益值。
算法模型很一目了然了……当重温一遍基本代码吧

n<=100

快试试吧，
可以对自己使用挽尊卡咯~

◆

深搜？

快试试吧，
可以对自己使用挽尊卡咯~

◆

还是DP？

n=100就意味着100！种方案没有超强力剪枝是绝对不行地
我咋想到最大流了...

回复：5楼
其实有点靠谱了

我记得n个人k份工作貌似是最大流问题，反正考试碰到这个我是准备这么写了- -
正解应该不是DP就是图吧

回复：7楼
正解不是DP，是什么你可以再考虑考虑

..睡觉去算了
争取梦里作出来（不是没有过..）

KM?

回复：9楼
想想吧，提示你用流可以做，但是不是那么单纯的流。而且写这题写流，就杀鸡用牛刀了

回复：10楼
Bingo~我觉得这不是明摆着的事么……知道KM的肯定直接看出是KM

RDFZ的牛保佑我。

回复：13楼
别……这样会减我的RP……
都努力呗，好好考，无论结果如何不后悔就行了

嗯，学习了。
心态心态心态心态心态心态心态心态心态心态
话说北京减了五个名额。

下载贴吧APP
看高清直播、视频！

分享到: