UVA - 1627 Team them up!——二分图染色+01背包

UVA - 1627 Team them up!——二分图染色+01背包

这题不是普通的01背包模型，是一个判断可行空间的01背包，是uva323的缩水版

#include #include #include #include #include using namespace std;const int maxn = 110;const int maxm = 220;int g[maxn][maxn];vector G[maxn];int vis[maxn];int link_cnt;vector link[maxn];int x[maxn], y[maxn], sub[maxn];bool dp[maxn][maxm];vector path[maxn][maxm];bool dfs(int u) { for (unsigned int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if (vis[v]) { if (vis[v] == -vis[u]) continue; else return false; } else { vis[v] = -vis[u]; link[link_cnt].push_back(v); if (!dfs(v)) return false; } } return true;}int main() { int T; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { int n; scanf("%d", &n); memset(g, 0, sizeof(g)); for (int i = 1; i <= n; i++) G[i].clear(), link[i].clear(); for (int i = 1; i <= n; i++) { int x; while (~scanf("%d", &x) && x) g[i][x] = 1; } for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { if (g[i][j] && g[j][i]) continue; G[i].push_back(j); G[j].push_back(i); } } memset(vis, 0, sizeof(vis)); bool ok = true; link_cnt = 0; for (int i = 1; i <= n; i++) { if (vis[i]) continue; ++link_cnt; vis[i] = 1; link[link_cnt].push_back(i); if (!dfs(i)) { ok = false; break; } } if (ok) { memset(x, 0, sizeof(x)); memset(y, 0, sizeof(y)); for (int i = 1; i <= link_cnt; i++) { for (unsigned int j = 0; j < link[i].size(); j++) { int t = link[i][j]; if (vis[t] == 1) x[i]++; else if (vis[t] == -1) y[i]++; } } int m = link_cnt; for (int i = 1; i <= m; i++) sub[i] = x[i] - y[i]; for (int i = 0; i <= m; i++) { for (int j = 0; j <= 205; j++) { dp[i][j] = false; path[i][j].clear(); } } dp[0][100] = true; for (int i = 0; i <= m; i++) { for (int j = 0; j < 200; j++) { if (!dp[i][j]) continue; if (j + sub[i + 1] < 0 || j + sub[i + 1] > 200) continue; if (j - sub[i + 1] < 0 || j - sub[i + 1] > 200) continue; dp[i + 1][j + sub[i + 1]] = true; path[i + 1][j + sub[i + 1]] = path[i][j]; path[i + 1][j + sub[i + 1]].push_back(1); dp[i + 1][j - sub[i + 1]] = true; path[i + 1][j - sub[i + 1]] = path[i][j]; path[i + 1][j - sub[i + 1]].push_back(-1); } } int pos = 0; for(; !dp[m][100+pos] && !dp[m][100-pos]; pos++); int state = dp[m][100+pos] ? 100+pos : 100-pos; int a[maxn], cnta = 0, b[maxn], cntb = 0; for (unsigned int i = 0; i < path[m][state].size(); i++) { int x = path[m][state][i]; for (unsigned int j = 0; j < link[i + 1].size(); j++) { int t = link[i+1][j]; if (x * vis[t] == 1) { a[++cnta] = t; } else if (x * vis[t] == -1) { b[++cntb] = t; } } } //if (kase != 1) printf("\n"); printf("%d", cnta); sort(a + 1, a + cnta + 1); for (int i = 1; i <= cnta; i++) printf(" %d", a[i]); printf("\n"); sort(b + 1, b + cntb + 1); printf("%d", cntb); for (int i = 1; i <= cntb; i++) printf(" %d", b[i]); printf("\n"); } else printf("No solution\n"); cout << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。