狗狗40题搞完纪念 » 1035

1035.cpp

```#include <vector>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int MAXN = 128;

struct DisjointSet {
int p[MAXN], a[MAXN], b[MAXN];

void init(int n) {
for (int i = 1; i <= n; ++i) {
p[i] = i;
a[i] = 1;
b[i] = 0;
}
}

int root(int i) {
if (i > 0) {
return i == p[i] ? i : (p[i] = root(p[i]));
} else {
return -i == p[-i] ? i : -(p[-i] = root(p[-i]));
}
}

int _istrue(int i, int j) {
if (i < 0) {
return _isfalse(-i, j);
} else if (j < 0) {
return _isfalse(i, -j);
} else if (i != j) {
p[j] = i;
a[i] += a[j];
b[i] += b[j];
return 1;
} else {
return 0;
}
}

int _isfalse(int i, int j) {
if (i < 0) {
return _istrue(-i, j);
} else if (j < 0) {
return _istrue(i, -j);
} else if (i != j) {
p[j] = -i;
a[i] += b[j];
b[i] += a[j];
return 1;
} else {
return -1;
}
}

int istrue(int i, int j) {
return _istrue(root(i), root(j));
}

int isfalse(int i, int j) {
return _isfalse(root(i), root(j));
}
} ds;

int r[MAXN], s[MAXN], t[MAXN];

struct F {
const int y;
F(int y) : y(y) { }
bool operator()(int x) const { return ds.root(x) != y; }
};

int main() {
int re, n, m, a, p, ans[MAXN];
bool flg, e[MAXN], dp[MAXN][MAXN];

scanf("%d", &re);
for (int ri = 1; ri <= re; ++ri) {
scanf("%d", &n);
ds.init(n);
flg = true;
for (int i = 1; i <= n; ++i) {
ans[i] = i;
fill(e + 1, e + 1 + n, false);
while (scanf("%d", &a) != EOF && a > 0) {
e[a] = true;
}
for (int j = 1; j <= n; ++j) {
if (!e[j] && j != i) {
flg &= ds.isfalse(i, j) != -1;
}
}
}

if (ri > 1) {
puts("");
}
if (!flg) {
puts("No solution");
continue;
}

m = 0;
for (int i = 1; i <= n; ++i) {
if (ds.root(i) == i) {
++m;
r[m] = i;
s[m] = ds.a[i];
t[m] = ds.b[i];
// printf("%d: %d + %d\n", r[m], s[m], t[m]);
}
}
dp[0][0] = true;
fill(dp[0] + 1, dp[0] + 1 + n, false);
for (int i = 1; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
dp[i][j] = (j >= s[i] && dp[i - 1][j - s[i]]) || (j >= t[i] && dp[i - 1][j - t[i]]);
}
}

a = 0;
for (int j = 0; j <= n; ++j) {
if (dp[m][j] && abs(n - 2 * j) < abs(n - 2 * a)) {
a = j;
}
}

p = n;
for (int i = m; i > 0; --i) {
if (a >= s[i] && dp[i - 1][a - s[i]]) {
a -= s[i];
p = partition(ans + 1, ans + 1 + p, F(-r[i])) - ans - 1;
} else {
a -= t[i];
p = partition(ans + 1, ans + 1 + p, F(r[i])) - ans - 1;
}
}

printf("%d", p);
for (int i = 1; i <= p; ++i) {
printf(" %d", ans[i]);
}
printf("\n%d", n - p);
for (int i = p + 1; i <= n; ++i) {
printf(" %d", ans[i]);
}
puts("");
}

return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//338 	2010-06-28 04:28:31 	Accepted 	1035 	C++ 	110 	180 	anotherpeg 	Source
```