2023睿抗省赛D

题意

输入第一行是一个正整数 N (1≤N≤1000），表示总共有多少条推论。

接下来的 N 行，每行有两对四个元素，形如下：

A 0 B 1
每对元素表示一个论点：第一个是一个长度不大于 5 的、只包含大小写字母的字符串，称为论点的核心；第二个数字固定为 0 或者 1，代表论点核心的方向属性。为简单理解，你可以将 0 理解为正面方向，1 理解为负面方向。例如：

YuCi 0 Rou 1

就可以理解为鱼刺大，肉少 。

于是一行中的两个论点就形成一条推论，表示第一个核心某个方向的属性能推出第二个核心的某个方向的属性，即鱼刺越大，肉越少。

输出格式:

按照弹幕格式输出一行，例如：

Yu 0 YuCi 0 YuCi 0 Rou 1 Rou 1 Yu 1 = Yu 0 Yu 1

具体格式要求为：在一行中输出从起始论点到最终论点的所有推论，论点格式与输入相同，论点间以1个空格分隔。随后输出等号（等号前后均有1个空格），最后是相互矛盾的起始和终止论点。

如果有多种方案，选择使用推论最少的；推论条数相同的输出任意一种方案均可。

在方案中每条推论仅可使用一次。保证有解，且给定的推论中没有相同的推论。

输入样例:

5
Yu 0 Yuci 0
Rou 1 Yu 1
Yuci 0 Rou 1
Yuci 0 Gutou 0
Gutou 0 Rou 0

输出样例:

Yu 0 Yuci 0 Yuci 0 Rou 1 Rou 1 Yu 1 = Yu 0 Yu 1

题解

题意中存在多种要求

• 输出格式要求 输出要完全满足格式，即推论尾部重复作为推论结果和推论依据，最后得到结论，等于号，给出推论第一条依据和最后一条结果
• 最短要求 要求如果存在多种可能，就输出最短的一条

依据推到性质可以看出，可以用图论做，抽象成推论依据连接推论结果的图

要求最短，用BFS做，要求输出，需要做映射，回溯得到答案，为了方便可以将图建成逆向图，这样BFS映射的答案就是顺序的

关键在于如何建图

• 题目中每个数据都是由一个串和一个01数组成，使用pair存储
• 但是由此，每个数据并没有编号，需要用哈希给出每个数据的单独编号（不重不漏）
• 按这个编号重新映射回这个数据，要求反向再哈希一次
• 依据这个编号建图

BFS搜索中，已知起点数据，可以依据题意推到出终点数据，用vector记录每个数据是由什么编号的数据引入队列的，之后再回溯

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e5 + 10, M = 2 * N;
typedef pair<string, int> PSI;
 
map<PSI, int> m1;
map<int, PSI> m2;
 
int h[N], e[M], ne[M], idx;
 
void add(int a, int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}
 
int f[N];
vector<PSI> ans;
bool st[M];
 
 
void bfs(PSI s)
{
    int tmp = m1[s];
    PSI t = s;
    t.second = 1 - s.second;
    if(m1.count(t) == 0) return;
 
    int end = m1[t];
 
    queue<int> q;
    q.push(tmp);
    st[tmp] = 1;
 
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
 
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(st[j]) continue;
 
            st[j] = 1;
            q.push(j);
 
            f[j] = t;
            if(j == end) break;
        }
    }
 
    if(f[end] == 0) return;
 
    vector<PSI> res; 
    //res.push_back(m2[end]);
    while(end != 0)
    {
        res.push_back(m2[end]);
        end = f[end];
    }
    //res.push_back(m2[tmp]);
    if(res.size() != 0 && ans.size() > res.size() || ans.size() == 0) ans = res;
}
 
 
int main()
{
    memset(h, -1, sizeof h);
    int n;
    cin >> n;
 
    int cnt = 0;
    for(int i = 0; i < n; i ++)
    {
        string s1, s2;
        int a, b;
        cin >> s1 >> a >> s2 >> b;
 
        PSI p1, p2;
        p1.first = s1, p1.second = a;
        p2.first = s2, p2.second = b;
 
        //m1存下对应的编号，方便bfs，m2存下编号对应的PSI，方便找回输出
        if(!m1.count(p1)) m1[p1] = ++ cnt, m2[cnt] = p1;
        if(!m1.count(p2)) m1[p2] = ++ cnt, m2[cnt] = p2;
 
        //逆序加入
        add(m1[p2], m1[p1]);
    }
 
    for(auto t: m1)
    {
        memset(st, 0, sizeof st);
        memset(f, 0, sizeof f);
        bfs(t.first);
    }
 
 
    for(int i = 0; i < ans.size(); i ++)
    {
        cout << ans[i].first << ' ' << ans[i].second << ' ';
        if(i > 0 && i < ans.size() - 1) 
        {
            cout << ans[i].first << ' ' << ans[i].second << ' ';
        }
        if(i == ans.size() - 1)
        {
            cout << "= ";
            cout << ans[0].first << ' ' << ans[0].second << ' ';
            cout << ans[i].first << ' ' << ans[i].second;
        }
    }
    cout << endl;
}
 
 
//Yu 0 Yuci 0 Yuci 0 Rou 1 Rou 1 Yu 1 = Yu 0 Yu 1
//Yu 0 Yuci 0 Yuci 0 Rou 1 Rou 1 Yu 1 = Yu 0 Yu 1