Description:
給一個DAGDAG圖，記邊是從aiai到bibi，邊權cici，要從00走到nn，求最短路。
保證ai<biai<bi，而且不存在ai<aj<bi<bjai<aj<bi<bj
每個點有一個顏色，每種顏色在路徑上要么不經過，要么全部經過

---

Solution:
吐槽:考試的時候幾乎想出了正解，可惜不會建對偶圖就gggg了。

首先我們把連成一條線的邊變成一個環，一個環的邊變成一條線，這樣最小割對應的也就是一條路徑。然后考慮顏色限制，那么劃分完區間后，每種區間里的顏色意味著如果選了這個顏色那么區間也得選。把每種顏色對應的區間互相連infinf即可。最后每個點向父親連邊，用來判無解。

---

#include <bits/stdc++.h> using namespace std; const int maxn = 5005, inf = 0x3f3f3f3f; struct edge {int nxt, to, f; } e[2000005]; int n, m, ans, cnt = 1, source, sink, tot = 1; int h[maxn], iter[maxn], d[maxn], c[maxn]; vector<int> col[maxn], G[maxn], w[maxn]; void link(int u, int v, int f) {e[++cnt].nxt = h[u];h[u] = cnt;e[cnt].to = v;e[cnt].f = f; } void insert(int u, int v, int f) {link(u, v, f);link(v, u, 0); } bool bfs() {queue<int> q;q.push(source);memset(d, -1, sizeof(d));d[source] = 0;while(!q.empty()) {int u = q.front();q.pop();for(int i = h[u]; i; i = e[i].nxt) {if(d[e[i].to] == -1 && e[i].f) {d[e[i].to] = d[u] + 1;q.push(e[i].to);}}}return d[sink] != -1; } int dfs(int u, int delta) {if(u == sink) {return delta;}int ret = 0;for(int &i = iter[u]; i; i = e[i].nxt) {if(d[e[i].to] == d[u] + 1 && e[i].f) {int x = dfs(e[i].to, min(delta, e[i].f));e[i].f -= x;e[i ^ 1].f += x;delta -= x;ret += x;if(!delta) {break;}}}return ret; } int dinic() {int ret = 0;while(bfs()) {memcpy(iter, h, sizeof(h));ret += dfs(source, inf);ret = min(ret, inf);}return ret; } class ColorfulPath {public: void build(int l, int r, int fa) {for(int x = l; x < r; ) {int y = 0, p = 0, m = G[x].size();if(x ^ l) {col[c[x]].push_back(fa);}for(int i = 0; i < m; ++i) {if(G[x][i] > y) {y = G[x][i];p = i;}}if(!y) {insert(fa, sink, inf);for(int i = l + 1; i < r; ++i) {col[c[i]].push_back(fa);}return;} else {G[x][p] = 0;++tot;insert(fa, tot, w[x][p]);insert(tot, fa, inf); build(x, y, tot);x = y; }}}int shortestPath(vector<int> a, vector<int> b, vector<int> cost, vector<int> color) {sink = 1;n = color.size() + 1;int m = a.size();for(int i = 0; i < m; ++i) {G[a[i]].push_back(b[i]);w[a[i]].push_back(cost[i]);}for(int i = 1; i < n; ++i) {c[i] = color[i - 1];}build(0, n, source);for(int i = 1; i <= 1000; ++i) {m = col[i].size();for(int j = 1; j < m; ++j) {insert(col[i][j - 1], col[i][j], inf);insert(col[i][j], col[i][j - 1], inf);}}int ans = dinic();return ans >= inf ? -1 : ans;} };

總結

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

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