icontofig | 发布于 2020-03-08 21:56:31 | 阅读量 809 | topsort
发布于 2020-03-08 21:56:31 | topsort

题目大意

有s种动物排成一个长度为n的队伍,有l种朋友关系a b,动物a和动物b为朋友可以互相交换位置,但是当且仅当这两种动物在相邻位置时。

问在所有的可能交换位置的方案后,序列最小的字典序排列是什么。

题解

挺难想的一个题,看题解只有一句话,看代码看了好久才想明白。

通过动物之间的朋友关系,我们可以确定可以互相交换的有哪些位置,也可以确定哪些动物的相对位置是不能发生改变的。

于是我们可以利用不是朋友的动物之间的相对位置不能发生改变这一点,来进行拓扑排序(当然是字典序更小的动物为更优先序的)

首先给所有物种的名字排序保证是字典序,然后用二维数组E:0 表示两个物种可以交换(是朋友),1表示不能交换(不是朋友)、二维数组Fij:0表示物种i的当前最前位置的一个在物种j当前最前位置的前面,1则相反。

然后枚举每个位置放哪个物种,如果当前物种i满足有一个j使得Eij & Fij = 1,那么就说明这个物种当前最前面的个体之前有不能与其交换的个体,就不能在当前这个位置放这个物种的这个个体,就需要放其它物种。如果满足没有这样的j,那么这个位置就放物种i了(这时字典序一定最小),然后更新一下Fij(因为是Fij表示的是两物种当前未被放入序列种的最靠前的个题之间的位置关系),继续枚举下一位置放什么就可以了。

E和F由于只需要&操作,所以可以用bitset来进行加速。

代码

#include <bits/stdc++.h>
using namespace std;
int s,l,n;
const int maxn = 205;
vector<int>pos[maxn];
string a,b;
vector<string>name;
int id(string str){
   return lower_bound(name.begin(),name.end(),str) - name.begin(); 
}
bitset<maxn>e[maxn],f[maxn];
vector<int>ans;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s >> l >> n;
    name.reserve(s);
    for(int i = 0;i < s;++i){
        cin >> a;
        name.push_back(a);
    }
    sort(name.begin(),name.end());
    for(int i = 0;i < maxn;++i)
        for(int j = 0;j < maxn;++j)
            e[i][j] = 1;
    memset(f,0,sizeof(f));
    for(int i = 0;i < l;++i){
        cin >> a >> b;
        int k = id(a),m = id(b);
        e[k][m] = e[m][k] = 0;
    }
    for(int i = 0;i < s;++i)
        e[i][i] = 0;
    for(int i = 0;i < n;++i){
        cin >> a;
        pos[id(a)].push_back(i);
    }
    for(int i = 0;i < s;++i){
        pos[i].push_back(n);
        reverse(pos[i].begin(),pos[i].end()); // 反一下会好做一些,正着来不好做,因为涉及到pop_back操作
    }
    for(int i = 0;i < s;++i)
        for(int j = 0;j < s;++j){
            if(i == j)continue;
            if(pos[i].back() > pos[j].back())
                f[i][j] = 1;
        }
    ans.clear();
    while(ans.size() < n){
        int id = 0;
        while((id < s && pos[id].back() == n) || (e[id] & f[id]).any())
            id++;
        ans.push_back(id);
        pos[id].pop_back();
        for(int i = 0;i < s;++i){
            f[id][i] = 0;
            f[i][id] = 0;
            (pos[id].back() > pos[i].back()) ? (f[id][i] = 1) : (f[i][id] = 1);
        }
    }
    for(auto i : ans){
        cout << name[i] << " ";
    }
    cout << "\n";
    return 0;
}



内容更新于: 2020-03-08 21:56:38
链接地址: http://blog.leanote.com/post/icontofig/d0af44307eaf

上一篇: HDU6417 Rikka with APSP min25筛+mobius反演 题解代码

下一篇: SWERC 2019-2020 Problem A Environment-Friendly Travel DP+bfs

809 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航