鏈接：https://community.topcoder.com/stat?c=problem_statement&pm=14447&rd=16839

題意：給一個DAG圖，記邊是從a[i]到b[i]，邊權c[i]，要從0走到n，求最短路。

保證a[i] < b[i]，而且不存在a[i] < a[j] < b[i] < b[j]

每個點有一個顏色，每種顏色在路徑上要么不經過，要么全部經過

題解：

網絡流

認真觀察可以發現這些邊對應的區間構成了樹的形式

我們考慮用最小割解決這道題

假設當前考慮區間[l, r]，表示節點為fa，則對于每個分割點[a, b]，表示節點為x，連邊(fa, x, c(a, b))

樹葉向T連INF的邊，畫一畫就知道一個割對應一條路徑。

現在考慮顏色，每個father記錄子節點的顏色，被放進對應顏色的vector里，然后兩兩連INF的邊，樹上向上加INF的反向邊

這樣保證了每種顏色的點要么都在S集，要么都在T集

#include <bits/stdc++.h> #define xx first #define yy second #define mp make_pair #define pb push_back #define fill( x, y ) memset( x, y, sizeof x ) #define copy( x, y ) memcpy( x, y, sizeof x ) using namespace std;typedef long long LL; typedef pair < int, int > pa;const int MAXN = 5005; const int MAXM = 500005; const int INF = 0x3f3f3f3f;int cnt = 1, n, c[MAXN]; vector < int > r[MAXN], w[MAXN], col[MAXN];namespace Flow {struct edge { int to, nxt, flow; } e[MAXM];int head[MAXN], cur[MAXN], S, T = 1, e_cnt = 1, q[MAXN], ql, qr, dis[MAXN];inline void Add(int x, int y, int w) { e[ ++e_cnt ] = { y, head[ x ], w }; head[ x ] = e_cnt; }inline void Addedge(int x, int y, int w) { Add( x, y, w ); Add( y, x, 0 ); }inline bool Bfs(){for( int i = 0 ; i <= cnt ; i++ ) dis[ i ] = 0;dis[ q[ ql = 0 ] = S ] = qr = 1;while( ql < qr ){int x = q[ ql++ ];for( int i = head[ x ] ; i ; i = e[ i ].nxt )if( e[ i ].flow && !dis[ e[ i ].to ] ) dis[ q[ qr++ ] = e[ i ].to ] = dis[ x ] + 1;}return dis[ T ];}inline int Dfs(int x, int f){if( x == T ) return f;int ret = 0;for( int &i = cur[ x ] ; i ; i = e[ i ].nxt )if( e[ i ].flow && dis[ e[ i ].to ] == dis[ x ] + 1 ){int d = Dfs( e[ i ].to, min( f - ret, e[ i ].flow ) );ret += d; e[ i ].flow -= d; e[ i ^ 1 ].flow += d;if( ret == f ) return ret;}if( !ret ) dis[ x ] = -1;return ret;}inline int Dinic(){int ret = 0;while( Bfs() ) memcpy( cur, head, sizeof head ), ret += Dfs( S, INF ), ret = min( ret, INF );return ret;} }using Flow::Addedge; using Flow::S; using Flow::T; using Flow::Dinic;class ColorfulPath {public:inline void build(int L, int R, int fa){for( int x = L ; x < R ; ){int d = 0, y = 0, m = r[ x ].size();if( x ^ L ) col[ c[ x ] ].pb( fa );for( int i = 0 ; i < m ; i++ ) if( r[ x ][ i ] > y ) y = r[ x ][ i ], d = i;if( !y ){Addedge( fa, T, INF );for( int i = L + 1 ; i < R ; i++ ) col[ c[ i ] ].pb( fa );return ;}else{r[ x ][ d ] = 0;cnt++;Addedge( fa, cnt, w[ x ][ d ] ); Addedge( cnt, fa, INF );build( x, y, cnt );x = y;}}}int shortestPath(vector < int > a, vector < int > b, vector < int > cost, vector < int > color){n = color.size() + 1; int m = a.size();for( int i = 0 ; i < m ; i++ ) r[ a[ i ] ].pb( b[ i ] ), w[ a[ i ] ].pb( cost[ i ] );for( int i = 1 ; i < n ; i++ ) c[ i ] = color[ i - 1 ];build( 0, n, S );for( int i = 1 ; i <= 1000 ; i++ ){m = col[ i ].size();for( int j = 1 ; j < m ; j++ ) Addedge( col[ i ][ j ], col[ i ][ j - 1 ], INF ), Addedge( col[ i ][ j - 1 ], col[ i ][ j ], INF );}int ans = Dinic();if( ans >= INF ) ans = -1;return ans;} };

總結

以上是生活随笔為你收集整理的Topcoder 2016 TCO Algorithm Algo Semifinal 1 Hard的全部內容，希望文章能夠幫你解決所遇到的問題。

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