hust校赛d题 PHP is the best language int the world(二分图着色+递推)

程序员文章站 2022-03-29 18:17:05

...

题目大意是给出一个图，要求判断是否是二分图，如果是，求二分图两个节点集之差的最小值。

两个人如果不会争吵的话连一条边，形成一个图，取这个图的反图。这个反图之间存在边则

说明这两个人不能在同一个team。首先二分染色看是否能够将反图变成一个二分图。

如果能染成二分图，记录每个二分图颜色人数。在某个联通分量里白色/黑色可以交换。

接下来用dp[i][j] = 1表示前i个联通分量能够形成一个人数为j的team.

然后在dp[num][s]里面遍历找到相差最小的team分法，输出答案，num为联通分量数。

代码如下：

#include  #include  #include  #include  #include  #include  #include  #include  #include  #include #include#include #includeusing namespace std;  #define LL long long  const int maxn = 100 + 5;const int INF = 1000000000;int color[maxn];//vector G[maxn];int G[maxn][maxn];int one, two, num[maxn][2], n;int d[maxn][maxn];bool bipartite(int u) {                       //判断节点u所在的联通分量是否为二分图 	if(color[u] == 1) one++;	else two++;	for(int v = 1; v   
  
     ??

相关标签： hust校赛d题 PHP is the best language int the world(二分图着色+递推)

上一篇： PHP调用其他文件中的类

下一篇： PHP表单数组的具体使用方法介绍_PHP教程