hust校赛d题 PHP is the best language int the world(二分图着色+递推)
程序员文章站
2022-03-25 20:00:45
...
题目大意是给出一个图,要求判断是否是二分图,如果是,求二分图两个节点集之差的最小值。
两个人如果不会争吵的话连一条边,形成一个图,取这个图的反图。这个反图之间存在边则
说明这两个人不能在同一个team。首先二分染色看是否能够将反图变成一个二分图。
如果能染成二分图,记录每个二分图颜色人数。在某个联通分量里白色/黑色可以交换。
接下来用dp[i][j] = 1表示前i个联通分量能够形成一个人数为j的team.
然后在dp[num][s]里面遍历找到相差最小的team分法,输出答案,num为联通分量数。
代码如下:
#include#include #include #include #include #include #include #include
上一篇: 一些常用的正则表达式总结
下一篇: 揭秘php深受Web开发者喜爱的原因