uva 1658 Admiral题目大意：在图中找出两条没有交集的线路，，要求这两条线路的费用最小。解题思路：还是拆点建图的问题。首先每个点都要拆成两个点，例如a点拆成a->a’。起点和终点的两点间的容量为2费用为0，保证了只找出两条线路。其余点的容量为1费用为0，保证每点只走一遍，两条线路无交集。然后根据题目给出的要求继续建图。每组数据读入a, b, c， 建立a’到b的边容量为1， 费用为c。图建完之后，用bellman-ford来实现MCMF。;ll;const int N = 2005;const int INF = 0x3f3f3f3f;int n, m, s, t;int a[N], pre[N], d[N], inq[N]; struct Edge{int from, to, cap, flow;ll cos;};vector<Edge> edges;vector<int> G[N];void init() {for (int i = 0; i < 2 * n; i++) G[i].clear();edges.clear();}void addEdge(int from, int to, int cap, int flow, ll cos) {edges.push_back((Edge){from, to, cap, 0, cos});edges.push_back((Edge){to, from, 0, 0, -cos});int m = edges.size();G[from].push_back(m – 2);G[to].push_back(m – 1);}void input() {addEdge(1, n + 1, 2, 0, 0);for (int i = 2; i <= n – 1; i++) {addEdge(i, i + n, 1, 0, 0);}addEdge(n, 2 * n, 2, 0, 0);int u, v;ll c;for (int i = 0; i < m; i++) {scanf(“%d %d %lld”, &u, &v, &c);addEdge(u + n, v, 1, 0, c);}}int BF(int s, int t, int& flow, ll& cost) {queue<int> Q;memset(inq, 0, sizeof(inq));memset(a, 0, sizeof(a));memset(pre, 0, sizeof(pre));for (int i = 0; i <= 2 * n + 1; i++) d[i] = INF;d[s] = 0;a[s] = INF;inq[s] = 1;int flag = 1;pre[s] = 0;Q.push(s);while (!Q.empty()) {int u = Q.front(); Q.pop();inq[u] = 0;for (int i = 0; i < G[u].size(); i++) {Edge &e = edges[G[u][i]];if (e.cap > e.flow && d[e.to] > d[u] + e.cos) {d[e.to] = d[u] + e.cos;a[e.to] = min(a[u], e.cap – e.flow);pre[e.to] = G[u][i];if (!inq[e.to]) {inq[e.to] = 1;Q.push(e.to);}}}flag = 0;}if (d[t] == INF) return 0;flow += a[t];cost += (ll)d[t] * (ll)a[t];for (int u = t; u != s; u = edges[pre[u]].from) {edges[pre[u]].flow += a[t];edges[pre[u]^1].flow -= a[t];}return 1;}int MCMF(int s, int t, ll& cost) {int flow = 0;cost = 0;while (BF(s, t, flow, cost));return flow;}int main() {while (scanf(“%d %d”, &n, &m) == 2) {s = 1, t = 2 * n;ll cost;init();input();MCMF(s, t, cost);printf(“%lld\n”, cost);}return 0;}
才能做到人在旅途，感悟人生，享受人生。
