題目大意

　　給定n個各不相同的無序字母對（區分大小寫，無序即字母對中的兩個字母可以位置顛倒）。請構造一個有n+1個字母的字符串使得每個字母對都在這個字符串中出現。若有多解，輸出字典序最小的那一個。

題解

　　首先由n+1可以想到什么？一條條邊首尾相接，端點數便是邊數+1。所以這道題就是一個歐拉路徑問題。

　　歐拉路徑的判定：度數為奇數的點為0個或2個。

　　歐拉路徑的遍歷：從一個度數為奇數的點（有度數為奇數的點的情況）或任意一點（無度數為奇數的點的情況）開始Dfs，存在沒有被訪問的邊就沿邊Dfs下去（節點可以重復走），最后將節點按Dfs逆后序輸出即為答案。

　　如何滿足字典序最小：我們按照逆后序輸出，我們應當讓每個節點的出邊節點編號遞增，這樣可以使得先Dfs到編號低的節點，過后再從編號高的節點回來，使得編號高的節點先入棧，逆后序輸出時編號高的節點會越靠后。

#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <stack> using namespace std;#define Char_Inten(c) (c >= 'a' ? c - 'a' + 27 : c - 'A' + 1) #define Int_Charten(x) (x <= 26 ? x - 1 + 'A' : x - 27 + 'a') const int MAX_NODE = 100, MAX_EDGE = MAX_NODE * MAX_NODE, INF = 0x3f3f3f3f; bool IntenCharVis[MAX_NODE]; int IntenChar_NodeId[MAX_NODE], NodeId_IntenChar[MAX_NODE]; int TotNode;struct ElurianGraph { private:struct Node;struct Edge;struct Node{Edge *Head;int Degree;//bool Vis;}_nodes[MAX_NODE], *Start, *Target;int _vCount;struct Edge{Edge *Next, *Rev;Node *From, *To;bool Vis;}_edges[MAX_EDGE];int _eCount;stack<Edge*> EdgeSt;Edge *AddEdge(Node *from, Node *to){Edge *e = _edges + ++_eCount;e->From = from;e->To = to;Node *prevTo = NULL;Edge **InsNext = &from->Head;while (true){if (!*InsNext || (prevTo <= e->To && e->To <= (*InsNext)->To)){e->Next = *InsNext;*InsNext = e;break;}else{prevTo = (*InsNext)->To;InsNext = &(*InsNext)->Next;}}return e;}void Dfs(Node *cur){_printf("Visiting %d\n", cur - _nodes);//if (cur->Vis)// return;//cur->Vis = true;for (Edge *e = cur->Head; e; e = e->Next){if (!e->Vis){e->Vis = e->Rev->Vis = true;Dfs(e->To);EdgeSt.push(e);}}}public:void Init(int n){_vCount = n;_eCount = 0;Start = Target = NULL;}void Build(int u, int v){Edge *e1 = AddEdge(_nodes + u, _nodes + v);Edge *e2 = AddEdge(_nodes + v, _nodes + u);e1->Rev = e2;e2->Rev = e1;_nodes[u].Degree++;_nodes[v].Degree++;}bool IsConnect(){for (int i = 1; i <= _vCount; i++){if (_nodes[i].Degree & 1){if (Target)return false;else if (Start){Target = _nodes + i;if (Start > Target)swap(Start, Target);}elseStart = _nodes + i;}}bool ans = (Start && Target) || !(Start || Target);if (!Start)Target = Start = _nodes + 1;return ans;}int *GetOrder(){int *ans = new int[MAX_EDGE];Dfs(Start);int i = 0;ans[++i] = EdgeSt.top()->From - _nodes;while (!EdgeSt.empty()){ans[++i] = EdgeSt.top()->To - _nodes;EdgeSt.pop();}ans[++i] = 0;return ans;} }g;void GetChar_NodeId() {TotNode = 0;for (int intenChar = 1; intenChar <= 52; intenChar++)if (IntenCharVis[intenChar]){IntenChar_NodeId[intenChar] = ++TotNode;NodeId_IntenChar[TotNode] = intenChar;} }int main() {int n;scanf("%d", &n);static char ss[MAX_EDGE][10];for (int i = 1; i <= n; i++){scanf("%s", ss[i] + 1);IntenCharVis[Char_Inten(ss[i][1])] = IntenCharVis[Char_Inten(ss[i][2])] = true;}GetChar_NodeId();g.Init(TotNode);for (int i = 1; i <= n; i++)g.Build(IntenChar_NodeId[Char_Inten(ss[i][1])], IntenChar_NodeId[Char_Inten(ss[i][2])]);if (!g.IsConnect()){printf("No Solution\n");return 0;}int *ans = g.GetOrder();for (int i = 1; ans[i]; i++)printf("%c", Int_Charten(NodeId_IntenChar[ans[i]]));printf("\n");return 0; }

　　

轉載于:https://www.cnblogs.com/headboy2002/p/9439683.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的luogu1341 无序字母对的全部內容，希望文章能夠幫你解決所遇到的問題。

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