Algorithm Princeton part II (week3)

这次图论的课第一遍听得云里雾里，仔细看了讲义发现懂了不少，还是挺深奥的。。anyway，作业这次竟然一遍过了，直接吓尿了。。。

最近进度比较慢，看到算法就心烦。这次又是讲的什么maxflow mincut,那一块听了好久。。后来问一个搞空间通信的同学，说这一块内容属于拓扑学的范畴。这次作业最大的难点，时间复杂度和空间度复杂度好像都没有了。所以代码可以随便写，只要能实现要求就可以了。
我觉得得搞清楚如何使用maxflow-mincut模型来解决这个问题。之前看人给的提示，说是，当右边全满时，如果左边的有未全满的，那么就一定eliminated的了。我也是照着这个写的。后来发现这样子是不全面的。
我的思路是，遍历左边的每条边，某条边没满时，查找到这条边to结点对应的那场比赛的双方，在右侧对应的两条边，看下这两条边是否已经满了。如果没满，那就一定eliminated的了。
如果右侧有边直接capacity < 0，那就直接退出这个方法了。这是我之前没想到的。我以为其他的仍然也需要验证，然后放进subset。但这里显然进行了简单处理。
另外，我觉得处理输入的字符串，构造多个数组，这一块儿，我并没能一次通过，因为有好多情况没考虑到。然后不断地换新的输入，不断地改进自己的constructor才搞好。是不是有一些模板式的处理方法我不知道？或者说有一些string类函数可以直接调用？但是中间可能有三个空格，两个空格，一个空格。结尾处可能是空格，也可能单纯的就是数字。我就是用一个头指针一个尾指针不停地扫描出来的。所以经常出错。
Anyway, 又熬过了一次作业。。

交作业

这次作业第一次一遍就100分，真是吃惊。这次作业感觉理解有点难，起码我感觉是这样。代码码起来也没有所说的很easy，但是只要把那几个test过了，基本就满分了。
另外发现了几个warning，求教各位，不懂啥问题：

其中15行是str = in.readLine().trim().split("\\s+");
124行是FordFulkerson FF= new FordFulkerson(FN, 0, numberOfTeams() + (numOfTeams -1) * (numberOfTeams() - 2) / 2);
多谢！

dnalwqer 发表于 2015-4-12 20:04
LZ，我碰到一个问题，还望指点，那个subset R是怎么求出来的？我找了半天instruction也没发现，是将剩下的 ...

不是有FF里面的inCut方法么，就是判断与S相连的min-cut的，直接用就行了

这次作业编程的难度不高，但是问题非常抽象，得仔细琢磨才能想明白

LZ，我碰到一个问题，还望指点，那个subset R是怎么求出来的？我找了半天instruction也没发现，是将剩下的没有eliminated的加起来吗？

搞定~  交个作业。。。。。

谢谢你们！谢谢coursera！

请问lz，跳过I的projects直接做II的OK吗？没有什么关联吧？

bluestarwing 发表于 2015-6-25 02:25
请问lz，跳过I的projects直接做II的OK吗？没有什么关联吧？

我记忆中是没什么关联，基础好的话直接上吧