题解：P11117 [ROI 2024] 交互式通道 (Day 2)
首先，判掉最后的图不合法的情况。
然后发现，黑黑、白白边可以删除，这些边在最后一定合法。
因此原图变成二分图。
要求：白色边不能被染黑。
最大的问题是：每个白点被染黑后再染白这段时间内不能存在白边，这是唯一的限制。
-
观察：黑点被染黑后不会再被染白。白点至多被染黑，染白一次。
感性理解：
黑点染白只会让已经染好的黑边失效，相当于没有染这个黑点，不如延后当前黑点被染黑的时间。
白点周围全是黑点，它染黑的时候周围黑点该黑的肯定得黑，由于黑点不会被染白，所以白点可以等到相邻黑点该染黑的染黑完后再染黑，使边颜色改变，接着马上染白，避免影响其余点染色。
根据观察的感性理解，可以发现白点的染黑、染白操作总是连续的。
这个问题很像 2-SAT。考虑建图：
-
对于白边，白点必须在黑点之前被染成过黑色，不然这条边直接黑了，黑点必须重新染白。
-
对于黑边，黑点必须在白点之前被染成黑色，不然白点都染回白色了你这条边还是白的。
于是用有向边表示点与点的染色顺序限制，合法条件就是不存在环。使用 Tarjan 判环，Topo 排序输出方案即可。
这是线性的。
code
#include <stdint.h>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
namespace fast_IO{
#define ld cin
#define jyt cout
}using namespace fast_IO;
#define REP(i, l, r) for (int i = l; i <= r; ++i)
#define PER(i, l, r) for (int i = l; i >= r; --i)
#define clean(name) memset(name, 0, sizeof(name))
#define memst(name, n) memset(name, 0, (n + 1) * sizeof(name[0]))
// #define int long long
constexpr int N = 2e5 + 7;
constexpr int inf = 1e9 + 7;
constexpr int P = 998244353;
namespace JoKing {
int n, m, q, a[N], dfn[N], low[N], deg[N], dc, stc[N], top, vis[N]; bool flag = true;
struct Edge {int u, v, w;} e[N];
vector<int> G[N];
inline void Tarjan(int x) {
dfn[x] = low[x] = ++dc, stc[++top] = x, vis[x] = 1;
for (int v : G[x]) {
if (!dfn[v]) Tarjan(v), low[x] = min(low[x], low[v]);
else if (vis[v]) low[x] = min(low[x], dfn[v]);
if (!flag) return;
}
if (dfn[x] == low[x]) {
if (stc[top] != x) flag = false;
else vis[x] = 0, --top;
}
}
signed main() {
ld >> n >> m, q = 0, flag = true;
REP(i, 1, m) ld >> e[i].u >> e[i].v >> e[i].w;
REP(i, 1, n) ld >> a[i];
REP(i, 1, m) if (a[e[i].u] ^ e[i].w && a[e[i].v] ^ e[i].w) return jyt << "NO\n";
REP(i, 1, m) if (a[e[i].u] ^ a[e[i].v]) e[++q] = e[i]; m = q;
REP(i, 1, m) {
if (a[e[i].u]) swap(e[i].u, e[i].v);
if (e[i].w) {
G[e[i].v].emplace_back(e[i].u), ++deg[e[i].u];
} else {
G[e[i].u].emplace_back(e[i].v), ++deg[e[i].v];
}
}
REP(i, 1, n) if (!dfn[i]) {Tarjan(i); if (!flag) break;}
if (!flag) {
jyt << "NO\n";
} else {
jyt << "YES\n";
queue<int> Q; int tot = 0;
REP(i, 1, n) if (tot += (a[i] ? 1 : 2), !deg[i]) Q.emplace(i);
jyt << tot << '\n';
while (!Q.empty()) {
int x = Q.front(); Q.pop();
if (!a[x]) jyt << x << ' ' << '1' << '\n' << x << ' ' << '0' << '\n';
else jyt << x << ' ' << 1 << '\n';
for (int v : G[x]) if (!(--deg[v])) Q.emplace(v);
}
}
REP(i, 1, n) dfn[i] = low[i] = vis[i] = deg[i] = 0, G[i].clear(); dc = top = 0;
return 0;
}
}
signed main() {
#ifdef WYY
freopen("files/code.in", "r", stdin);
freopen("files/code.out", "w", stdout);
freopen("files/code.err", "w", stderr);
#else
// freopen("yui.in", "r", stdin);
// freopen("yui.out", "w", stdout);
#endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T = 0; ld >> T;
while (T--) JoKing::main();
return 0;
}