学术社区 题解

这题通过代码为 tjz 同学的，在此表示衷心感谢。

代码中有详细介绍（主要是 tjz 同学给我讲时的注释）。

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using vi = vector<int>;
using ll = long long;

template <typename T> T read() {
    T x = 0, f = 0;
    char ch = getchar();

    while (!isdigit(ch))
        f |= (ch == '-'), ch = getchar();

    while (isdigit(ch))
        x = x * 10 + (ch - '0'), ch = getchar();

    return f ? -x : x;
}

#define rdi read<int>
#define rdll read<ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back

const int N = 240010;
const int INF = 0x3f3f3f3f;

map<string, int> nam;

int n, m;

struct Edge {
    int to, nxt, f;
} e[N * 10];
int head[N * 4], tot = 1;

void addedge(int x, int y, int f) {
    e[++tot] = {y, head[x], f};
    head[x] = tot;
    e[++tot] = {x, head[y], 0};
    head[y] = tot;
}

struct Mes {
    int fr, to, typ;
    ll id;
} me[N];
bool operator<(const Mes &a, const Mes &b) {
    return make_tuple(a.typ, a.fr, a.to) < make_tuple(b.typ, b.fr, b.to);
}

inline int idd(int x, int typ) {
    return 2 * m + x * 2 - 1 + typ;
}

namespace MF {
int dep[N * 4];
bool bfs(int S, int T) {
    memset(dep, 0, sizeof(int) * (T + 2));
    queue<int> q;
    q.push(S), dep[S] = 1;

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        if (x == T)
            return true;

        for (int i = head[x]; i; i = e[i].nxt) {
            int y = e[i].to;

            if (e[i].f && !dep[y]) {
                dep[y] = dep[x] + 1;
                q.push(y);
            }
        }
    }

    return false;
}
int dfs(int x, int fl, int T) {
    if (x == T)
        return fl;

    int rest = fl;

    for (int i = head[x]; i; i = e[i].nxt) {
        int y = e[i].to;

        if (e[i].f && dep[y] == dep[x] + 1) {
            int tmp = dfs(y, min(fl, e[i].f), T);

            if (tmp < min(fl, e[i].f))
                dep[y] = 0;

            e[i].f -= tmp, e[i ^ 1].f += tmp, rest -= tmp;

            if (!rest)
                break;
        }
    }

    return fl - rest;
}
int mf(int S, int T) {
    int sum = 0;

    while (bfs(S, T))
        sum += dfs(S, INF, T);

    return sum;
}
} // namespace MF

int S, T, ans, m1;

void build() {
    // find parallel edges
    m1 = m;
    multiset<Mes> s;

    for (int i = 1; i <= m; i++)
        s.insert(me[i]);

    while (!s.empty()) {
        auto tmp = *s.begin();
        s.erase(s.begin());

        if (tmp.typ != 1)
            continue;

        auto it = s.find({tmp.to, tmp.fr, 2, 0});

        if (it != s.end()) {
            //删除不满足性质 C 的两句话，加入新点
            me[tmp.id].typ = me[it->id].typ = -1, ans += 2;
            me[++m] = {tmp.fr, tmp.to, 3, (tmp.id << 20) | it->id};
            s.erase(it);
        }
    }

    S = 2 * m + 2 * n + 1, T = 2 * m + 2 * n + 2;

    for (int i = 1; i <= m; i++) {
        if (me[i].typ == -1)
            continue;

        int x = me[i].fr, y = me[i].to;
        addedge(S, i, 1);
        addedge(i + m, T, 1);

        if (me[i].typ < 3) {
            addedge(i, idd(x, 0), 1);
            addedge(idd(x, 1), i + m, 1);

            if (me[i].typ == 1)
                addedge(i, idd(y, 1), 1);
            else if (me[i].typ == 2)
                addedge(idd(y, 0), i + m, 1);
        } else if (me[i].typ == 3) {
            //如果是两句话缩起来的点，则建图有点区别，不过应该好理解
            addedge(idd(x, 1), i + m, 1);
            addedge(i, idd(y, 0), 1);
        }
    }
}

vi s1[N * 2], s2[N * 2];

int nxt[N], seq[N], pos;
int pre[N], id[N];

void construct() {
    //寻找每句话的下一句话（即 out_i 匹配了谁）
    for (int x = 1; x <= n; x++) {
        for (int i = head[idd(x, 0)]; i; i = e[i].nxt) {
            if (i & 1)
                continue;

            if (!e[i].f)
                s2[idd(x, 0)].pb(e[i].to - m);
        }

        for (int i = head[idd(x, 1)]; i; i = e[i].nxt) {
            if (i & 1)
                continue;

            if (!e[i].f)
                s2[idd(x, 1)].pb(e[i].to - m);
        }
    }

    for (int x = 1; x <= m; x++) {
        for (int i = head[x]; i; i = e[i].nxt) {
            if (i & 1)
                continue;

            if (!e[i].f)
                s1[e[i].to].pb(x);
        }
    }

    //nxt_i 即为第 i 句话的下一句话
    for (int x = 1; x <= n; x++) {
        for (int j = 0; j <= 1; j++) {
            int now = idd(x, j);

            for (auto x : s1[now])
                nxt[x] = s2[now].back(), s2[now].pop_back();
        }
    }

    static int vis[N];
    static vi s[N];

    auto doit = [&](int typ) {
        vector<vi> lp;
        vi st;

        for (int i = 0; i <= m; i++)
            vis[i] = 0;

        for (int i = 0; i <= n; i++)
            s[i].clear();

        for (int x = 1; x <= m; x++)
            vis[nxt[x]] = 1;

        for (int x = 1; x <= m; x++)
            if (!vis[x])
                st.pb(x);

        for (int x = 1; x <= m; x++)
            vis[x] = 0;

        //先把链给去掉
        for (auto x : st) {
            int now = x;

            while (now)
                vis[now] = 1, now = nxt[now];
        }

        // 找环
        for (int x = 1; x <= m; x++)
            if (!vis[x]) {
                int now = x;

                if (me[now].typ == typ)
                    lp.pb({});

                while (!vis[now]) {
                    vis[now] = 1;

                    if (me[now].typ == typ)
                        lp.back().pb(now);

                    now = nxt[now];
                }
            }

        //id_i 表示发送者为 i 的学术消息的编号
        for (int i = 1; i <= m; i++) {
            if (nxt[i])
                pre[nxt[i]] = i;

            if (!me[i].typ)
                id[me[i].fr] = i;
            else if (me[i].typ == 3)
                id[typ == 1 ? me[i].fr : me[i].to] = i;
        }

        auto link = [&](int x, int y) {
            nxt[x] = y, pre[y] = x;
        };

        if (typ == 1) {
            for (auto &tmp : lp) {
                int fr = me[tmp[0]].to;
                int x1 = tmp[0], y1 = nxt[tmp[0]], x2 = pre[id[fr]],
                    y2 = id[fr];
                link(x1, y2), link(x2, y1);
            }
        } else {
            for (auto &tmp : lp) {
                int fr = me[tmp[0]].fr;
                int x1 = tmp[0], y1 = nxt[tmp[0]], x2 = id[fr],
                    y2 = nxt[id[fr]];
                link(x1, y2), link(x2, y1);
            }
        }
    };

    doit(1);
    doit(2);

    vi st;

    for (int i = 0; i <= m; i++)
        vis[i] = 0;

    for (int x = 1; x <= m; x++)
        vis[nxt[x]] = 1;

    for (int x = 1; x <= m; x++)
        if (!vis[x])
            st.pb(x);

    for (int i = 1; i <= m; i++)
        vis[i] = 0;

    for (auto x : st) {
        if (me[x].typ == -1)
            continue;

        while (x)
            seq[++pos] = x, x = nxt[x];
    }

    reverse(seq + 1, seq + pos + 1);
}

void clear() {
    memset(head, 0, sizeof(int) * (T + 2));
    tot = 1;
    nam.clear();
    pos = ans = 0;

    for (int i = 0; i <= m; i++)
        nxt[i] = pre[i] = id[i] = 0;

    for (int i = 1; i <= n; i++)
        for (int j : {0, 1})
            s1[idd(i, j)].clear(), s2[idd(i, j)].clear();
}

void solve() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        nam[s] = i;
    }

    for (int i = 1; i <= m; i++) {
        string s1, s2, s3;
        cin >> s1 >> s2 >> s3;
        int fr = nam[s1], to = 0, typ = 0;
        map<string, int>::iterator it;

        //注意：这里 loushang louxia 反过来了
        if (s3 == "louxia" && (it = nam.find(s2)) != nam.end())
            typ = 1, to = it->se;
        else if (s3 == "loushang" && (it = nam.find(s2)) != nam.end())
            typ = 2, to = it->se;
        else
            typ = 0;

        me[i] = {fr, to, typ, i};
    }

    build();
    ans += MF::mf(S, T);
    construct();
    cout << ans << '\n';

    for (int i = 1; i <= pos; i++) {
        int x = seq[i];

        if (me[x].typ <= 2)
            cout << seq[i] << ' ';
        else
            //如果是两句话缩起来的，则输出两个
            cout << (me[x].id & ((1 << 20) - 1)) << ' ' << (me[x].id >> 20)
                 << ' ';
    }

    cout << '\n';
    clear();
}

int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;

    while (T--)
        solve();

    return 0;
}