续昨天。
T8
洛谷 P4150 最短路问题
行数很小，考虑使用矩阵。对于一个区间 \([l, r]\)，维护 \(ll_{i, j}, rr_{i, j}, lr_{i, j}\) 分别表示 \((i, l) \rightarrow (j, l)\)、\((i, r) \rightarrow (j, r)\)、\((i, l) \rightarrow (j, r)\) 的最小代价。为了转移方便，再维护 \(lm_{i, j}\) 和 \(rm_{i, j}\) 表示从 \((i, l)\) 出发，先走到区间中点这一列上 \(mid\) 或其右边再走到 \((j, mid)\) 的最小代价和从 \((i, r)\) 出发，先走到 \(mid\) 或其左边再走到 \((j, mid)\) 的最小代价。使用线段树维护，合并两个儿子时枚举一个 \(k \in [1, 6]\)，先转移 \(lm\) 和 \(rm\)，再用 \(lm\) 和 \(rm\) 来转移 \(ll, rr, lr\)。画个图大概就会转移了。
接下来统计答案。我们发现最短路与询问的两列一定只会有 \(\le 6\) 个交点，包括询问的两个点。所以我们直接暴力枚举剩下的四个交点，如果有重复的就当是这两个交点并作一个。我们把两个询问左边、中间和右边的三个矩阵搞出来，然后随便算一下就好了。发现最短路要么横穿整个区间一次，要么横穿三次。两种情况要分别考虑，不然会被 hack。在草稿纸上画个图很容易就会算了。会出现算重的点，减掉即可。
代码
#include <iostream>
#define int long long
using namespace std;
const int inf = 2147483647;
int n;
struct node {
int ll[6][6], rr[6][6];
int lm[6][6], rm[6][6];
int lr[6][6];
} T[400005];
int A[7][100005];
node operator+(node a, node b) {
node c;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
c.ll[i][j] = c.rr[i][j] = c.lm[i][j] = c.rm[i][j] = c.lr[i][j] = inf;
for (int k = 0; k < 6; k++) {
c.lm[i][j] = min(c.lm[i][j], a.lr[i][k] + b.ll[k][j]);
c.rm[i][j] = min(c.rm[i][j], a.rr[k][j] + b.lr[k][i]);
}
}
}
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
for (int k = 0; k < 6; k++) {
c.ll[i][j] = min(c.ll[i][j], min(a.ll[i][j], c.lm[i][k] + a.lr[j][k]));
c.rr[i][j] = min(c.rr[i][j], min(b.rr[i][j], c.rm[i][k] + b.lr[k][j]));
c.lr[i][j] = min(c.lr[i][j], min(a.lr[i][k] + b.lr[k][j], c.lm[i][k] + c.rm[j][k]));
}
}
}
return c;
}
void gen(int o, int x) {
for (int i = 0; i < 6; i++) {
for (int j = i; j < 6; j++) {
T[o].ll[i][j] = 0;
for (int k = i; k <= j; k++)
T[o].ll[i][j] += A[k][x];
T[o].ll[j][i] = T[o].ll[i][j];
T[o].rr[i][j] = T[o].rr[j][i] = T[o].ll[i][j];
T[o].rm[i][j] = T[o].rm[j][i] = T[o].ll[i][j];
T[o].lm[i][j] = T[o].lm[j][i] = T[o].ll[i][j];
T[o].lr[i][j] = T[o].lr[j][i] = T[o].ll[i][j];
}
}
}
struct Segment_Tree {
void Build(int o, int l, int r) {
if (l == r) {
gen(o, l);
return;
}
int mid = (l + r) >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
T[o] = T[o << 1] + T[o << 1 | 1];
}
void Change(int o, int l, int r, int x, int y, int v) {
if (l == r) {
A[x][y] = v;
gen(o, l);
return;
}
int mid = (l + r) >> 1;
if (y <= mid)
Change(o << 1, l, mid, x, y, v);
else
Change(o << 1 | 1, mid + 1, r, x, y, v);
T[o] = T[o << 1] + T[o << 1 | 1];
}
node Query(int o, int l, int r, int L, int R) {
if (L > R)
return T[0];
if (L <= l && r <= R)
return T[o];
int mid = (l + r) >> 1;
if (R <= mid)
return Query(o << 1, l, mid, L, R);
if (L > mid)
return Query(o << 1 | 1, mid + 1, r, L, R);
return Query(o << 1, l, mid, L, R) + Query(o << 1 | 1, mid + 1, r, L, R);
}
} seg;
int Query(int x1, int y1, int x2, int y2) {
if (y1 > y2)
swap(y1, y2), swap(x1, x2);
int ret = inf;
node x, y, z;
x = seg.Query(1, 1, n, 1, y1);
y = seg.Query(1, 1, n, y1, y2);
z = seg.Query(1, 1, n, y2, n);
for (int a = 0; a < 6; a++) {
for (int b = 0; b < 6; b++) {
for (int c = 0; c < 6; c++) {
for (int d = 0; d < 6; d++) {
ret = min(ret, y.ll[x1][a] + x.rr[a][b] + y.lr[b][c] + z.ll[c][d] + y.rr[d][x2] - A[a][y1] - A[b][y1] - A[c][y2] - A[d][y2]);
ret = min(ret, y.lr[x1][d] + z.ll[d][c] + y.lr[a][c] + x.rr[a][b] + y.lr[b][x2] - A[a][y1] - A[b][y1] - A[c][y2] - A[d][y2]);
}
}
}
}
return ret;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++)
T[0].ll[i][j] = T[0].lm[i][j] = T[0].rm[i][j] = T[0].lr[i][j] = T[0].rr[i][j] = inf;
}
for (int i = 0; i < 6; i++) {
for (int j = 1; j <= n; j++)
cin >> A[i][j];
}
seg.Build(1, 1, n);
int q;
cin >> q;
while (q--) {
int op, x1, y1, x2, y2, v;
cin >> op;
if (op == 2) {
cin >> x1 >> y1 >> x2 >> y2;
--x1, --x2;
cout << Query(x1, y1, x2, y2) << "\n";
} else {
cin >> x1 >> y1 >> v;
--x1;
seg.Change(1, 1, n, x1, y1, v);
}
}
return 0;
}
T9
洛谷 P4217 产品销售
首先考虑费用流建模，从左往右依次增广。然后发现增广路一共只有两种，而且往左增广时如果有往右增广时出现的反向边就一定不会使用原来的边。所以三棵线段树分别维护往左到达每个点的代价，往右到达每个点的代价以及每条往左的边的剩余流量（如果这条边上没有反向边就是 \(+\infty\)）。往右走时先把右边点的代价减去这条边权，再根据这条边是否被用来往右增广过对左边点的代价进行增加或减少。如果一次增广流满了一条反向边，就把这条边左边点的代价和这条边的剩余流量都改掉。具体可以参考我在洛谷写的题解。
代码
#include <iostream>
#define int long long
using namespace std;
const int inf = 21474836470000;
int d[100005], u[100005], p[100005], m[100005], c[100005], pre[100005];
int n;
struct Segment_Tree1 {
int mn[400005], mnp[400005];
int tg[400005];
inline void tag(int x, int y) { mn[x] += y, tg[x] += y; }
inline void pushdown(int o) {
if (!tg[o])
return;
tag(o << 1, tg[o]);
tag(o << 1 | 1, tg[o]);
tg[o] = 0;
}
inline void pushup(int o) {
if (mn[o << 1] < mn[o << 1 | 1])
mn[o] = mn[o << 1], mnp[o] = mnp[o << 1];
else
mn[o] = mn[o << 1 | 1], mnp[o] = mnp[o << 1 | 1];
}
void Build(int o, int l, int r) {
if (l == r) {
mn[o] = p[l];
mnp[o] = r;
return;
}
int mid = (l + r) >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
pushup(o);
}
void Add(int o, int l, int r, int L, int R, int v) {
if (L > R)
return;
if (L <= l && r <= R) {
tag(o, v);
return;
}
pushdown(o);
int mid = (l + r) >> 1;
if (L <= mid)
Add(o << 1, l, mid, L, R, v);
if (R > mid)
Add(o << 1 | 1, mid + 1, r, L, R, v);
pushup(o);
}
int Query(int o, int l, int r, int L, int R, int& p) {
if (L > R) {
p = 0;
return inf;
}
if (L <= l && r <= R) {
p = mnp[o];
return mn[o];
}
pushdown(o);
int mid = (l + r) >> 1;
if (R <= mid)
return Query(o << 1, l, mid, L, R, p);
if (L > mid)
return Query(o << 1 | 1, mid + 1, r, L, R, p);
int lp, lv = Query(o << 1, l, mid, L, R, lp);
int rp, rv = Query(o << 1 | 1, mid + 1, r, L, R, rp);
if (lv > rv)
swap(lv, rv), swap(lp, rp);
return p = lp, lv;
}
} seg1, seg2, seg3;
void Deal(int o, int l, int r) {
if (seg3.mn[o] != 0)
return;
if (l == r) {
seg3.mn[o] = inf;
if (pre[l + 1])
seg2.Add(1, 1, n, 1, l, c[l] + m[r]);
return;
}
seg3.pushdown(o);
int mid = (l + r) >> 1;
if (seg3.mn[o << 1] == 0)
Deal(o << 1, l, mid);
if (seg3.mn[o << 1 | 1] == 0)
Deal(o << 1 | 1, mid + 1, r);
seg3.pushup(o);
}
void Deal(int o, int l, int r, int L, int R) {
if (!L || !R || L > R)
return;
if (L <= l && r <= R) {
Deal(o, l, r);
return;
}
seg3.pushdown(o);
int mid = (l + r) >> 1;
if (L <= mid)
Deal(o << 1, l, mid, L, R);
if (R > mid)
Deal(o << 1 | 1, mid + 1, r, L, R);
seg3.pushup(o);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> d[i];
for (int i = 1; i <= n; i++) cin >> u[i];
for (int i = 1; i <= n; i++) cin >> p[i];
seg1.Build(1, 1, n), seg2.Build(1, 1, n);
for (int i = 1; i < n; i++) cin >> m[i];
for (int i = 1; i < n; i++) cin >> c[i], seg1.Add(1, 1, n, i + 1, n, c[i]);
int ans = 0;
for (int i = 1; i <= n; i++) {
pre[i] += pre[i - 1];
seg1.Add(1, 1, n, i, n, -c[i - 1]);
if (pre[i])
seg2.Add(1, 1, n, 1, i - 1, -c[i - 1]);
else
seg2.Add(1, 1, n, 1, i - 1, m[i - 1]);
Deal(1, 1, n - 1, i - 1, i - 1);
while (d[i]) {
int x;
int pl, ml = seg2.Query(1, 1, n, 1, i - 1, pl);
int pr, mr = seg1.Query(1, 1, n, i, n, pr);
if (mr < ml) {
int f = min(d[i], u[pr]);
d[i] -= f, u[pr] -= f;
ans += f * mr;
pre[i]++, pre[pr + 1]--;
seg3.Add(1, 1, n - 1, i, pr - 1, f);
if (!u[pr]) {
seg1.Add(1, 1, n, pr, pr, inf);
seg2.Add(1, 1, n, pr, pr, inf);
}
} else {
int x;
int f = min(seg3.Query(1, 1, n - 1, pl, i - 1, x), min(u[pl], d[i]));
d[i] -= f, u[pl] -= f;
seg3.Add(1, 1, n - 1, pl, i - 1, -f);
Deal(1, 1, n - 1, pl, i - 1);
ans += f * ml;
if (!u[pl]) {
seg1.Add(1, 1, n, pl, pl, inf);
seg2.Add(1, 1, n, pl, pl, inf);
}
}
}
}
cout << ans << "\n";
return 0;
}
T10
洛谷 P2414 阿狸的打字机
建 fail 树，问题变为询问从某字符串的每个前缀往上跳能到达另一个字符串总共多少次。等价于询问另一个字符串的子树中有多少某字符串的前缀。在原先的 trie 树上 dfs，进入一个节点就把 fail 树上的对应节点加一下，离开时减一下，这样在遇到一个字符串的结尾时 fail 树上一定只有这个字符串的所有前缀的位置有值。所以直接把所有以这个字符串为文本串的询问都回答掉即可。点加子树和使用 dfn 树状数组维护。
代码
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
#define lowbit(x) ((x) & -(x))
using namespace std;
int ep[100005], n;
int mp[1000005];
int cur, ncnt;
int son[100005][26];
int rec[100005][26];
int fail[2000005];
int head[2000005], nxt[2000005], to[2000005], ecnt;
vector<pair<int, int> > vec[2000005];
int fa[2000005];
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
queue<int> q;
void Build() {
for (int i = 0; i < 26; i++)
if (son[0][i])
q.push(son[0][i]), fail[son[0][i]] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = 0; i < 26; i++) {
if (son[x][i])
fail[son[x][i]] = son[fail[x]][i], q.push(son[x][i]);
else
son[x][i] = son[fail[x]][i];
}
}
for (int i = 1; i <= ncnt; i++) add(fail[i] + 1, i + 1);
}
int L[2000005], R[2000005], ncnt2;
void dfs1(int x) {
L[x] = ++ncnt2;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
dfs1(v);
}
R[x] = ncnt2;
}
int ans[100005];
struct BIT {
int bit[2000005];
void add(int x, int v) { for (; x <= 2000000; x += lowbit(x)) bit[x] += v; }
int query(int x) {
int ret = 0;
for (; x; x -= lowbit(x)) ret += bit[x];
return ret;
}
int query(int l, int r) { return query(r) - query(l - 1); }
} bit;
void dfs2(int x) {
bit.add(L[x + 1], 1);
if (mp[x + 1]) {
for (auto v : vec[x + 1])
ans[v.first] = bit.query(L[ep[v.second]], R[ep[v.second]]);
}
for (int i = 0; i < 26; i++) {
if (rec[x][i])
dfs2(rec[x][i]);
}
bit.add(L[x + 1], -1);
}
int main() {
string str;
cin >> str;
for (int i = 0; i < (int)str.size(); i++) {
if (str[i] == 'P')
ep[++n] = cur + 1, mp[cur + 1] = n;
else if (str[i] == 'B')
cur = fa[cur];
else {
int x = str[i] - 'a';
if (!son[cur][x])
fa[son[cur][x] = ++ncnt] = cur;
cur = son[cur][x];
}
}
memcpy(rec, son, sizeof son);
Build();
dfs1(1);
int m;
cin >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
vec[ep[y]].emplace_back(make_pair(i, x));
}
dfs2(0);
for (int i = 1; i <= m; i++) cout << ans[i] << "\n";
return 0;
}
T11
洛谷 P1973 NOI 嘉年华
首先将时间离散化，记 \(f[i][j]\) 表示前 \(i\) 个时间点，分了 \(j\) 个活动给第一场，此时第二场最多多少活动。转移就枚举上一个断点，把这一段的所有活动都分给第一场或第二场。考虑如何钦定选择一个活动。我们记 \(s[i][j]\) 表示强制 \([i, j]\) 这段区间内无断点时的答案，也就是较少的场最多多少个活动。可以通过暴力枚举这段时间之前和之后分别选了几个活动来计算。为此还要求 \(g[i][j]\) 表示后 \(i\) 个时间点，分了 \(j\) 个给第一场时第二场最多多少。这样复杂度是 \(O(n^4)\)，但是可以艹过去。这题有一个单调性，就是计算 \(s\) 时可以只枚举一边选的个数，另一边可以通过根据单调性来只往一个方向移动。这样复杂度就是 \(O(n^3)\) 的。但是我写挂了，所以代码是 \(O(n^4)\) 的。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <map>
#define int long long
using namespace std;
int l[2005], r[2005], d[405], dcnt;
map<int, int> mp;
int n;
int c[405][405], s[405][405];
int f[405][405], g[405][405];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
l[i] = x, r[i] = x + y - 1;
d[++dcnt] = l[i], d[++dcnt] = r[i];
}
sort(d + 1, d + dcnt + 1);
for (int i = 1; i <= dcnt; i++) mp[d[i]] = mp[d[i - 1]] + (d[i] != d[i - 1]);
for (int i = 1; i <= n; i++) l[i] = mp[l[i]] + 1, r[i] = mp[r[i]] + 1;
int T = mp[d[dcnt]] + 2;
for (int i = 1; i <= T; i++) {
for (int j = i; j <= T; j++) {
for (int k = 1; k <= n; k++)
c[i][j] += (i <= l[k] && r[k] <= j);
}
}
for (int i = 0; i <= T + 1; i++) {
for (int j = 0; j <= n; j++)
f[i][j] = g[i][j] = -2147483647;
}
memset(s, 128, sizeof s);
f[0][0] = g[T + 1][0] = 0;
for (int i = 1; i <= T; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 1; k <= i; k++) {
f[i][j] = max(f[i][j], f[k - 1][j] + c[k][i]);
if (c[k][i] <= j)
f[i][j] = max(f[i][j], f[k - 1][j - c[k][i]]);
}
}
}
int ans = 0;
for (int i = 0; i <= n; i++) ans = max(ans, min(f[T][i], i));
cout << ans << "\n";
for (int i = T; i; i--) {
for (int j = 0; j <= n; j++) {
for (int k = i; k <= T; k++) {
g[i][j] = max(g[i][j], g[k + 1][j] + c[i][k]);
if (c[i][k] <= j)
g[i][j] = max(g[i][j], g[k + 1][j - c[i][k]]);
}
}
}
for (int i = 1; i <= T; i++) {
for (int j = i; j <= T; j++) {
for (int a = 0; a <= c[1][i - 1]; a++) {
for (int b = 0; b <= c[j + 1][T]; b++)
s[i][j] = max(s[i][j], min(a + b + c[i][j], f[i - 1][a] + g[j + 1][b]));
}
}
}
for (int i = 1; i <= n; i++) {
int ans = 0;
for (int j = 1; j <= l[i]; j++) {
for (int k = r[i]; k <= T; k++)
ans = max(ans, s[j][k]);
}
cout << ans << "\n";
}
return 0;
}
T12
洛谷 P1971 兔兔与蛋蛋游戏
首先发现空格不会移动到之前已经走过的位置。因为如果要回到原位，一定是移动了偶数步。最后要回去的时候一定是移动了奇数步，所以一开始操作的人和此时操作的人一定不同。由于这次操作的人不能移动一开始操作的人留在原位的棋子，所以不可能回到原位。这样就可以把空格的移动视为一条路径，路径上黑白交替。由于起点走到白格，我们将起点视为黑格。这样就变成了一个二分图博弈。
二分图博弈：
两个玩家，一张二分图，一个棋子。玩家轮流操作，将棋子沿图中的边移向另一个节点。不能经过已经走过的节点，无法移动者负。
结论：若开始时棋子在最大匹配的必须点上，则先手必胜。否则后手必胜。
证明：
-
若棋子在必须点上：此时有两种情况，一种是走向必须点，一种是走向非必须点。如果走向必须点的话，后手也必然走向必须点。如果后手可以走到非必须点，则可以将当前点与后手走向的点的匹配状态互换，从而当前点不是必须点。所以后手必然走向必须点，如此循环，最终先手必胜。
-
若棋子在非必须点上：此时无论如何一定走到必须点上，否则出现连接两个非匹配点的边，最大匹配会增加。走向必须点后后手按情况一即必胜。
所以对于这题只需要判断每走完一步之后当前状态是否是先手必胜。如果连续两步走完之后都是先手必胜，则说明是犯了错误。要判断某点是否是必须点只需要把它删掉跑一遍最大匹配，再加上跑一遍，看两遍结果是否相同即可。如果使用网络流需要倒序加点以减小常数，否则无法通过。
代码
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m;
int S, T;
int id[1605][1605];
bool clr[1605];
int lst;
int ans[16005], acnt;
bool win[16005];
int head[16005], nxt[100005], to[100005], res[100005], ecnt;
int cur[16005];
bool vis[16005];
int del[16005], dcnt;
int add(int u, int v, int ww) {
to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, res[ecnt] = ww;
to[++ecnt] = u, nxt[ecnt] = head[v], head[v] = ecnt, res[ecnt] = 0;
return ecnt >> 1;
}
inline int f(int x, int y) { return (x - 1) * m + y; }
int rec[100005];
queue<int> q;
int dep[16005];
bool bfs() {
for (int i = 1; i <= T; i++) dep[i] = -1;
dep[S] = 1;
q.push(S);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (dep[v] == -1 && res[i] && !vis[v]) {
dep[v] = dep[x] + 1;
q.push(v);
}
}
}
return (dep[T] != -1);
}
int dfs(int x, int flow) {
if (x == T)
return flow;
int ret = 0;
for (int i = cur[x]; i && flow; i = nxt[i]) {
cur[x] = i;
int v = to[i];
if (dep[v] == dep[x] + 1 && res[i]) {
int tmp = dfs(v, min(flow, res[i]));
if (tmp) {
res[i] -= tmp;
res[i ^ 1] += tmp;
flow -= tmp;
ret += tmp;
}
}
}
if (!ret)
dep[x] = -1;
return ret;
}
int dinic() {
int ret = 0;
while (bfs()) {
for (int i = 1; i <= T; i++) cur[i] = head[i];
ret += dfs(S, inf);
}
return ret;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ecnt = 1;
cin >> n >> m;
S = n * m + 1, T = S + 1;
for (int i = 1; i <= n; i++) {
string str;
cin >> str;
for (int j = 0; j < m; j++) {
if (str[j] == 'O')
id[S][f(i, j + 1)] = add(S, f(i, j + 1), 1);
else {
if (str[j] == '.')
lst = f(i, j + 1);
clr[f(i, j + 1)] = 1;
// str[i] = 'X';
id[f(i, j + 1)][T] = add(f(i, j + 1), T, 1);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int tmp = f(i, j);
if (i != 1 && clr[tmp - m] ^ clr[tmp]) {
if (clr[tmp])
id[tmp - m][tmp] = add(tmp - m, tmp, 1);
else
id[tmp][tmp - m] = add(tmp, tmp - m, 1);
}
if (i != n && clr[tmp + m] ^ clr[tmp]) {
if (clr[tmp])
id[tmp + m][tmp] = add(tmp + m, tmp, 1);
else
id[tmp][tmp + m] = add(tmp, tmp + m, 1);
}
if (j != 1 && clr[tmp - 1] ^ clr[tmp]) {
if (clr[tmp])
id[tmp - 1][tmp] = add(tmp - 1, tmp, 1);
else
id[tmp][tmp - 1] = add(tmp, tmp - 1, 1);
}
if (j != m && clr[tmp + 1] ^ clr[tmp]) {
if (clr[tmp])
id[tmp + 1][tmp] = add(tmp + 1, tmp, 1);
else
id[tmp][tmp + 1] = add(tmp, tmp + 1, 1);
}
}
}
int q;
cin >> q;
vis[del[0] = lst] = 1;
for (int i = 1; i <= q * 2; i++) {
int x, y;
cin >> x >> y;
int tmp = f(x, y);
del[i] = tmp;
vis[tmp] = 1;
}
lst = dinic();
for (int i = q * 2; ~i; i--) {
vis[del[i]] = 0;
win[i] = (dinic() != 0);
}
for (int i = 0; i < q * 2; i += 2) {
if (win[i] && win[i ^ 1])
ans[++acnt] = (i >> 1) + 1;
}
cout << acnt << "\n";
for (int i = 1; i <= acnt; i++) cout << ans[i] << "\n";
return 0;
}