題目鏈接

題意

給出一個n*m的酒店，每個點是一個房間，要將這個酒店的房間劃分成為兩塊（一塊無煙區，一塊吸煙區），相鄰的兩個房間之間有一條帶權邊，權值代表空氣鎖的面積，如果把這條邊給去掉，那么需要花費（空氣鎖的面積+開一個窗口傳食物）*1000元。問需要的最少花費是多少。要注意如果面積為0，則這條邊不能劃分。

思路

全場做的人不多，主要看題意比較難，看懂題意就會發現是裸的最小割，但是有個面積為0的坑點。這里的邊需要開的比較大，考慮到每次增加兩個點，就會使邊增加三條（不知道這樣想對不對），于是就開兩倍（還有兩倍雙向邊）。

#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> pii; const int INF = 0x3f3f3f3f; const int M = 1e3 + 11; const int N = 1e6 + 11; struct Edge {int u, v, nxt, cap; } edge[N*4]; int head[N], tot, id[M][M]; int cur[N], gap[N], dis[N], pre[N]; queue<int> que;void Add(int u, int v, int cap) {edge[tot] = (Edge) { u, v, head[u], cap }; head[u] = tot++;edge[tot] = (Edge) { v, u, head[v], cap }; head[v] = tot++; }void BFS(int T) {while(!que.empty()) que.pop();memset(dis, INF, sizeof(dis));memset(gap, 0, sizeof(gap));gap[0] = 1; dis[T] = 0;que.push(T);while(!que.empty()) {int u = que.front(); que.pop();for(int i = head[u]; ~i; i = edge[i].nxt) {int v = edge[i].v;if(dis[v] != INF) continue;dis[v] = dis[u] + 1;gap[dis[v]]++;que.push(v);}} }int ISAP(int S, int T, int n) {BFS(T);memcpy(cur, head, sizeof(cur));int i, flow, u = pre[S] = S, index, ans = 0;while(dis[S] < n) {if(u == T) {flow = INF, index = u;for(u = S; u != T; u = edge[cur[u]].v)if(edge[cur[u]].cap < flow) flow = edge[cur[u]].cap, index = u;for(u = S; u != T; u = edge[cur[u]].v)edge[cur[u]].cap -= flow, edge[cur[u]^1].cap += flow;u = index, ans += flow;}for(i = cur[u]; ~i; i = edge[i].nxt)if(dis[edge[i].v] == dis[u] - 1 && edge[i].cap) break;if(~i) {pre[edge[i].v] = u; cur[u] = i; u = edge[i].v;} else {if(--gap[dis[u]] == 0) break;int md = n + 1;for(i = head[u]; ~i; i = edge[i].nxt)if(edge[i].cap && dis[edge[i].v] < md) md = dis[edge[i].v], cur[u] = i;gap[dis[u] = md + 1]++;u = pre[u];}} return ans; }int main() {int t; scanf("%d", &t);while(t--) {memset(head, -1, sizeof(head));tot = 0;int n, m, sx, sy, ex, ey;scanf("%d%d", &n, &m);scanf("%d%d%d%d", &sx, &sy, &ex, &ey);int cnt = 0;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++) id[i][j] = ++cnt;for(int i = 0; i < n; i++) {for(int j = 0; j < m - 1; j++) {int cap; scanf("%d", &cap);if(cap) Add(id[i][j], id[i][j+1], cap + 1);}}for(int i = 0; i < n - 1; i++) {for(int j = 0; j < m; j++) {int cap; scanf("%d", &cap);if(cap) Add(id[i][j], id[i+1][j], cap + 1);}}printf("%d\n", ISAP(id[sx][sy], id[ex][ey], n * m) * 1000);} return 0; }

轉載于:https://www.cnblogs.com/fightfordream/p/7636624.html

總結

以上是生活随笔為你收集整理的Codeforces Gym101518H：No Smoking, Please（最小割）的全部內容，希望文章能夠幫你解決所遇到的問題。

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