中石油训练赛 - Swapping Places(字典序最小的拓扑排序)

题目链接：点击查看

题目大意：给出 s 个字符串表示种类，再给出 m 个朋友关系，表示两个种类的动物是朋友，现在给出一个长度为 n 的种类排列，规定相邻两个是朋友的种类的动物可以交换位置，问如何操作，可以使得整个字符串的字典序最小

题目分析：感觉很好的一道图论题，因为建图实在是非常的巧妙

正难则反，考虑对于两个种类的动物来说，如果其不是朋友关系的话，那么在序列中，其相对位置无论如何都是不会改变的

所以最简单的一个思路就是，设 a[ i ] ，i ∈ [ 1 , n ] 为：第 i 个元素的种类，设 f[ x ][ y ]，x,y ∈ [ 1 , s ] 为：种类 x 和 y 是否为朋友关系，然后对于长度为 n 的序列建出一张完全图，即对于任意两个位置 i 和 j 如果满足下列情况时可以建立 i -> j 的有向边：

i < j

a[ i ] 和 a[ j ] 不是朋友

然后进行拓扑排序就可以了，因为需要求字典序最小，所以需要加上一个优先队列用来贪心确定字典序

以上思路的正确性毋庸置疑，不过现在的问题是，n 比较大，建立上述完全图需要 n * n 的时空复杂度，显然是不太可行的

再考虑下图中的一种情况：

按照上述思路建出一张完全图，不难发现对于相同的种类（种类 a）来说，后面的元素一定会被前面的元素所约束，又因为不同的种类（种类 b）会被前面不同的种类（种类 a）的所有元素约束，实质上起约束作用的只有（种类 a）的最后一个元素，这样一来就可以将上述 n * n 的图简化成一个 n * s 的图，即：对于每个位置 i 而言，只需要找到其前面 不属于朋友的种类 的最后一次出现的位置 j 然后连边 j -> i 即可，如此建图后，正确性还是可以得证，然后跑拓扑就好了

代码：
 

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;string str[310];map<string,int>mp;bool f[310][310];int a[N],pre[310],du[N];//pre[i]:种类i上一次出现的位置 vector<int>node[N];struct cmp {bool operator()(int x,int y){if(a[x]==a[y])return x>y;return a[x]>a[y];} };int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int s,l,n;scanf("%d%d%d",&s,&l,&n);for(int i=1;i<=s;i++)cin>>str[i];sort(str+1,str+1+s);for(int i=1;i<=s;i++)mp[str[i]]=i;for(int i=1;i<=l;i++){string a,b;cin>>a>>b;f[mp[a]][mp[b]]=f[mp[b]][mp[a]]=true;}for(int i=1;i<=n;i++){string s;cin>>s;a[i]=mp[s];}for(int i=1;i<=n;i++)//为每个点找一个前驱 {for(int j=1;j<=s;j++){if(!pre[j]||f[a[i]][j])continue;node[pre[j]].push_back(i);du[i]++;}pre[a[i]]=i;}priority_queue<int,vector<int>,cmp>q;for(int i=1;i<=n;i++)if(!du[i])q.push(i);while(q.size()){int u=q.top();q.pop();cout<<str[a[u]]<<' ';for(auto v:node[u])if(!--du[v])q.push(v);}return 0; }

 

总结

以上是生活随笔为你收集整理的中石油训练赛 - Swapping Places(字典序最小的拓扑排序)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。