虽然，最大匹配跟最小割原理一样，都从题意理解方面考虑，用最小割概念会好理解很多！

分析：
    把所有的row作为left nodes,把所有的column作为right nodes.设多一个源点跟汇点，源点连left nodes,汇点连right nodes,而left nodes跟right nodes之间的连边则由asteroids决定，这样就建立了一个网络图了。
    由于题意是要销毁所有的asteroids，也就是说让left nodes跟right nodes之间不再有连边，即是让left nodes跟right nodes成为两个独立集。而题目说要用做少的销毁次数达到目的，也就是说要去掉最少的边，让left nodes跟right nodes成为独立集，我们很容易就可以想到最小割原理了，并且只在left nodes跟right nodes之间切割。
    分析完毕，接着就靠你了^_^

• 多谢指点，想怎样构图都快想疯了。 (17) threetree 2008-09-09 11:08:18
  • Re:多谢指点，想怎样构图都快想疯了。 (13) saramand9 2008-09-12 22:49:10
    • Re:多谢指点，想怎样构图都快想疯了。 (42) ccnuzhang 2008-10-08 10:37:07