BZOJ3894 文理分科（最小割）

青旅半醒 2022-01-10 16:07 235阅读 0赞

## 题意： ##

## 文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）    小P所在的班级要进行文理分科。他的班级可以用一个n\*m的矩阵进行描述,每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：    1．如果第i行第秒J的同学选择了文科，则他将获得art\[i\]\[j\]的满意值，如果选择理科，将得到science\[i\]\[j\]的满意值。    2．如果第i行第J列的同学选择了文科，并且他相邻（两个格子相邻当且仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开心，所以会增加same\_art\[i\]\[j\]的满意值。    3．如果第i行第j列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加same\_science\[i\]j\[\]的满意值。小P想知道，大家应该如何选择，才能使所有人的满意值之和最大。请告诉他这个最大值。 ##

## 分析：  ##

## **首先只考虑前两种情况，即对于每个人只选文科或者选理科的情况。从源点向每个点连一条边，边权为art,从汇点向每个点连一条边，边权为science。单看这个图直接跑网络流会产生最小割。如果一条边被割断了就表示不选择这个情况。也就是说：若源点连出的边被割断了,则表示我不选择文科。同理，若连到汇点的边被割断了就表示不选择理科。那么前两种情况就处理完了。剩下的就是处理周围同学的事情了。对于一个点周围的几个相邻的点的情况，我们新建一个点，将S连向这个点，长度为同时选文可获得的收益，如果该边被割，则说明这些人不同时选文，不能获得同时选文可获得的收益。理科的情况以此类推。那么怎么保证如果这几个人选相同的科目时能够不割断这个边呢？从周围这个点向周围的同学连一条INF的边，那么这种情况下都选同一科时，新边肯定不会被割断，就保证了网络流当中的割是使剩下的图满足条件的最小值。理科的建图就是相反的（从周围的同学连向自己）。这个时候网络流中的割就是舍去之后满足条件的需要舍去的值。根据最大流最小割定理。求出网络流图中的最大流，就是最小割。那么用总的开心值减去最小割就是最大流了。**建图如下。 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][]

## 总结：对于网格中相邻节点关系的处理，可以通过增加节点的方式来解决。 ##

## 代码：待补。参考[https://blog.csdn.net/u014085852/article/details/81334388][https_blog.csdn.net_u014085852_article_details_81334388]。 ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20220110/c7fceffea28d4062a7e2653544a523ee.png
[https_blog.csdn.net_u014085852_article_details_81334388]: https://blog.csdn.net/u014085852/article/details/81334388