欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

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  #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   

??