AtCoder Regular Contest 061 E - Snuke’s Subway Trip

problem

洛谷翻譯

my idea

最近一直在做網絡流，所以一讀這題后，我就想到了最小費用流。

首先的問題就是建邊問題。

不同線路到達同一個點從而引發后面的費用是相互獨立的，不能由同一個點表示。

所以我想到了拆點，把每條邊對應的兩個點都分別拆出一個虛點，此虛點就代表這條邊的顏色。

顯然每個點只會拆出與之關聯的邊不同顏色的個數，而一條邊只關聯兩個點，這最多是 $O(n+2m)$ 的。

到目前為止都是可以接受的。

然后就是從一個站點到另一個站點之間的連邊，發現如果要把所有情況都包含，必須一個站點的所有拆點都向另一個站點的所有拆點連邊，費用為 $1/0$。別的不說，這邊數就是 $O(m^2)$ 級別的了。

肯定的，我們非常想把每個站點的拆點都縮成一個虛點。

顏色不同的連虛點費用 $1$，顏色相同就不管。然而——stuck

solution

將邊當作點，正反向邊分別建點，建立源匯 $s,t$。

先將原圖每個節點 $u$ 按照出邊的顏色排序，保證相同顏色的出點 $v$ 是連續的一段區間。

【以下在新圖中連邊參與的“點”都是指把邊當作點時，邊的編號】

• 正反向邊之間連邊，費用 $0$。

• 如果邊起點為 $1$，連邊 $(s,id,1)$。因為從 $s$ 開始就相當于換了公司。

• 如果 $u$ 相同的兩條相鄰出邊 $i{d}_1,i{d}_2$ 顏色一樣，那么相互連邊 $(i{d}_1,i{d}_2,0),(i{d}_2,i{d}_1,0)$。

  因為這兩條邊可以免費走。這樣一段連續的相同顏色的邊兩兩之間都可以免費走了。

• 考慮顏色轉化的點，暴力連邊如上面是會卡成平方的。

  新建一個虛點，對于 $u$ 出邊的每種顏色，隨便取一條可以代表這種顏色的邊向虛點連邊 $1$。

  【上一個連邊知道了相同顏色的邊是兩兩之間隨便走的，所以隨便選哪條連虛點都不影響。】

  虛點往這條隨便選取的邊連邊 $0$。

  往虛點走就證明已經換了一家公司，然后虛點走向的點就是換完后代表的公司了。

  如果不走虛點就表示不換公司。

• 如果邊終點為 $n$，連邊 $(u,t,0)$。

每個點只會建立一個虛點，每條邊拆成正反兩條邊，還有源匯，總點數為 $O(n+2m+2)$。

邊數也是差不多級別的。

費用只有 $0/1$ 之分，而且這個費用可以看作是邊權。

0/1 bfs 可以做到線性，但是堆優化 dijkstra 跑個最短路，更板子不用腦一點直接寫。

code

#include <bits/stdc++.h> using namespace std; #define maxn 2000005 #define inf 0x7f7f7f7f #define Pair pair < int, int > struct node { int v, c, id; }; vector < node > E[maxn]; vector < Pair > G[maxn]; priority_queue < Pair, vector < Pair >, greater < Pair > > q; int n, m, s, t; int dis[maxn], tag[maxn];void dijkstra() {memset( dis, 0x7f, sizeof( dis ) );q.push( { dis[s] = 0, s } );while ( q.size() ) {int u = q.top().second, d = q.top().first; q.pop();if( dis[u] ^ d ) continue;for( int i = 0; i < G[u].size();i ++ ) {int v = G[u][i].first, w = G[u][i].second;if( dis[v] > dis[u] + w ) {dis[v] = dis[u] + w;q.push( { dis[v], v } );}} } }int main() {scanf( "%d %d", &n, &m );for( int i = 1, u, v, c;i <= m;i ++ ) {scanf( "%d %d %d", &u, &v, &c );E[u].push_back( { v, c, i << 1 } );E[v].push_back( { u, c, i << 1 | 1 } );}s = 1, t = m * 2 + 2; int tot = t;for( int i = 1;i <= n;i ++ ) {tot ++;sort( E[i].begin(), E[i].end(), []( node x, node y ) { return x.c < y.c; } );for( int j = 0;j < E[i].size();j ++ ) {int k = E[i][j].v, c = E[i][j].c, id = E[i][j].id;if( tag[c] ^ i ) {tag[c] = i;G[tot].push_back( { id, 0 } );G[id].push_back( { tot, 1 } );}G[id].push_back( { id ^ 1, 0 } );if( i == 1 ) G[s].push_back( { id, 1 } );if( k == n ) G[id].push_back( { t, 0 } );if( j and c == E[i][j - 1].c ) G[id].push_back( { E[i][j - 1].id, 0 } ), G[E[i][j - 1].id].push_back( { id, 0 } );}}dijkstra();printf( "%d\n", dis[t] == inf ? -1 : dis[t] );return 0; }

總結

以上是生活随笔為你收集整理的AtCoder Regular Contest 061 E - Snuke‘s Subway Trip（建图 + dijkstra最短路 / 0/1bfs / 并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。

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