題目鏈接

Problem Description

Nowadays, at least one wrestling match is held every year in our country. There are a lot of people in the game is “good player”, the rest is “bad player”. Now, Xiao Ming is referee of the wrestling match and he has a list of the matches in his hand. At the same time, he knows some people are good players,some are bad players. He believes that every game is a battle between the good and the bad player. Now he wants to know whether all the people can be divided into “good player” and “bad player”.

Input

Input contains multiple sets of data.For each set of data,there are four numbers in the first line:N (1 ≤ N≤ 1000)、M(1 ≤M ≤ 10000)、X,Y(X+Y≤N ),in order to show the number of players(numbered 1toN ),the number of matches,the number of known “good players” and the number of known “bad players”.In the next M lines,Each line has two numbersa, b(a≠b) ,said there is a game between a and b .The next line has X different numbers.Each number is known as a “good player” number.The last line contains Y different numbers.Each number represents a known “bad player” number.Data guarantees there will not be a player number is a good player and also a bad player.

Output

If all the people can be divided into “good players” and “bad players”, output “YES”, otherwise output “NO”.

Sample Input

5 4 0 0 1 3 1 4 3 5 4 5 5 4 1 0 1 3 1 4 3 5 4 5 2

Sample Output

NO YES

AC

• 染色
  
• 首先將已經(jīng)確定的選手染色
• 如果還有選手存在比賽，而且沒有染色，那么他們肯定是成對存在，對這些選手染色（染成good和bad都可以）
• 最后判斷，如果還存在沒有染色的選手就不能組成合適的對陣

#include <iostream> #include <cmath> #include <map> #include <vector> #include <set> #include <cstring> #include <queue> #include <algorithm> #define ll long long #define ull unsigned long long #define N 1005 using namespace std;int n, m; vector<int> g[N]; int color[N]; // 染色判斷 bool dfs(int x, int y) {color[x] = y;for (int i = 0; i < g[x].size(); ++i) {if (color[g[x][i]] == (y ^ 1)) continue;else if (color[g[x][i]] == y) return false;else if (!dfs(g[x][i], y ^ 1)) return false;}return true; }bool solve() {// 將已知顏色染色 for (int i = 1; i <= n; ++i) {if (color[i] == 1 && !dfs(i, 1))return false;else if (color[i] == 0 && !dfs(i , 0))return false;}// 如果還有沒有沒有染色，但是存在比賽的選手，將其染色 for (int i = 1; i <= n; ++i) {if (color[i] == 2 && !dfs(i, 1))return false;}// 如果還有不確定的選手 for (int i = 1; i <= n; ++i) {if (color[i] == -1)return false;}return true; }int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endif int x, y;while (scanf("%d%d%d%d", &n, &m, &x, &y) != EOF) {memset(color, -1, sizeof(color));// color -1 表示沒有染色// color 1 表示選手為bad // color 0 表示選手為good // color 2 表示存在對決但是沒有被染色 for (int i = 0; i < m; ++i) {int u, v;scanf("%d%d", &u, &v);color[u] = color[v] = 2; g[u].push_back(v);g[v].push_back(u);}for (int i = 1; i <= x; ++i) {int tar;scanf("%d", &tar);color[tar] = 1;}for (int i = 1; i <= y; ++i) {int tar;scanf("%d", &tar);color[tar] = 0;}if (solve()) printf("YES\n");else printf("NO\n");for (int i = 1; i <= n; ++i)g[i].clear();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的HDU Problem - 5971 Wrestling Match（染色）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。