luogu2770 航空路線問題 網絡流

題目大意：

給定一張航空圖，圖中頂點代表城市，邊代表 2 城市間的直通航線。現要求找出一條滿足下述限制條件的且途經城市最多的旅行路線。
(1)從最西端城市出發，單向從西向東途經若干城市到達最東端城市，然后再單向從東向西飛回起點(可途經若干城市)。
(2)除起點城市外，任何城市只能訪問 1 次。

?

關鍵字：網絡流 方向等效轉換 拆點 不交叉路徑 特判

?

網絡流：1個人旅行的過程可以看作以流量為1流動的過程。

方向等效轉化：本問題可以看作兩個人同時從最西的城市走向最東的城市，每個人占有1個流量，總流量為2。

拆點：題中說每個城市只經過一次，因此把一個城市看作容量為1的邊，如果西東兩個城市之間有航線，則把西城to節點連東城from節點，容量為1。為保證總流量為2，最西城邊容量和最東城容量為2。

不交叉路徑：流量為1，即可保證路徑不交叉

特判：如果最西城與最東城有航線，則邊的容量為2。

?

#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <cassert>
#include <map>
#include <string>
#include <iostream>
using namespace std;//#define test
#define INF 0x3f3f3f3f
#define LOOP(i,n) for(int i=1; i<=n; i++)
const int MAX_CITY = 110, MAX_EDGE = MAX_CITY*MAX_CITY + MAX_CITY * 2, MAX_NODE = MAX_CITY * 2;
map<string, int> loc;
string Cities[MAX_CITY];
bool Vis[MAX_CITY];
int TotCity, TotLine;struct MCMF
{struct Node;struct Edge;struct Node{int Id;Edge *Head, *Prev;int Dist;bool Inq;void Init(){Prev = NULL;Dist = INF;Inq = false;}};struct Edge{int Cap, Cost;Node *From, *To;Edge *Next, *Rev;Edge(int cap, int cost, Node *from, Node *to, Edge *next) :Cap(cap), Cost(cost), From(from), To(to), Next(next){}};Node _nodes[MAX_NODE];Edge *_edges[MAX_EDGE];int _vCount = 0, _eCount = 0;Node *Start, *Sink;int TotFlow, TotCost;void Reset(int n, int sId, int tId){_vCount = n;_eCount = 0;Start = &_nodes[sId], Sink = &_nodes[tId];TotFlow = TotCost = 0;}Edge* AddEdge(Node *from, Node *to, int cap, int cost){Edge *cur = _edges[++_eCount] = new Edge(cap, cost, from, to, from->Head);from->Head = cur;return cur;}void Build(int uId, int vId, int cap, int cost){Node *u = &_nodes[uId], *v = &_nodes[vId];u->Id = uId;v->Id = vId;Edge *edge1 = AddEdge(u, v, cap, cost);Edge *edge2 = AddEdge(v, u, 0, -cost);//遺忘點*2：-costedge1->Rev = edge2;edge2->Rev = edge1;}bool SPFA(){queue<Node*> q;for (int i = 1; i <= _vCount; i++)_nodes[i].Init();Start->Dist = 0;q.push(Start);while (!q.empty()){Node *u = q.front();q.pop();u->Inq = false;//易忘點for (Edge *e = u->Head; e; e = e->Next){if (e->Cap && u->Dist + e->Cost < e->To->Dist)//易忘點*2：e->Cap
                {e->To->Dist = u->Dist + e->Cost;e->To->Prev = e;if (!e->To->Inq){e->To->Inq = true;q.push(e->To);}}}}return Sink->Prev;}void Proceed(){while (SPFA()){assert(Sink->Dist != INF);int minFlow = INF;for (Edge *e = Sink->Prev; e; e = e->From->Prev)minFlow = min(minFlow, e->Cap);TotFlow += minFlow;for (Edge *e = Sink->Prev; e; e = e->From->Prev){e->Cap -= minFlow;e->Rev->Cap += minFlow;TotCost += minFlow * e->Cost;
#ifdef testprintf("%d-%d Cost %d restCap %d\n", e->From->Id, e->To->Id, e->Cost*minFlow, e->Cap);
#endif}
#ifdef testprintf("TotFlow %d TotCost %d\n", TotFlow, TotCost);
#endif}}int GetFlow(){return TotFlow;}int GetCost(){return TotCost;}
}g;void print1()
{MCMF::Node *cur = 1 + g._nodes;while (cur->Id != TotCity){Vis[cur->Id] = true;cout << Cities[cur->Id] << endl;cur = cur->Id + TotCity + g._nodes;for (MCMF::Edge *e = cur->Head; e; e = e->Next){if (!e->Cap && !Vis[e->To->Id] && e->To->Id > cur->Id-TotCity){cur = e->To;break;}}}
}void print2(int id)
{if (id == TotCity){cout << Cities[id] << endl;return;}Vis[id] = true;MCMF::Node *cur = id + TotCity + g._nodes;for (MCMF::Edge *e = cur->Head; e; e = e->Next){if (!e->Cap && !Vis[e->To->Id] && e->To->Id > cur->Id - TotCity){print2(e->To->Id);break;}}cout << Cities[id] << endl;
}int main()
{
#ifdef _DEBUGfreopen("c:\\noi\\source\\input.txt", "r", stdin);
#endifint sId, tId;string s1, s2;scanf("%d%d", &TotCity, &TotLine);sId = 1;tId = TotCity * 2;g.Reset(tId, sId, tId);LOOP(city, TotCity){cin >> Cities[city];loc.insert(pair<string, int>(Cities[city], city));if (city == 1 || city == TotCity)g.Build(city, city + TotCity, 2, -1);elseg.Build(city, city + TotCity, 1, -1);}LOOP(line, TotLine){cin >> s1 >> s2;int p1 = loc[s1], p2 = loc[s2];if (p2 < p1)swap(p1, p2);if (p1 == 1 && p2 == TotCity)g.Build(p1+TotCity, p2, 2, 0);elseg.Build(p1+TotCity, p2, 1, 0);}g.Proceed();if (g.TotFlow<2){cout << "No Solution!" << endl;return 0;}printf("%d\n", -g.TotCost-2);LOOP(v, g._vCount)g._nodes[v].Inq = false;print1();print2(1);return 0;
}

?