加载中…POJ PKU 1112 Team Them Up 二分图染色 DP 模拟
(2011-06-28 22:02:20)
标签：
pojpku1112teamthemup二分图染色dp模拟it |
分类： 图论 |
题目描述：
col[id]
= co;
gp[gpid
* 2 + co].push_back(id);
for(int
i = 0; i < n; i++)
if (jeo[id][i]
&& col[i] == -1)
judge(i, co ^ 1, gpid);
if (l
== 0 && r == 0) return;
for(int
i = 0; i < gp[path[l][r][pos]].size(); i++)
ans[pos].push_back(gp[path[l][r][pos]][i]);
getans(pre[l][r][0], pre[l][r][1], pos);
while(scanf("%d", &n) !=
EOF)
{
memset(g, 0, sizeof(g));
memset(jeo, 0,
sizeof(jeo));
memset(col, -1,
sizeof(col));
memset(dp, -1,
sizeof(dp));memset(path, -1, sizeof(path));
memset(pre, -1,
sizeof(pre));
ans[0].clear();
ans[1].clear();
gpnum = 0;
for(int i = 0; i
< n + n; i++) gp[i].clear();
for(int i = 0; i
< n; i++)
{
int in; while(scanf("%d", &in)
&& in)
g[i][in -
1] = 1;
}
for(int i = 0; i
< n; i++)
for(int j = 0; j < n; j++)
if (i != j
&& !(g[i][j]
&& g[j][i])) jeo[i][j] = jeo[j][i]
= 1;
for(int i = 0; i
< n; i++)//染色
if (col[i] == -1) judge(i, 0, gpnum++);
bool flag = true;
for(int i = 0; i
< n; i++)for(int j = 0; j < n;
j++)
if (jeo[i][j] &&
col[i] == col[j]) flag = false;
if (!flag)
{
printf("No solution\n");
continue;
}
int sum = 0; dp[0][0] =
1;
for(int i = 0; i
< gpnum; i++)
{
sum += gp[i * 2].size() + gp[i * 2 +
1].size();
for(int j = sum, k = sum - j; j >=
0; j--)
for(int t =
0; t < 2; t++)
{
int A = i * 2 + t, B = i * 2 +
(t ^ 1);
if (dp[j][k] == -1
&& j -
(int)gp[A].size() >= 0
&& k - (int)gp[B].size()
>= 0
&& dp[j -
gp[A].size()][k - gp[B].size()] == 1)
{
dp[j][k] = 1;
path[j][k][0] = A;
path[j][k][1] = B;
pre[j][k][0] = j - gp[A].size();
pre[j][k][1] = k - gp[B].size();
}
}
}
int mmin = n, l, r;
for(int i = 1; i
< n; i++)
if (i >= (n - i)
&& dp[i][n - i] == 1
&& i + i - n <
mmin)
{
mmin = i +
i - n;
l = i, r =
n - i;
}
getans(l, r, 0); getans(l, r,
1);
for(int i = 0; i
< 2; i++)
{
printf("%d", ans[i].size());
for(int j = 0; j < ans[i].size();
j++)
printf("
%d", ans[i][j] + 1);
printf("\n");
}
}
return
0;
n个人，告诉你每个人是否认识其他的人，让你把这n个人分成两组：
1. 每组至少一个人
2. 在同一组的人都互相认识
3. 这两组人数的差值最小
问：是否存在解
存在的话，输出分配方案。
解题报告：
首先，每组的所有人都要互相认识。
如果我们这样建无向图：连接i，j表示i和j不是互相认识，这样，如果ij之间没有边，就表示他们互相认识，那么，题目的要求就是分成两组，每组内部没有边（互相认识），即2分图。
这样，构图之后，染色，如果一边的两个节点颜色一样，就不是2分图，无解。
如果G是二分图，计算每个连通分支中分成属于x[i]，y[i]2个组的人数（i表示连通分支）；
下面是差值最小：
dp[j][k] = 1表示一组j人，另一组有k人可以成立。
那么如果枚举到第i个分支，则当前人数总和sum = x[0]+x[1] + .. + x[i] + y[0] + .. +
y[i]
if (dp[j - x[i]][k - y[i]] == 1
&& dp[j][k] == 0) dp[j][k] =
1;
if (dp[j - y[i]][k - x[i]] == 1
&& dp[j][k] == 0) dp[j][k] =
1;
代码如下：
#include<iostream>
#include<vector>
using namespace std;
#define siz 101
int n, g[siz][siz], jeo[siz][siz], col[siz], gpnum;
int dp[siz][siz], path[siz][siz][2], pre[siz][siz][2];
vector<int> gp[siz * 2],
ans[2];
void judge(int id, int co, int gpid)
{
}
void getans(int l, int r, int pos)
{
}
int main()
{
}
喜欢
0
赠金笔
后一篇：一个错误。。。