[UVA][dp] 11331 - The Joys of Farming
Problem I: The Joys of Farming
Farmer John owns b bulls and c cows.
He also owns b+c fields where each field can hold either one cow or one bull.
The fields are located in an area with many hills, so for some pairs of fields the
animals in those fields cannot see each other.
Unfortunately, his bulls really do not like each other, and neither do his cows.
To avoid making any animal angry, John would like to assign the animals
to fields such that no two bulls can see each other and no two cows can see each other.
Help determine if John can assign his bulls and cows in such a manner.
Input: The first line of input contains n, the number of examples. The first line of each example contains integers b, c, and a where 0 ≤ b,c ≤ 1000 are, respectively, the number of bulls and cows and 0 ≤ a ≤ 20,000. The next a lines of input each contains two numbers u and v which indicates that animals placed in fields u and v can see each other. Fields are numbered from 1 to b+c.
Output: For each example, output a single line containing yes if peace can be ensured, and no if it can not.
Sample input
2 2 2 4 1 2 2 3 3 4 4 1 3 1 2 1 2 3 4
Output for sample input
yes no
Martin Müller
題目描述：
有 b 隻公牛 c 隻母牛，農場主人有 b+c 塊土地，土地分布為丘陵地，
因此有些地點無法看到其他地點。公牛之間會互看不順眼，母牛間也是。
每塊土地上只能放置一頭牛。
農場主人知道土地間的看得到的訊息。
問有沒有辦法放置這 b+c 頭牛，且不會使得牛群互看不順眼的情況發生。
題目解法：
對於一張連通圖來說，很明顯地是一道二分圖染色問題。
但是題目可能有很多連通子圖，那麼需要稍微做點 DP。
因此會得到每個連通子圖的兩個權重 (w1, w2)。
如果二分圖染色失敗，則答案一定為 no。
對於所有 (w1, w2) 著手 dp 背包問題，稍微改變的是 w1 和 w2 一定要選擇一個放入背包。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[2005];
int color[2005], visited[2005];
int err, black, white;
void dfs(int nd) {
if(err)
return;
visited[nd] = 1;
if(color[nd] == 0) black++;
else white++;
int i;
for(i = 0; i < g[nd].size(); i++) {
if(visited[g[nd][i]] && color[nd] == color[g[nd][i]])
err = 1;
else if(visited[g[nd][i]] == 0){
color[g[nd][i]] = !color[nd];
dfs(g[nd][i]);
}
}
}
int main() {
int testcase, b, c, n;
int i, j, k, x, y;
int w1[2005], w2[2005];
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d %d", &b, &c, &n);
for(i = b+c; i >= 1; i--)
g[i].clear();
memset(color, 0, sizeof(color));
memset(visited, 0, sizeof(visited));
while(n--) {
scanf("%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
err = 0;
for(i = b+c, n = 0; i >= 1; i--) {
if(visited[i] == 0) {
black = white = 0;
dfs(i);
w1[n] = black;
w2[n] = white;
n++;
}
}
if(err) {
puts("no");
continue;
}
int dp[2][2005] = {}, roll = 0;
dp[0][0] = 1;
b = min(b, c);
for(i = 0; i < n; i++) {
memset(dp[!roll], 0, sizeof(dp[!roll]));
int ww1 = w1[i], ww2 = w2[i];
int mn = min(ww1, ww2);
for(j = b; j >= mn; j--) {
if(j-ww1 >= 0) dp[!roll][j] |= dp[roll][j-ww1];
if(j-ww2 >= 0) dp[!roll][j] |= dp[roll][j-ww2];
}
roll = !roll;
}
puts(dp[roll][b] ? "yes" : "no");
}
return 0;
}
Thank...