• 欢迎光临~

网络流 24 题

开发技术 开发技术 2022-07-16 次浏览
  • P2756 飞行员配对方案问题

只要默认前面 (m) 个都是外国的,然后剩下的都是英国的,接着暴力建图跑 Dinic 即可。
貌似只需要弄一个源点 (0) 和汇点 (n+1) 即可。

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
const int N = 2e4 + 10;
int n, m, cnt = 1;
int head[N], dep[N];
bool vis[N];

struct Edge {
  int to, nxt, val;
} e[N];

void addEdge(int u, int v, int w) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  e[cnt].val = w;
  head[u] = cnt; return ;
}

bool check() {
  for (int i=0; i<=n+1; ++i) dep[i] = 0;
  dep[0] = 2; queue <int> sp; sp.push(0);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    for (int i=head[cur]; i; i=e[i].nxt) {
      int to = e[i].to;
      if (!dep[to] && e[i].val) {
        dep[to] = dep[cur] + 1, sp.push(to);
        if (to==n+1) return true;
      }
    }
  }
  return false;
}

int dfs(int cur, int Max) {
  if (cur==n+1) return Max;
  int increase = Max;
  for (int i=head[cur]; i&&increase; i=e[i].nxt) {
    int to = e[i].to;
    if (e[i].val && dep[to]==dep[cur]+1) {
      int res = dfs(to, min(increase, e[i].val));
      e[i].val -= res, e[i^1].val += res;
      if (!res) dep[to] = 0;
      increase -= res;
    }
  }
  return Max-increase;
}

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

int main() {
  read(m), read(n);
  while (1) {
    int u, v; read(u), read(v);
    if (u==-1 && v==-1) break;
    addEdge(u, v, inf);
    addEdge(v, u, 0);
  }
  for (int i=1; i<=m; ++i)
    addEdge(0, i, 1), addEdge(i, 0, 0);
  for (int i=m+1; i<=n; ++i)
    addEdge(i, n+1, 1), addEdge(n+1, i, 0);
  int ans = 0;
  while(check()) ans += dfs(0, inf);
  cout << ans << endl;
  for (int i=2; i<=cnt; i+=2) {
    if (!e[i^1].val) continue;
    if (!e[i].to || !e[i^1].to) continue;
    if (e[i].to==n+1) continue;
    if (e[i^1].to==n+1) continue;
    printf("%d %dn", e[i^1].to, e[i].to);
  }
  return 0;
}
  • P1251 餐巾计划问题

这道题最重要的是连边。
那么很显然的拆点技巧,将一天拆成服务和收工两个点,即 i+Ni,后前两个点。
那么源点为 0,汇点为 2*N+1

  • 要购买餐巾

显然从源点处购买,直接建边 add(0,i+N,inf,p)

  • 偷懒先不洗餐巾

显然直接延到下一天,add(i,i+1,inf,0)

  • 快洗

显然直接丢到 (m) 天后,add(i,i+N+m,inf,f)

  • 慢洗

同理丢到 (n) 天后,add(i,i+N+n,inf,s)

然后每一天要跑至少为 r[i] 的流量,直接源点连收工,汇点连服务。

然后跑一遍最小费用最大流即可。

nt 的地方:DFS 要标记 cur,数组不要开小。
要是写对了正解然后数组开小了那就真的是个 zz。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 2e3 + 10;
const int inf = 2e9;

int N, cnt = 1, head[MAXN*12];
int p, m, f, n, s, dist[MAXN*12];
bool inq[MAXN*2], vis[MAXN*2];
int cost;

struct Edge {
  int to, nxt, flow, val;
} e[MAXN*12];

void addEdge(int u, int v, int f, int w) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  e[cnt].flow = f, e[cnt].val = w;
  head[u] = cnt;

  e[++cnt].to = u;
  e[cnt].nxt = head[v];
  e[cnt].flow = 0, e[cnt].val = -w;
  head[v] = cnt; return ;
}

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

bool spfa() {
  for (int i=0; i<=2*N+1; ++i)
    dist[i] = inf, inq[i] = false;
  dist[0] = 0, inq[0] = true;
  queue <int> sp; sp.push(0);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    inq[cur] = false;
    for (int i=head[cur]; i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dist[to]>dist[cur]+e[i].val) {
        dist[to] = dist[cur] + e[i].val;
        if (!inq[to]) inq[to] = true, sp.push(to);
      }
    }
  }
  return dist[2*N+1] < inf;
}

int dfs(int cur, int Max) {
  if (cur == 2*N+1) { vis[cur] = true; return Max; }
  int increase = Max; vis[cur] = true;
  for (int i=head[cur]; i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if ((!vis[to] || to==MAXN) && e[i].flow && dist[to]==dist[cur]+e[i].val) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) continue;
      e[i].flow -= res, e[i^1].flow += res;
      cost += res * e[i].val, increase -= res;
    }
  }
  return Max-increase;
}

signed main() {
  cin >> N;
  for (int i=1; i<=N; ++i) {
    int r; cin >> r;
    addEdge(0, i, r, 0);
    addEdge(i+N, 2*N+1, r, 0);
  }
  cin >> p >> m >> f >> n >> s;
  // begin point: i
  // ending point: i+N
  for (int i=1; i<=N; ++i) {
    addEdge(0, i+N, inf, p);
    if (i<N) addEdge(i, i+1, inf, 0);
    if (i+m<=N) addEdge(i, i+N+m, inf, f);
    if (i+n<=N) addEdge(i, i+N+n, inf, s);
  }
  while (spfa()) {
    for (int i=0; i<=2*N+1; ++i) vis[i] = false;
    dfs(0, inf);
  }
  cout << cost << endl;
  return 0;
}
  • P4011 孤岛营救问题

这道题为什么要网络流啊。

难道不是直接暴力 BFS 寻找路径吗?

直接状压一下钥匙,然后每一次到达门就看有没有钥匙就可以了。

nt 的地方:x(x), y(y) 写成了 x(x), y(x) ... ...

#include <bits/stdc++.h>
using namespace std;

const int N = 11;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int n, m, p, k, s, door[N][N][N][N];
int cnt[N][N], key[N][N][N];
bool vis[N][N][1<<N];

struct spread {
  int x, y, Key, cost;
  spread(int x, int y, int Key, int cost):
    x(x), y(y), Key(Key), cost(cost) {}
  spread() {}
};

int keyset(int x, int y) {
  int S = 0;
  for (int i=1; i<=cnt[x][y]; ++i)
    S |= (1<<(key[x][y][i]-1));
  return S;
}

bool check(int x, int y, int k, int st) {
  if (x<1 || x>n) return false;
  if (y<1 || y>m) return false;
  if (k<0 || (k && !(st&(1<<(k-1))))) return false;
  return true;
}

int bfs() {
  int x = 1, y = 1;
  int S = keyset(x, y);
  queue <spread> que; que.push(spread(x, y, S, 0));
  vis[x][y][S] = true;
  while (!que.empty()) {
    spread cur = que.front(); que.pop();
    x = cur.x, y = cur.y, S = cur.Key;
    if (x==n && y==m) return cur.cost;
    for (int i=0; i<4; ++i) {
      int tox = x + dx[i], toy = y + dy[i];
      int Door = door[x][y][tox][toy];
      if (!check(tox, toy, Door, S)) continue;
      int to = S|keyset(tox, toy);
      if (vis[tox][toy][to]) continue;
      vis[tox][toy][to] = true;
      que.push(spread(tox, toy, to, cur.cost+1));
    }
  }
  return -1;
}

int main() {
  cin >> n >> m >> p >> k;
  while (k--) {
    int x, y, X, Y, G;
    cin >> x >> y >> X >> Y >> G;
    if (G) door[x][y][X][Y] = door[X][Y][x][y] = G;
    else door[x][y][X][Y] = door[X][Y][x][y] = -1;
  }
  cin >> s;
  while (s--) {
    int x, y, Q; cin >> x >> y >> Q;
    key[x][y][++cnt[x][y]] = Q;
  }
  cout << bfs() << endl;
  return 0;
}
  • P2764 最小路径覆盖问题

众所周知最小路径覆盖 (=) 顶点数 (-) 最大匹配数,这个是很显然的。

Proof:因为对于每一个点一开始都可以作为一条路径,所以一开始就有 (n) 条路径。因为每一次匹配相当于把两个点合并,所以路径条数相当于减掉了 (1),所以最大匹配数就是合并的个数,所以最后就是 (n-)最大匹配数。
又因为二分图可以网络流乱搞,所以路径覆盖也可以网络流乱搞。

所以正常的 trick,拆点跑最大流。
路径输出比较正常,直接在 DFS 的时候找到起始点然后记录路径即可。

#include <bits/stdc++.h>
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

const int N = 1e5 + 10;
const int inf = 1e9;

int n, m, s, t, cnt = 1;
int dep[N], head[N]; bool inq[N];
int cost, path[N]; bool vis[N];

struct Edge {
  int to, nxt, flow;
} e[N];

void addEdge(int u, int v, int f) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  e[cnt].flow = f; head[u] = cnt;

  e[++cnt].to = u;
  e[cnt].nxt = head[v];
  e[cnt].flow = 0; head[v] = cnt;
  return ;
}

bool check() {
  for (int i=0; i<=t; ++i)
    dep[i] = inf, inq[i] = false;
  dep[s] = 0; queue <int> sp;
  sp.push(s); inq[s] = true;
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    for (int i=head[cur]; i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dep[to]==inf) {
        dep[to] = dep[cur] + 1, sp.push(to);
      }
    }
  }
  return dep[t] ^ inf;
}

int dfs(int cur, int Max) {
  if (cur==t) return Max;
  int increase = Max;
  for (int i=head[cur]; i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if (e[i].flow && dep[to]==dep[cur]+1) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) { dep[to] = -1; continue; }
      e[i].flow -=  res, e[i^1].flow += res;
      path[cur] = to; if (cur) vis[to-n] = true;
      increase -= res;
    }
  }
  return Max-increase;
}

int main() {
  cin >> n >> m; t = 2*n+1;
  for (int i=1; i<=m; ++i) {
    int u, v; cin >> u >> v;
    addEdge(u, n+v, 1);
  }
  for (int i=1; i<=n; ++i) addEdge(s, i, 1);
  for (int i=1; i<=n; ++i) addEdge(i+n, t, 1);
  int ans = 0; while (check()) ans += dfs(s, inf);
  for (int i=1; i<=n; ++i) {
    if (vis[i]) continue;
    int cur = i; cout << i;
    while(path[cur] && path[cur]^t)
      cout << ' ' << path[cur]-n, cur = path[cur]-n;
    cout << endl;
  }
  cout << n-ans << endl;
  return 0;
}
  • P4016 负载平衡问题

听名字还挺高大上的。

其实就是个卡牌游戏啊,只不过每一次只可以交换环上相邻两个。
那么直接断环成链,拿原数减掉最后的固定答案然后前缀和加到 ans

顺带卡了下常,12ms 最优解 Rank1。

#include <stdio.h>
int n, sum, ans, a[110], Sum[110];

int abs(int x) { return x>0? x:-x; }

void qsort(int l, int r) {
  int mid = Sum[(l+r)>>1];
  int i=l, j=r;
  do {
    while (Sum[i]<mid) ++i;
    while (Sum[j]>mid) --j;
    if(i<=j) {
      int u=Sum[i]; Sum[i]=Sum[j]; Sum[j]=u;
      i++, j--;
    }
  } while (i<=j);
  if (l<j) qsort(l, j);
  if (i<r) qsort(i, r);
  return ;
}

int main() {
  scanf("%d", &n);
  for (int i=1; i<=n; ++i)
    scanf("%d", &a[i]), sum += a[i];
  sum /= n;
  for (int i=1; i<=n; ++i)
    Sum[i] = Sum[i-1]+a[i]-sum, a[i] = Sum[i];
  qsort(1, n); int mid = n/2+1;
  for (int i=1; i<=n; ++i)
    ans += abs(Sum[mid]-Sum[i]);
  printf("%dn", ans);
  return 0;
}
  • UVA11380 Down Went The Titanic

简单题。

首先看到点有限制,直接拆点。

那么因为没有给出单源点和汇点,分别建一个。

接着可以将 * 视为连向源点,所以边权为 (1)
同理 # 视为连向汇点,边权为限制 (p)

然后因为 . 只能踩一次,所以拆成两个点,两个点之间的限制为 (1)
@ 可以踩无数次,所以连 INF。

接着因为周边四个点都可以扩展到(除起始点和水显然不可以扩展)。
所以连容量为 INF 的边。

然后跑一遍最大流。

记得多测 cnt 要赋成 (1) 而不是 (0)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int inf = 1e9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n, m, p, s, t, cnt = 1;
int dep[N], head[N]; char ch[40][40];

struct Edge {
  int to, nxt, flow;
} e[N];

void addEdge(int u, int v, int f) {
  e[++cnt].to = v, e[cnt].nxt = head[u];
  e[cnt].flow = f, head[u] = cnt;
  e[++cnt].to = u, e[cnt].nxt = head[v];
  e[cnt].flow = 0, head[v] = cnt;
}

bool check(int x, int y) {
  return x<1 || x>n || y<1 || y>m;
}

void init() {
  cnt = 1; t = 2*n*m + 1;
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j) cin >> ch[i][j];
  memset(head, -1, sizeof head);
  return ;
}

int id(int x, int y) { return (x-1)*m+y; }
bool spfa() {
  for (int i=s; i<=t; ++i) dep[i] = inf;
  dep[s] = 0; queue <int> sp; sp.push(s);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    for (int i=head[cur]; ~i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dep[to]==inf) {
        dep[to] = dep[cur] + 1, sp.push(to);
      }
    }
  }
  return dep[t]^inf;
}

int dfs(int cur, int Max) {
  if (cur==t) return Max;
  int increase = Max;
  for (int i=head[cur]; ~i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if (e[i].flow && dep[to]==dep[cur]+1) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) continue;
      e[i].flow -= res, e[i^1].flow += res;
      increase -= res;
    }
  }
  return Max-increase;
}

int main() {
  while (scanf("%d%d%d", &n, &m, &p) != EOF) {
    init(); int siz = n*m;
    for (int i=1; i<=n; ++i) {
      for (int j=1; j<=m; ++j) {
        if (ch[i][j] == '~') continue;
        if (ch[i][j] == '*') addEdge(s, id(i,j), 1);
        if (ch[i][j] == '.') addEdge(id(i,j), id(i,j)+siz, 1);
        if (ch[i][j] == '#') addEdge(id(i,j), t, p);
        for (int k=0; k<4; ++k) {
          int tox = i+dx[k], toy = j+dy[k];
          if (check(tox, toy)) continue;
          if (ch[tox][toy] == '*' || ch[tox][toy] == '~') continue;
          if (ch[i][j] == '.') addEdge(id(i,j)+siz, id(tox, toy), inf);
          else addEdge(id(i,j), id(tox, toy), inf);
        }
      }
    }
    int ans = 0;
    while (spfa()) ans += dfs(s, inf);
    cout << ans << endl;
  }
  return 0;
}
  • P3965 循环格

这题也是个拆点模板。
首先 S 连向出点,T 连向入点,默认已经拆完点。
所以因为要使得成为循环格,所以要进行两两之间点的匹配。
即入度、出度均为 (1)

所以跑二分图匹配最小费用即可。
建边的 value 只需要看当前点实际指的方向是否是枚举的方向。
如果是费用为 (0),否则为 (1)

最后要注意:cnt 要赋成 (1)!!11

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;
const int inf = 114514;

int n, m, s, t, cnt = 1, cost;
int dist[N], head[N];
bool vis[N], inq[N];
char Map[20][20]; int To[20][20];

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

struct Edge {
  int to, nxt, flow, val;
} e[N];

void addEdge(int u, int v, int f, int w) {
  e[++cnt].to = v, e[cnt].nxt = head[u];
  e[cnt].flow = f, e[cnt].val = w, head[u] = cnt;
  e[++cnt].to = u, e[cnt].nxt = head[v];
  e[cnt].flow = 0, e[cnt].val = -w, head[v] = cnt;
  return ;
}

bool spfa() {
  for (int i=s; i<=t; ++i)
    inq[i] = false, dist[i] = inf;
  dist[s] = 0, inq[s] = true;
  queue <int> sp; sp.push(s);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    inq[cur] = false;
    for (int i=head[cur]; ~i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dist[to]>dist[cur]+e[i].val) {
        dist[to] = dist[cur] + e[i].val;
        if (!inq[to]) { inq[to] = true; sp.push(to); }
      }
    }
  }
  return dist[t]^inf;
}

int dfs(int cur, int Max) {
  vis[cur] = true;
  if (cur==t) return Max;
  int increase = Max;
  for (int i=head[cur]; ~i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if ((!vis[to]||to==t) && e[i].flow && dist[to]==dist[cur]+e[i].val) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) continue;
      e[i].flow -= res, e[i^1].flow += res;
      increase -= res, cost += res * e[i].val;
    }
  }
  return Max-increase;
}

int id(int x, int y) { return (x-1)*m+y; }

int main() {
  memset(head, -1, sizeof head);
  cin >> n >> m; t = 2*n*m + 1;
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j) {
      cin >> Map[i][j];
      if (Map[i][j]=='L') To[i][j] = 0;
      if (Map[i][j]=='R') To[i][j] = 1;
      if (Map[i][j]=='U') To[i][j] = 2;
      if (Map[i][j]=='D') To[i][j] = 3;
    }
  for (int i=1; i<=n; ++i) {
    for (int j=1; j<=m; ++j) {
      for (int k=0; k<4; ++k) {
        int tox = i+dx[k], toy = j+dy[k];
        if (tox<1) tox = n; if (tox>n) tox = 1;
        if (toy<1) toy = m; if (toy>m) toy = 1;
        addEdge(id(i,j)+n*m, id(tox, toy), 1, k!=To[i][j]);
      }
    }
  }
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j) {
      addEdge(s, id(i,j)+n*m, 1, 0);
      addEdge(id(i,j), t, 1, 0);
    }
  int ans = 0;
  while (spfa()) {
    for (int i=s; i<=t; ++i) vis[i] = false;
    ans += dfs(s, inf);
  }
  cout << cost << endl;
  return 0;
}
程序员灯塔
转载请注明原文链接:网络流 24 题
喜欢 (0)