电商电商网站建设,开发商城网站开发,免费公司网站建站,网站运维服务内容题意#xff1a;
题意#xff1a; 有n个人#xff0c;m对人相互认识#xff1b; 问能否分成两个组#xff0c;组内任意两个人之间不认识#xff1b; 若不能#xff0c;则输出No#xff1b; 若能#xff0c;则相互认识的两个人一间房#xff0c;求最多需要几间房
题意 有n个人m对人相互认识 问能否分成两个组组内任意两个人之间不认识 若不能则输出No 若能则相互认识的两个人一间房求最多需要几间房 给出一些学生的认识情况比如A和B认识B和C认识但是A和C不一定认识。现在问能否将这些学生分成两个组并且每组中的学生互相不认识如果能分求出最大能匹配的学生对数。
题目
There are a group of students. Some of them may know each other, while others don’t. For example, A and B know each other, B and C know each other. But this may not imply that A and C know each other.
Now you are given all pairs of students who know each other. Your task is to divide the students into two groups so that any two students in the same group don’t know each other.If this goal can be achieved, then arrange them into double rooms. Remember, only paris appearing in the previous given set can live in the same room, which means only known students can live in the same room.
Calculate the maximum number of pairs that can be arranged into these double rooms.
Input
For each data set: The first line gives two integers, n and m(1n200), indicating there are n students and m pairs of students who know each other. The next m lines give such pairs.
Proceed to the end of file.
Output
If these students cannot be divided into two groups, print “No”. Otherwise, print the maximum number of pairs that can be arranged in those rooms.
Sample Input
4 4 1 2 1 3 1 4 2 3 6 5 1 2 1 3 1 4 2 5 3 6
Sample Output
No 3
题解
1首先bfs判断是否是二分图然后求二分最大匹配。 2判断是否为二分图在无向图G中无向图G为二分图的充分必要条件是G至少有两个顶点,且当存在回路时其所有回路的长度均为偶数。回路就是环路也就是判断是否存在奇数环。如果存在奇数回路(回路中节点个数为奇数)则不是二分图。否则是二分图。 采用染色法bfs染色法是将一个点先染色然后把和它相邻的点染成不同的颜色如果遇到相邻点的颜色相同的情况就不是二分图 3 染色法判断回路奇偶性把相邻两点染成黑白两色如果相邻两点出现颜色相同则存在奇数回路。也就是非二分图。 4匹配的对数由于是两个相同的集合进行配对所以最后将结果除2
AC代码
#includestdio.h
#includestring.h
#includequeue
#includealgorithm
using namespace std;
const int M2e210;
int n,m,dp[M],book[M],e[M],map[M][M];
bool dfs()//先要判断能否分成两组使得每组内的人互不认识即判断是否为二分图
{memset(dp,-1,sizeof(dp));//染色数组-1为未染01则为两种不同颜色for(int i1; in; i){if(dp[i]!-1)continue;dp[i]0;queueintq;q.push(i);while(!q.empty()){int headq.front();q.pop();for(int j1; jn; j){if(!map[head][j])continue;if(dp[j]!-1dp[head]dp[j])//把相邻两点染成黑白两色如果相邻两点出现颜色相同则存在奇数回路。也就是非二分图。return false;else if(dp[j]-1){dp[j]!dp[head];q.push(j);}}}}return true;
}
bool math(int x)//匈牙利算法
{for(int i1; in; i)if(!book[i]map[x][i]){book[i]1;if(!e[i]||math(e[i])){e[i]x;return true;}}return false;
}
int main()
{while(~scanf(%d%d,n,m)){memset(map,0,sizeof(map));for(int i1; im; i){int a,b;scanf(%d%d,a,b);map[a][b]map[b][a]1;}if(dfs()false){printf(No\n);continue;}int ans0;memset(e,0,sizeof(e));for(int i1; in; i){memset(book,0,sizeof(book));if(math(i))ans;}printf(%d\n,ans/2);//求对数除2}return 0;
}
