題目鏈接：點擊查看

題目大意：給出 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(字典序最小的拓扑排序)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。