給你一個無向圖，每條邊有cost，現在問如果不走已經走過的邊，則從S到T，然後再從T到S的最少cost是多少，如果無法達成則輸出"Back to jail"。
想法：
最小cost最大流，S到T再從T到S，也就是T當作源點，S當作匯點，從T流到S，看是否能流過去2條，如果能則輸出min_cost，否則輸出"Back to jail"。
因為同一條邊不能重複走，因此可以用一個二維矩陣used[][]，在SPFA找"正向邊"的時候檢查used[i][j]!=true，除了code 82行和96行之外，其他都和MCMF模板一樣。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <cstring> | |
| #include <vector> | |
| #include <queue> | |
| #include <algorithm> | |
| using namespace std; | |
| #define INF 99999999 | |
| #define MAXN 205 | |
| vector<int> edge[MAXN]; | |
| int cap[MAXN][MAXN], flow[MAXN][MAXN], cost[MAXN][MAXN]; | |
| int pre[MAXN], dis[MAXN]; | |
| bool used[MAXN][MAXN]; // used[i][j] == true means edge(i,j) is used | |
| void Initial(int N); | |
| void MCMF(int S, int T); | |
| bool SPFA(int S, int T); | |
| void UpdateFlow(int S, int T, int bottleneck); | |
| int main() | |
| { | |
| int N, M; | |
| while (scanf("%d", &N) && N) { | |
| scanf("%d", &M); | |
| Initial(N); | |
| int u, v, t; | |
| for (int i = 0; i < M; ++i) { | |
| scanf("%d %d %d", &u, &v, &t); | |
| cap[u][v] = cap[v][u] = 1; | |
| cost[u][v] = cost[v][u] = t; | |
| edge[u].push_back(v); | |
| edge[v].push_back(u); | |
| } | |
| MCMF(N, 1); | |
| } | |
| } | |
| void Initial(int N) | |
| { | |
| for (int i = 1; i <= N; ++i) edge[i].clear(); | |
| memset(cap, 0, sizeof(cap)); | |
| memset(flow, 0, sizeof(flow)); | |
| memset(cost, 0, sizeof(cost)); | |
| memset(used, 0, sizeof(used)); | |
| } | |
| void MCMF(int S, int T) | |
| { | |
| int min_cost = 0; | |
| int max_flow = 0; | |
| while (SPFA(S, T)) { | |
| UpdateFlow(S, T, 1); | |
| min_cost += dis[T]; | |
| ++max_flow; | |
| if (max_flow >= 2) break; | |
| } | |
| if (max_flow < 2) puts("Back to jail"); | |
| else printf("%d\n", min_cost); | |
| } | |
| bool SPFA(int S, int T) | |
| { | |
| fill(begin(dis), end(dis), INF); | |
| queue<int> Q; | |
| bool inQueue[MAXN] = {0}; | |
| dis[S] = 0; | |
| Q.push(S); | |
| inQueue[S] = true; | |
| while (!Q.empty()) { | |
| int cur = Q.front(); | |
| Q.pop(); | |
| inQueue[cur] = false; | |
| for (int nxt : edge[cur]) { | |
| if (flow[nxt][cur] > 0 && dis[cur] + (-cost[nxt][cur]) < dis[nxt]) { | |
| dis[nxt] = dis[cur] + (-cost[nxt][cur]); | |
| pre[nxt] = cur; | |
| if (!inQueue[nxt]) {inQueue[nxt] = true; Q.push(nxt);} | |
| } | |
| else if (!used[cur][nxt] && cap[cur][nxt] > flow[cur][nxt] && dis[cur] + cost[cur][nxt] < dis[nxt]) { | |
| dis[nxt] = dis[cur] + cost[cur][nxt]; | |
| pre[nxt] = cur; | |
| if (!inQueue[nxt]) {inQueue[nxt] = true; Q.push(nxt);} | |
| } | |
| } | |
| } | |
| return dis[T] != INF; | |
| } | |
| void UpdateFlow(int S, int T, int bottleneck) | |
| { | |
| for (int u = T; u != S; u = pre[u]) { | |
| flow[pre[u]][u] += bottleneck; | |
| flow[u][pre[u]] -= bottleneck; | |
| used[pre[u]][u] = used[u][pre[u]] = true; | |
| } | |
| } |
沒有留言:
張貼留言