自动搬运

查看原文

来自洛谷，原作者为

	流水行船CCD 果 果 没 有 特 权 ~

搬运于2025-08-24 23:04:22，当前版本为作者最后更新于2025-06-30 21:09:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，判掉最后的图不合法的情况。

然后发现，黑黑、白白边可以删除，这些边在最后一定合法。

因此原图变成二分图。

要求：白色边不能被染黑。

最大的问题是：每个白点被染黑后再染白这段时间内不能存在白边，这是唯一的限制。

• 观察：黑点被染黑后不会再被染白。白点至多被染黑，染白一次。

感性理解：

黑点染白只会让已经染好的黑边失效，相当于没有染这个黑点，不如延后当前黑点被染黑的时间。

白点周围全是黑点，它染黑的时候周围黑点该黑的肯定得黑，由于黑点不会被染白，所以白点可以等到相邻黑点该染黑的染黑完后再染黑，使边颜色改变，接着马上染白，避免影响其余点染色。

根据观察的感性理解，可以发现白点的染黑、染白操作总是连续的。

这个问题很像 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;
}