网络流24题

07/12 09:24
阅读数 43


网络流24题


前言

按照\(\text{luogu}\)题号排序


餐巾计划问题

知识点:拆点,最小费用最大流。

建立超级源点,超级汇点。
将一天拆为获取脏餐巾消耗净餐巾两部分,按以下策略建图:

  1. 超级源 向每天 获取脏餐巾 连边,容量为本日需求,费用为0。
  2. 每日 消耗净餐巾超级汇 连边,容量为本日需求,费用为0。
  3. 每日 获取脏餐巾 向次日 获取脏餐巾 连边,容量无限,费用为0。
    代表 可将脏餐巾 无限量留至次日。
  4. 每日 获取脏餐巾快洗天数后 连边,容量无限,费用为 快洗费用
    代表将本日脏餐巾快洗,在指定天数后 获取净餐巾。
  5. 每日 获取脏餐巾慢洗天数后 连边,容量无限,费用为 慢洗费用
    代表将本日脏餐巾慢洗,在指定天数后 获取净餐巾。
  6. 超级源 向每日 消耗净餐巾 连边,容量无限,费用为 购买费用
    代表直接购买新餐巾。

按上述策略建图,显然汇点必可满流。
进行最小费用最大流算法,汇点满流代表 每日需求均可满足。
求得满流时最小费用,即为答案。

//知识点:网络流
/*
By:Luckyblock
i<=N:获取脏餐巾, i>N:消耗净餐巾
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <queue>
#define min std::min
#define int long long
const int MARX = 2e5 + 10;
const int INF = 2e9 + 10;
//===========================================================
struct Edge
{
    int u, v, w, cost, ne;
} e[MARX << 1];
int N, S, T, edgenum = - 1, head[MARX];
int mincost, dis[MARX], flow[MARX];
int pre[MARX], pren[MARX];
bool vis[MARX];
//===========================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; ! isdigit(ch); ch = getchar()) if(ch == '-') f = - 1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void AddEdge(int u, int v, int w, int cost)
{
    e[++ edgenum].u = u, e[edgenum].v = v, e[edgenum].w = w, e[edgenum].cost = cost;
    e[edgenum].ne = head[u], head[u] = edgenum;

    e[++ edgenum].u = v, e[edgenum].v = u, e[edgenum].w = 0, e[edgenum].cost = - cost;
    e[edgenum].ne = head[v], head[v] = edgenum;
}
bool Spfa(int S, int T)
{
    std :: queue <int> q;
    memset(dis, 0x7f, sizeof(dis));
    memset(flow, 0x7f, sizeof(flow));
    memset(vis, 0, sizeof(vis));
    q.push(S); vis[S] = 1; dis[S] = 0, pren[T] = - 1;

    while(! q.empty())
    {
      int now = q.front(); q.pop(); vis[now] = false;
      for(int i = head[now]; i != - 1; i = e[i].ne)
        if(e[i].w > 0 && dis[e[i].v] > dis[now] + e[i].cost)
        {
          dis[e[i].v] = dis[now] + e[i].cost;
          pren[e[i].v] = now, pre[e[i].v] = i;
          flow[e[i].v] = min(flow[now], e[i].w);
          if(! vis[e[i].v]) vis[e[i].v] = true, q.push(e[i].v);
        }
    }
    return (pren[T] != - 1);
}
void EK(int S, int T)
{
    while(Spfa(S, T))
    {
      int now = T; mincost += flow[T] * dis[T];
      for(int now = T; now != S; now = pren[now])
      e[pre[now]].w -= flow[T],
      e[pre[now] ^ 1].w += flow[T];
    }
}
//===========================================================
signed main()
{
    N = read(), S = 0, T = 2 * N + 1;
    memset(head, - 1, sizeof(head));
    for(int i = 1; i <= N; i ++)
    {
      int Need = read();
      AddEdge(S, i, Need, 0);
      AddEdge(i + N, T, Need, 0);
    }
    int NewCost = read(), FastTime = read(), FastCost = read(), SlowTime = read(), SlowCost = read();
    for(int i = 1; i <= N; i ++)
    {
      if(i + 1 <= N) AddEdge(i, i + 1, INF, 0);
      if(i + FastTime <= N) AddEdge(i, i + N + FastTime, INF, FastCost);
      if(i + SlowTime <= N) AddEdge(i, i + N + SlowTime, INF, SlowCost);
      AddEdge(S, i + N, INF, NewCost);
    }
    EK(S, T);
    printf("%lld", mincost);
    return 0;
}

CTSC 1999家园 / 星际转移问题

嫦娥啊,你看到了吗!

分层图 + 网络流

先用并查集,将可互达的点合并,判断是否有解。
只要起点和终点之间联通,则必有解。

时间维不便处理,由于数据范围较小,考虑按照时间建分层图。
每一层包含 \(n + 2\)个节点 (空间站及地月)。
求答案时 从大到小枚举时间,并根据当前时间 扩充分层图。

建立超级源汇,对于每个时间点,按照下列策略建图:

  1. 超级源本层地球 连边,容量无限。
  2. 本层月球超级汇 连边,容量无限。
  3. 枚举每一艘飞船,获得其上个时间点位置 x 和 当前位置 y。
    上层 x本层 y 连边,容量为此飞船容量。
  4. 上层各点本层对应点 连边,容量无限。
    代表乘客在此点暂时等候。

对于每个时间点,求得对应分层图的最大流。
若最大流大于等于人数,则当前时间内可完成运输。

每次扩充分层图后,只需要在残量网络跑Dinic,就可得到新的最大流,复杂度较EK更低。

//知识点:分层图,网络流  
/*
By:Luckyblock
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <queue>
#define min std::min
#define ll long long
const int MARX = 110;
const int MARX1 = 1e6 + 10;
const int INF = 2e9 + 10;
//===========================================================
struct Edge
{
    int u, v, w, ne;
} e[MARX1 << 1];
int N, M, K, S, T, edgenum = - 1, head[MARX1], Dep[MARX1];
int maxp[MARX], num[MARX], pos[MARX][MARX]; //描述飞船
int Father[MARX];
int MaxFlow;
//===========================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; ! isdigit(ch); ch = getchar()) if(ch == '-') f = - 1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void AddEdge(int u, int v, int w)
{
    e[++ edgenum].u = u, e[edgenum].v = v, e[edgenum].w = w;
    e[edgenum].ne = head[u], head[u] = edgenum;
    e[++ edgenum].u = v, e[edgenum].v = u, e[edgenum].w = 0;
    e[edgenum].ne = head[v], head[v] = edgenum;
}
int Find(int now) {return Father[now] == now ? now : Father[now] = Find(Father[now]);}
void Unico(int x, int y)
{
    x = Find(x), y = Find(y);
    if(x != y) Father[x] = y;
}
bool Bfs()
{
    std :: queue <int> Q;
    memset(Dep, 0 ,sizeof(Dep));
    Dep[S] = 1; Q.push(S);

    do
    {
      int u = Q.front(); Q.pop();
      if(u == T) return true;
      for(int i = head[u]; i != - 1; i = e[i].ne)
        if(e[i].w > 0 && Dep[e[i].v] == 0)
          Dep[e[i].v] = Dep[u] + 1,
          Q.push(e[i].v);
    }
    while(! Q.empty());
    return false;
}
int Dfs(int u, int dis)
{
    if(u == T) return dis;
    for(int i = head[u]; i != - 1; i = e[i].ne)
      if(Dep[e[i].v] == Dep[e[i].u] + 1 && e[i].w)
      {
        int ret = Dfs(e[i].v, min(dis, e[i].w));
        if(ret > 0)
        {
          e[i].w -= ret, e[i ^ 1].w += ret;
          return ret;
        }
      }
    return 0;
}
int Dinic()
{
    while(Bfs()) while(int ret = Dfs(S, INF)) MaxFlow += ret;
    return MaxFlow;
}
//===========================================================
int main()
{
    N = read(), M = read(), K = read(), S = 0, T = MARX1 - 2;
    memset(head, - 1, sizeof(head));  
    for(int i = 1; i <= N + 2; i ++) Father[i] = i;
    for(int i = 1; i <= M; i ++)
    {
      maxp[i] = read(), num[i] = read();
      for(int j = 0; j < num[i]; j ++)
      {
        pos[i][j] = read();
        if(pos[i][j] == 0) pos[i][j] = N + 1;
        if(pos[i][j] == - 1) pos[i][j] = N + 2;
        if(j != 0) Unico(pos[i][j - 1], pos[i][j]);
      }
    }
    if(Find(N + 1) != Find(N + 2)) {printf("0"); return 0;}

    for(int Ans = 1; ; Ans ++)
    {
      AddEdge(S, (Ans - 1) * (N + 2) + N + 1, INF);
      AddEdge(Ans * (N + 2) + N + 2, T, INF);
      for(int i = 1; i <= M; i ++)
      {
        int x = (Ans - 1) % num[i], y = Ans % num[i];
        if(pos[i][x] == N + 2) continue;
        x = (Ans - 1) * (N + 2) + pos[i][x];
        y = Ans * (N + 2) + pos[i][y];
        AddEdge(x, y, maxp[i]);
      }
      for(int i = 1; i <= N + 1; i ++) AddEdge((Ans - 1) * (N + 2) + i, Ans * (N + 2) + i, INF);
      if(Dinic() >= K) {printf("%d\n", Ans); return 0;}
    }
    return 0;
}

飞行员配对方案问题

为什么不写Dinic?这是对网络流24题的侮辱!
我本想这样大声呵斥她,但匈牙利真的太好写了。

二分图匹配模板, 使用匈牙利算法。
题目要求输出方案, 由于有spj输出任意一组即可。
详见注释。

//知识点:二分图匹配 , 匈牙利算法
/*
By:Luckyblock
*/
#include <cstdio>
#include <cstring>
#include <ctype.h>
#define ll long long
const int MARX = 1e3 + 10;
const int MARX1 = 1e7 + 10;
//=============================================================
struct edge
{
    int u, v, ne;
}e[MARX1];
int N, M, E, num, ans, head[MARX], match[MARX];
bool vis[MARX];
//=============================================================
inline int read()
{
    int s = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') s = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 1) + (w << 3) + (ch ^ '0');
    return s * w;
}
void add(int u, int v)
{
    e[++ num].u = u, e[num].v = v;
    e[num].ne = head[u], head[u] = num;
}
bool dfs(int u)//匈牙利算法配对
{
    for(int i = head[u]; i; i = e[i].ne)//枚举能到达的点
      if(! vis[e[i].v])//在此轮配对中未被访问
      {
        vis[e[i].v] = 1;
        if(! match[e[i].v] || dfs(match[e[i].v]))//若可配对
        {
          match[e[i].v] = u; //更新
          return 1;
        }
      }
    return 0;
}
//=============================================================
signed main()
{
    N = read(), M = read();
    while(1)
    {
      int u = read(), v = read();
      if(u == -1 && v == -1) break;
      add(u, v);
    }

    for(int i = 1; i <= N; i ++)//枚举一组中的N个点
    {
      memset(vis, 0, sizeof(vis));//初始化
      if(dfs(i)) ans ++;//可以将i点 加入匹配中
    }
    printf("%d\n", ans);
    for(int i = N + 1; i <= M; i ++)//输出方案
      if(match[i]) printf("%d %d\n", match[i], i);
}


软件补丁问题

网络流24题不用网络流解不是很正常吗?

用二进制状压维护bug的修复情况,
答案 即为到达全部修复状态 所需的最短时间。
将最短路中的节点替换为状态,使用spfa算法即可。

//知识点:状压 + 最短路
/*
By:Luckyblock
*/
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define ll long long
const int MARX = (1 << 22);
//=============================================================
struct Patch
{
    int b1, b2, f1, f2, time;
} patch[110];
int N, M, All, INF, dis[MARX];
bool vis[MARX];
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void Spfa()
{
    std :: queue <int> q;
    memset(dis, 0x3f, sizeof(dis));
    INF = dis[All]; dis[All] = 0; q.push(All);

    while(! q.empty())
    {
      int u = q.front(); vis[u] = false; q.pop();
      for(int i = 1; i <= M; i ++)
        if((u & patch[i].b1) == patch[i].b1 && (u & patch[i].b2) == 0)
        {
          int v = ((u | patch[i].f1) | patch[i].f2) ^ patch[i].f1;
          if(dis[u] + patch[i].time < dis[v])
          {
            dis[v] = dis[u] + patch[i].time;
            if(! vis[v]) vis[v] = true, q.push(v);
          }
        }
    }
}
//=============================================================
int main()
{
    N = read(), M = read(); All = (1 << N) - 1;
    for(int i = 1; i <= M; i ++)
    {
      patch[i].time = read();
      char b[30], f[30]; scanf("%s", b), scanf("%s", f);
      for(int j = 0; j < N; j ++)
        if(b[j] == '+') patch[i].b1 |= (1 << j);
        else if(b[j] == '-') patch[i].b2 |= (1 << j);
      for(int j = 0; j < N; j ++)
        if(f[j] == '-') patch[i].f1 |= (1 << j);
        else if(f[j] == '+') patch[i].f2 |= (1 << j);
    }
    Spfa();
    if(dis[0] == INF) printf("0");
    else printf("%d", dis[0]);
    system("pause");
    return 0;
}

太空飞行计划问题

将实验看做正权点,权值为奖金,仪器看做负权点,权值为价值的相反数。
从各实验 向 此实验所需的各仪器连边,则本题转化为:

给定一有向图,点有点权,
选择一个子图,若选择了一个点就必须选择 后继所有点。
最大化点权和。

即为 最大权闭合子图问题。

建立超级源汇,按照下列策略建边:

  1. 超级源各实验 连边, 权值为 奖金数。
  2. 各实验此实验所需的各仪器 连边,权值无限。
  3. 各仪器超级汇 连边,权值为 仪器价格的绝对值。

求得最小割,答案即为 奖金总和 - 最小割。

?为什么是正确的呢 证明
暂时没看明白,挖个坑以后再填。

//知识点:最大权闭合图,最小割
/*
By:Luckyblock
*/
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define ll long long
const int INF = 2e9 +10;
const int MARX = 1e5 + 10;
//=============================================================
struct Edge
{
    int v, w, ne;
} e[MARX << 1];
int N, M, S, T, ans, edgenum = 1, head[MARX];
int Dep[MARX], cur[MARX];
bool flag;
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    if(ch == '\r'|| ch == '\n') flag = true;
    return f * w;
}
void AddEdge(int u, int v, int w)
{
    e[++ edgenum].v = v, e[edgenum].w = w;
    e[edgenum].ne = head[u], head[u] = edgenum;
    e[++ edgenum].v = u, e[edgenum].w = 0;
    e[edgenum].ne = head[v], head[v] = edgenum;
}
bool Bfs()
{
    std :: queue <int> q;
    memset(Dep, 0, sizeof(Dep));
    Dep[S] = 1; q.push(S);

    do
    {
      int u = q.front(); q.pop();
      for(int i = head[u]; i; i = e[i].ne)
        if(e[i].w > 0 && Dep[e[i].v] == 0)
          Dep[e[i].v] = Dep[u] + 1,
          q.push(e[i].v);
    } 
    while (! q.empty());
    return Dep[T];
}
int Dfs(int u, int dis)
{
    if(u == T) return dis;
    for(int i = cur[u]; i; i = e[i].ne)
      if(Dep[e[i].v] == Dep[u] + 1 && e[i].w)
      {
        int ret = Dfs(e[i].v, std :: min(dis, e[i].w));
        if(ret > 0)
        {
          e[i].w -= ret, e[i ^ 1].w += ret;
          return ret;
        }
      }
    return 0;
}
int Dinic()
{
    int ans = 0;
    while(Bfs())
    {
      for(int i = S; i <= T; i ++) cur[i] = head[i];
      while(int ret = Dfs(S, INF)) ans += ret;
    }
    return ans;
}
//=============================================================
int main()
{ 
    M = read(), N = read(), S = 0, T = 514;
    for(int i = 1, val; i <= M; i ++)
    {
      val = read(); ans += val; flag = false;
      AddEdge(S, i, val);
      while(! flag) val = read(), AddEdge(i, val + M, INF);
    }
    for(int i = 1, val; i <= N; i ++) val = read(), AddEdge(i + M, T, val);

    ans -= Dinic();
    for(int i = 1; i <= M; i ++) if(Dep[i] > 0) printf("%d ", i);
    printf("\n");
    for(int i = 1; i <= N; i ++) if(Dep[i + M] > 0) printf("%d ", i);
    printf("\n%d", ans);
    system("pause");
    return 0;
}

试题库问题

首先建立超级源汇,源点与试题相连,汇点与类型相连,对应试题与对应类型相连。

考虑边的容量:

  • 一道题只可有一个,则源点和试题 边容量为 1。
  • 一道题只能满足一种类型,则试题和类型 边容量为 1。
  • 需要满足的类型是有多个的,则类型与汇点 边容量为 所需类型的数量。

使用最大流算法,使得向汇点流满,
此时遍历代表题型的各点连接题目的边。
若一条边权值不为 0, 说明对应题目为该题型。

//知识点:网络流
/*
By:Luckyblock
*/
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define ll long long
const int INF = 2e9 + 10;
const int MARX = 1e4 + 10;
//=============================================================
struct Edge
{
    int v, w, ne;
} e[MARX << 3];
int K, N, M, S, T, edgenum = 1, head[MARX];
int Dep[MARX], cur[MARX];
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void AddEdge(int u, int v, int w)
{
    e[++ edgenum].v = v, e[edgenum].w = w;
    e[edgenum].ne = head[u], head[u] = edgenum;
    e[++ edgenum].v = u, e[edgenum].w = 0;
    e[edgenum].ne = head[v], head[v] = edgenum;
}
bool Bfs()
{
    std :: queue <int> q;
    memset(Dep, 0, sizeof(Dep));
    Dep[S] = 1; q.push(S);

    do
    {
      int u = q.front(); q.pop();
      for(int i = head[u]; i; i = e[i].ne)
        if(e[i].w > 0 && Dep[e[i].v] == 0)
          Dep[e[i].v] = Dep[u] + 1,
          q.push(e[i].v);
    } 
    while (! q.empty());
    return Dep[T];
}
int Dfs(int u, int dis)
{
    if(u == T) return dis;
    for(int i = cur[u]; i; i = e[i].ne)
      if(Dep[e[i].v] == Dep[u] + 1 && e[i].w)
      {
        int ret = Dfs(e[i].v, std :: min(dis, e[i].w));
        if(ret > 0)
        {
          e[i].w -= ret, e[i ^ 1].w += ret;
          return ret;
        }
      }
    return 0;
}
int Dinic()
{
    int ans = 0;
    while(Bfs())
    {
      for(int i = 0; i <= T; i ++) cur[i] = head[i];
      while(int ret = Dfs(S, INF)) ans += ret;
    }
    return ans;
}
//=============================================================
int main()
{
    K = read(), N = read(), S = 0, T = MARX - 10;
    for(int i = 1; i <= K; i ++) 
    {
      int Need = read(); M += Need;
      AddEdge(i, T, Need);
    }
    for(int i = 1; i <= N; i ++)
    {
      int u = i + K, p = read(), v;
      for(int j = 1; j <= p; j ++) v = read(), AddEdge(u, v, 1);
      AddEdge(S, u, 1);
    }
    if(Dinic() != M) {printf("No Solution!"); return 0;}
    for(int i = 1; i<= K; putchar('\n'), i ++)
    {
      printf("%d: ", i);
      for(int j = head[i]; j; j = e[j].ne)
        if(e[j].w) printf("%d ", e[j].v - K);
    }
    system("pause");
    return 0;
}

魔术球问题

对于一个进来的编号的球,他有两种情况:

  1. 放在某个和他组成平方数的球的后面。
  2. 独立门户。

以每一个珠子为点,若满足条件(编号相加为平方数)就两两连边。
为了符合上述情况, 只向编号比自己小的球连边。
当新点加入后 有增广路出现,说明新球会放置在之前的球之上。
否则新球将加入一根新柱。


在增广时 使用链式储存每个点的后继。

//知识点:最大流
/*
By:Luckyblock
*/
#include <queue>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define ll long long
const int INF = 2e9 + 10;
const int MARX = 1e5 + 10;
//=============================================================
struct Edge
{
    int v, w, ne;
} e[MARX << 1];
int N, M, S, T, BallNum, edgenum = 1, head[MARX];
int Dep[MARX], cur[MARX];
int Next[MARX], Head[MARX];
bool vis[MARX];
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void AddEdge(int u, int v, int w)
{
    e[++ edgenum].v = v, e[edgenum].w = w;
    e[edgenum].ne = head[u], head[u] = edgenum;
    e[++ edgenum].v = u, e[edgenum].w = 0;
    e[edgenum].ne = head[v], head[v] = edgenum;
}
bool Bfs()
{
    std :: queue <int> q;
    memset(Dep, 0, sizeof(Dep));
    Dep[S] = 1; q.push(S);

    do
    {
      int u = q.front(); q.pop();
      for(int i = head[u]; i; i = e[i].ne)
        if(e[i].w > 0 && Dep[e[i].v] == 0)
          Dep[e[i].v] = Dep[u] + 1,
          q.push(e[i].v);
    }
    while (! q.empty());
    return Dep[T];
}
int Dfs(int u, int dis)
{
    if(u == T) return dis;
    for(int i = cur[u]; i; i = e[i].ne)
      if(Dep[e[i].v] == Dep[u] + 1 && e[i].w)
      {
        int ret = Dfs(e[i].v, std :: min(dis, e[i].w));
        if(ret > 0)
        {
          e[i].w -= ret, e[i ^ 1].w += ret;
          if(e[i].v != T) Next[u >> 1] = (e[i].v >> 1);
          return ret;
        }
      }
    return 0;
}
int Dinic()
{
    int ans = 0;
    while(Bfs())
    {
      for(int i = S; i <= T; i ++) cur[i] = head[i];
      while(int ret = Dfs(S, INF)) ans += ret;
    }
    return ans;
}
//=============================================================
int main()
{
    N = read(), S = 0, T = (int) (5e4 + 10);
    for(int used = 0; used <= N; )
    {
      BallNum ++;
      AddEdge(S, BallNum << 1, 1), 
      AddEdge((BallNum << 1 ) | 1, T, 1);
      for(int i = sqrt(BallNum) + 1; i * i < 2 * BallNum; i ++)
        AddEdge((i * i - BallNum) << 1, (BallNum << 1) | 1, 1);
      int ret = Dinic();
      if(! ret) Head[++ used] = BallNum; //单球套柱, 住上的第一个球
    }
    printf("%d\n", -- BallNum);
    for(int i = 1; i <= N; i ++) //链式遍历
    {
      int x = Head[i]; vis[x] = true;
      for(; x; x = Next[x], vis[x] = true) printf("%d ", x);
      putchar('\n');
    }
    system("pause");
    return 0;
}

最长不下降子序列问题

知识点:拆点, 最大流

  • 第一问:最长不下降子序列的长度 \(s\)\(O(n^2)\) 暴力即可。
    \(f_i\)为以\(i\)结尾的 最长不下降子序列 的最长长度。
    有:\(f_i = \max(f_j) +1 (j<i,x_j\le x_i)\)
    求得答案,并保存\(f\)以备后用。


  • 第二问:求长度为\(s\)的 不下降子序列 个数,一个数只能选一次。
    一个不下降子序列 的贡献为1,
    在网络流中相当于 一条从源至汇的 流量为1的弧。
    考虑如何建图,满足上述要求。


    将数列映射为n个点,一个点的贡献为1,考虑拆点,将点\(i\)拆为\(i_1,i_2\)
    按下列策略连边:

    1. 从源点向\(f_i = 1\) 的点连边,容量为1。
    2. \(i_1\)\(i_2\)连边,容量为1,表示一个点只可做出一次贡献。
    3. 对于一对\(i,j\),若满足\(x_i\ge x_j\)\(f_i = f_j +1\),从\(j_2\)\(i_1\)连边,容量为1。
    4. 从满足\(f_i = s\)\(i_y\)向汇点连边,容量为1。

    求得最大流,即为答案。

  • 第三问:求长度为\(s\)的 不同的 不下降子序列个数,允许多次使用\(x_1,x_n\)
    解除了\(x_1,x_n\)的选择限制。
    在第二问中,用拆点后容量为1的边 代表限制,
    \(<S, 1_1>,<1_1,1_2>,<n_1,n_2>,<n_2,T>\)的容量变为\(\inf\)即可。


    经过第二问处理后,得到了一个残量网络。
    在此基础上 添加上述四条边,再求得一次最大流。
    由最大流算法的性质知,显然第三问答案 = 第二问答案 + 最大流。

//֪知识点:拆点, 最大流
/*
By:Luckyblock
*/
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define ll long long
const int INF = 2e9 + 10;
const int MARX = 1e5 + 10;
//=============================================================
struct Edge
{
    int v, w, ne;
} e[MARX << 3];
int N, M, S, T, edgenum = 1, head[MARX],Dep[MARX];
int ans1, ans2, Num[MARX], f[MARX];
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void AddEdge(int u, int v, int w)
{
    e[++ edgenum].v = v, e[edgenum].w = w;
    e[edgenum].ne = head[u], head[u] = edgenum;
    e[++ edgenum].v = u, e[edgenum].w = 0;
    e[edgenum].ne = head[v], head[v] = edgenum;
}
bool Bfs()
{
    std :: queue <int> q;
    memset(Dep, 0, sizeof(Dep));
    Dep[S] = 1; q.push(S);

    do
    {
      int u = q.front(); q.pop();
      for(int i = head[u]; i; i = e[i].ne)
        if(e[i].w > 0 && Dep[e[i].v] == 0)
          Dep[e[i].v] = Dep[u] + 1,
          q.push(e[i].v);
    } 
    while (! q.empty());
    return Dep[T];
}
int Dfs(int u, int dis)
{
    if(u == T) return dis;
    for(int i = head[u]; i; i = e[i].ne)
      if(Dep[e[i].v] == Dep[u] + 1 && e[i].w)
      {
        int ret = Dfs(e[i].v, std :: min(dis, e[i].w));
        if(ret > 0)
        {
          e[i].w -= ret, e[i ^ 1].w += ret;
          return ret;
        }
      }
    return 0;
}
int Dinic()
{
    int ans = 0;
    while(Bfs()) while(int ret = Dfs(S, INF + 10)) ans += ret;
    return ans;
}
//=============================================================
int main()
{
    N = read(), S = 0, T = N + N + 1;
    if(N == 1) {printf("1\n1\n1\n"); return 0;}
    for(int i = 1; i <= N; i ++) Num[i] = read();
    for(int i = 1; i <= N; i ++)
    {
      for(int j = 1; j < i; j ++)
        if(Num[j] <= Num[i] && f[j] > f[i])
          f[i] = f[j];
      f[i] ++, ans1 = std :: max(ans1, f[i]); 
    }
    printf("%d\n", ans1);

    for(int i = 1; i <= N; i ++) AddEdge(i, i + N, 1);
    for(int i = 1; i <= N; i ++) if(f[i] == 1) AddEdge(S, i, 1);
    for(int i = 1; i <= N; i ++) if(f[i] == ans1) AddEdge(i + N, T, 1);
    for(int i = 1; i <= N; i ++)
      for(int j = 1; j < i; j ++)
        if(Num[j] <= Num[i] && f[j] == f[i] - 1)
          AddEdge(j + N, i, 1);
    printf("%d\n", (ans2 = Dinic()));

    AddEdge(1, 1 + N, INF), AddEdge(S, 1, INF);
    if(f[N] == ans1) AddEdge(N + N, T, INF), AddEdge(N, N + N, INF);
    printf("%d\n", ans2 + Dinic());
    system("pause");
    return 0;
}

航空路线问题

求从起点到终点的两条路径的权值最大值。
拆点,流量设为1。
特别的,起点终点流量设为2。

dfs找路径,注意特判起点直达终点的路径。

//֪知识点:最小费用最大流
/*
By:Luckyblock
*/
#include <map>
#include <queue>
#include <string> 
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
const int MARX = 1e5 + 10;
const int INF = 2e9 + 10;
//=============================================================
struct Edge
{
    int v, w, cost, ne;
} e[MARX << 1];
int N, M, S, T, edgenum = 1, head[MARX];
int dis[MARX], flow[MARX];
int PreEdge[MARX], PreNode[MARX];
int maxflow, mincost;
bool flag, vis[MARX];
std :: string m2[MARX];
std :: map <std :: string, int> m1;
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void AddEdge(int u, int v, int w, int cost)
{
	e[++ edgenum].v = v, e[edgenum].w = w, e[edgenum].cost = cost;
	e[edgenum].ne = head[u], head[u] = edgenum; 
	e[++ edgenum].v = u, e[edgenum].w = 0, e[edgenum].cost = - cost;
	e[edgenum].ne = head[v], head[v] = edgenum; 
}
bool Spfa()
{
    std :: queue <int> q;
    memset(dis, 0x3f, sizeof(dis));
	memset(flow, 0x3f, sizeof(flow));
	memset(vis, 0, sizeof(vis));
    q.push(S); vis[S] = 1; dis[S] = 0, PreNode[T] = - 1;

    while(! q.empty())
    {
      int u = q.front(); q.pop(); vis[u] = false;
      for(int i = head[u]; i; i = e[i].ne)
        if(e[i].w > 0 && dis[e[i].v] > dis[u] + e[i].cost)
        {
          dis[e[i].v] = dis[u] + e[i].cost;
          PreNode[e[i].v] = u, PreEdge[e[i].v] = i;
          flow[e[i].v] = std :: min(flow[u], e[i].w);
          if(! vis[e[i].v]) vis[e[i].v] = true, q.push(e[i].v);
        }
    }
    return (PreNode[T] != - 1);
}
void EK()
{
    while(Spfa())
    {
      maxflow += flow[T], mincost += flow[T] * dis[T];
      for(int now = T; now != S; now = PreNode[now])
        e[PreEdge[now]].w -= flow[T],
        e[PreEdge[now] ^ 1].w += flow[T];
    }
}
void Dfs1(int u)
{
	vis[u] = true;
	std :: cout << m2[u - N] << '\n';
	for(int i = head[u]; i; i = e[i].ne)
	  if(e[i].v <= N && ! e[i].w)
	  {
		Dfs1(e[i].v + N);
		break;
	  }
}
void Dfs2(int u)
{
	for(int i = head[u]; i; i = e[i].ne)
	  if(e[i].v <= N && ! vis[e[i].v + N] && ! e[i].w)
	    Dfs2(e[i].v + N);
	std :: cout << m2[u - N] << '\n';
}
//=============================================================
int main()
{
    N = read(), M = read(), S = 1, T = N << 1;
	for(int i = 1; i <= N; i ++)
	{
	  std :: string name;  std :: cin >> name;
	  m1[name] = i, m2[i] = name;
	  int u = i, v = i + N, w = 1;
	  if(i == 1 || i == N) w ++;
	  AddEdge(u, v, w, 0);
	}
	for(int i = 1; i <= M; i ++)
	{
	  std :: string s, t; std :: cin >> s >> t;
	  int u = m1[s], v = m1[t];
	  if(u == 1 && v == N) flag = true;	 
	  AddEdge(u + N, v, 1, - 1);
	}
	EK();
	
	if(maxflow != 2 && ! flag) {printf("No Solution!\n"); return 0;}
	if(maxflow != 2 && flag)
	{
	  std :: cout <<"2\n" << m2[1] << '\n' << m2[N] << '\n' << m2[1] << '\n';
	  return 0;
	}
	printf("%d\n", - mincost);
	Dfs1(N + 1), Dfs2(N + 1);
    system("pause");
    return 0;
}

方格取数问题

黑白染色, 建二分图, 答案 = 权值和 - 最小割。

//知识点: 最大独立集, 二分图匹配 
/*
By:Luckyblock
*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <ctype.h>
#define min std::min
#define ll long long
int ex[4] = {1, - 1, 0, 0};//存坐标变化量
int ey[4] = {0, 0, 1, - 1};
const int MARX = 5e4 + 10;
const int INF = 2e9 + 2077; 
//=============================================================
struct Edge
{
	int u, v, w, ne;
} e[MARX << 1];
int N, M, S, T, edgenum = - 1, Sum, head[MARX], Val[110][110];
int Dep[MARX], cur[MARX];
bool color[110][110];
//=============================================================
inline int read()
{
    int s = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') s = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 1) + (w << 3) + (ch ^ '0');
    return s * w;
}
void AddEdge(int u, int v, int w)
{
	e[++ edgenum].u = u, e[edgenum].v = v, e[edgenum].w = w;
	e[edgenum].ne = head[u], head[u] = edgenum; 
	
	e[++ edgenum].u = v, e[edgenum].v = u, e[edgenum].w = 0;
	e[edgenum].ne = head[v], head[v] = edgenum; 
}
bool Bfs()
{
	std :: queue <int> Q;
	memset(Dep, 0 ,sizeof(Dep));
	Dep[S] = 1; Q.push(S);
	
	do 
	{
	  int u = Q.front(); Q.pop();
	  for(int i = head[u]; i != - 1; i = e[i].ne)
	    if(e[i].w > 0 && Dep[e[i].v] == 0)
	      Dep[e[i].v] = Dep[u] + 1,
	      Q.push(e[i].v);
	} 
	while(! Q.empty());
	return Dep[T];
}
int Dfs(int u, int dis)
{
	if(u == T) return dis;
	for(int& i = cur[u]; i != - 1; i = e[i].ne)
	  if(Dep[e[i].v] == Dep[e[i].u] + 1 && e[i].w) 
	  {
	  	int ret = Dfs(e[i].v, min(dis, e[i].w));
	  	if(ret > 0) 
		{
		  e[i].w -= ret, e[i ^ 1].w += ret;
		  return ret;
		}
	  }
	return 0;
}
int Dinic()
{
	int ans = 0;
	while(Bfs()) 
	{
	  for(int i = 0; i <= N * M + 1; i ++) cur[i] = head[i];
	  while(int ret = Dfs(S, INF)) ans += ret;
	}
	return ans;
}
//=============================================================
signed main()
{
	N = read(), M = read(), S = 0, T = N * M + 1;
	memset(head, - 1, sizeof(head));
	for(int i = 1; i <= N; i ++)
	  for(int j = 1; j <= M; j ++) //对棋盘按照奇偶性 黑白染色
	  {
	  	color[i][j] = ((i + j) % 2 == 0),
		Val[i][j] = read(), 
		Sum += Val[i][j];
	    if(color[i][j]) AddEdge(S, (i - 1) * M + j, Val[i][j]);
	    else AddEdge((i - 1) * M + j, T,  Val[i][j]);
	  }
	for(int i = 1; i <= N; i ++) //枚举坐标 
	  for(int j = 1; j <= M; j ++)
	    if(color[i][j]) //枚举 一个独立集中的点, 向另一个独立集连边 
	  	  for(int k = 0; k < 4; k ++)
	      {
	        if(i + ex[k] < 1 || i + ex[k] > N || j + ey[k] < 1 || j + ey[k] > M) continue;
	        if(color[i + ex[k]][j + ey[k]]) continue;
		    AddEdge((i - 1) * M + j, (i + ex[k] - 1) * M + j + ey[k], INF); //双向连边, 注意边权 
		  }
	printf("%d", Sum - Dinic());  //求得 最大独立集 
}


机器人路径规划问题

我是傻逼,不会做这道题。
请不吝赐教。


圆桌问题

单位和桌子是两个独立集。
每个单位向每个桌子连容量为1的边。
建立超级源汇,求得最大流。

若最大流等于代表数,说明存在方案,
遍历各单位,检查连边的残余容量以确定方案。

//֪知识点:二分图
/*
By:Luckyblock
*/
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define ll long long
const int INF = 2e9 + 10;
const int MARX = 1e6 + 10;
//=============================================================
struct Edge
{
    int v, w, ne;
} e[MARX << 1];
int N, M, S, T, edgenum = 1, sum, head[MARX];
int Dep[MARX], cur[MARX];
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void AddEdge(int u, int v, int w)
{
    e[++ edgenum].v = v, e[edgenum].w = w;
    e[edgenum].ne = head[u], head[u] = edgenum;
    e[++ edgenum].v = u, e[edgenum].w = 0;
    e[edgenum].ne = head[v], head[v] = edgenum;
}
bool Bfs()
{
    std :: queue <int> q;
    memset(Dep, 0, sizeof(Dep));
    Dep[S] = 1; q.push(S);

    do
    {
      int u = q.front(); q.pop();
      for(int i = head[u]; i; i = e[i].ne)
        if(e[i].w > 0 && Dep[e[i].v] == 0)
          Dep[e[i].v] = Dep[u] + 1,
          q.push(e[i].v);
    }
    while (! q.empty());
    return Dep[T];
}
int Dfs(int u, int dis)
{
    if(u == T) return dis;
    for(int i = cur[u]; i; i = e[i].ne)
      if(Dep[e[i].v] == Dep[u] + 1 && e[i].w)
      {
        int ret = Dfs(e[i].v, std :: min(dis, e[i].w));
        if(ret > 0)
        {
          e[i].w -= ret, e[i ^ 1].w += ret;
          return ret;
        }
      }
    return 0;
}
int Dinic()
{
    int ans = 0;
    while(Bfs())
    {
      for(int i = S; i <= T; i ++) cur[i] = head[i];
      while(int ret = Dfs(S, INF)) ans += ret;
    }
    return ans;
}
//=============================================================
int main()
{
    M = read(), N = read(), S = 0, T = N + M + 1;
    for(int i = 1, val; i <= M; i ++) val = read(), sum += val, AddEdge(S, i, val);
    for(int i = 1, val; i <= N; i ++) val = read(), AddEdge(i + M, T, val);
    for(int i = 1; i <= M; i ++)
      for(int j = 1; j <= N; j ++)
        AddEdge(i, j + M, 1);

    if(Dinic() != sum) {printf("0\n"); return 0;}
    printf("1\n");
    for(int i = 1; i <= M; putchar('\n'), i ++)
      for(int j = head[i]; j; j = e[j].ne)
        if(e[j].v > M && e[j].v <= M + N && e[j].w == 0)
          printf("%d ", e[j].v - M);
    system("pause");
    return 0;
}

骑士共存问题

知识点:二分图最大独立集

若将矩阵上每格看做一结点,向其可攻击位置连边。
建图后, 则题目转化为: 求给定图的 最大独立集。

由于题目给定了一张棋盘图,
可将棋盘黑白染色, 使相邻两格子不同色。
观察图形发现, 对于每一个格子, 其能够攻击到的位置 颜色一定与其不同。

将格点转化为结点后, 按照染色的不同, 可将各点分为两点集。
可以发现, 对于每一个点集之间没有连边, 即每一个点集都为一独立集。
则原棋盘图转化为 一二分图。

对于一二分图, 其最大独立集 = 节点数(n) — 最大匹配数(m)。
可使用 匈牙利/网络流 求得最大匹配数, 即得答案

//知识点:二分图最大独立集
/*
By:Luckyblock
*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <ctype.h>
#define min std::min
#define ll long long
int ex[10] = {2, -2, 2, -2, -1, 1, -1, 1};//存坐标变化量
int ey[10] = {1, 1, -1, -1, 2, 2, -2, -2};
const int MARX = 4e4 + 10;
const int INF = 2e9 + 2077; 
const int MARX1 = 3e7 + 10;
//=============================================================
struct Edge
{
	int u, v, w, ne;
} e[MARX1];
int N, M, S, T, edgenum = - 1, NodeNum, head[MARX], color[210][210];
int Dep[MARX], cur[MARX];
//=============================================================
inline int read()
{
    int s = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') s = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 1) + (w << 3) + (ch ^ '0');
    return s * w;
}
void AddEdge(int u, int v, int w)
{
    e[++ edgenum].u = u, e[edgenum].v = v, e[edgenum].w = w;
    e[edgenum].ne = head[u], head[u] = edgenum; 
}
bool Bfs()
{
    std :: queue <int> Q;
    memset(Dep, 0 ,sizeof(Dep));
    Dep[S] = 1; Q.push(S);

    do 
    {
      int u = Q.front(); Q.pop();
      for(int i = head[u]; i != - 1; i = e[i].ne)
        if(e[i].w > 0 && Dep[e[i].v] == 0)
          Dep[e[i].v] = Dep[u] + 1,
          Q.push(e[i].v);
    } 
    while(! Q.empty());
    return Dep[T];
}
int Dfs(int u, int dis)
{
    if(u == T) return dis;
    for(int& i = cur[u]; i != - 1; i = e[i].ne)
      if(Dep[e[i].v] == Dep[e[i].u] + 1 && e[i].w) 
      {
        int ret = Dfs(e[i].v, min(dis, e[i].w));
        if(ret > 0) 
        {
          e[i].w -= ret, e[i ^ 1].w += ret;
          return ret;
        }
      }
    return 0;
}
int Dinic()
{
    int ans = 0;
    while(Bfs()) 
    {
      for(int i = 0; i <= N * N + 1; i ++) cur[i] = head[i];
      while(int ret = Dfs(S, INF)) ans += ret;
    }
    return ans;
}
//=============================================================
signed main()
{
    N = read(), M = read(), S = 0, T = N * N + 1;
    memset(head, - 1, sizeof(head));
    for(int i = 1; i <= N; i ++)
      for(int j = 1; j <= N; j ++) //对棋盘按照奇偶性 黑白染色
        NodeNum ++, color[i][j] = (i + j) % 2 ? 1 : -1;

    for(int i = 1; i <= M; i ++)
    {
      int x = read(), y = read();
      color[x][y] = 0, NodeNum --;
    }

    for(int i = 1; i <= N; i ++) //枚举坐标 
      for(int j = 1; j <= N; j ++)
        if(color[i][j] == 1) //枚举 一个独立集中的点, 向另一个独立集连边 
          for(int k = 0; k < 8; k ++)
          {
            if(i + ex[k] < 1 || i + ex[k] > N || j + ey[k] < 1 || j + ey[k] > N) continue;
            if(color[i + ex[k]][j + ey[k]] != - 1) continue;
            AddEdge((i - 1) * N + j, (i + ex[k] - 1) * N + j + ey[k], INF); //双向连边, 注意边权 
            AddEdge((i + ex[k] - 1) * N + j + ey[k], (i - 1) * N + j, 0);
          }

    for(int i = 1; i <= N; i ++) //将染为 1的点加入点集 
      for(int j = 1; j <= N; j ++)
        if(color[i][j] == 1) AddEdge(S, (i - 1) * N + j, 1), AddEdge((i - 1) * N + j, S,  0);
        else if(color[i][j] == - 1) AddEdge((i - 1) * N + j, T,  1), AddEdge(T, (i - 1) * N + j, 0);
    printf("%d", NodeNum - Dinic());  //求得 最大独立集 
}

火星探险问题

//֪知识点:最小费用最大流
/*
By:Luckyblock
*/
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define ll long long
const int MARX = 1e5 + 10;
const int INF = 2e9 + 10;
//=============================================================
struct Edge
{
    int v, w, cost, ne;
} e[MARX << 1];
int CarNum, N, M, S, T, edgenum = 1, head[MARX];
int dis[MARX], flow[MARX], PreEdge[MARX], PreNode[MARX];
int maxflow, mincost;
int ID, Map[40][40], Id[40][40];
bool vis[MARX];
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void AddEdge(int u, int v, int w, int cost)
{
    e[++ edgenum].v = v, e[edgenum].w = w, e[edgenum].cost = cost;
    e[edgenum].ne = head[u], head[u] = edgenum; 

    e[++ edgenum].v = u, e[edgenum].w = 0, e[edgenum].cost = - cost;
    e[edgenum].ne = head[v], head[v] = edgenum; 
}
bool Spfa()
{
    std :: queue <int> q;
    memset(dis, 0x3f, sizeof(dis));
	memset(flow, 0x3f, sizeof(flow));
	memset(vis, 0, sizeof(vis));
    q.push(S); vis[S] = 1; dis[S] = 0, PreNode[T] = - 1;

    while(! q.empty())
    {
      int u = q.front(); q.pop(); vis[u] = false;
      for(int i = head[u]; i; i = e[i].ne)
        if(e[i].w > 0 && dis[e[i].v] > dis[u] + e[i].cost)
        {
          dis[e[i].v] = dis[u] + e[i].cost;
          PreNode[e[i].v] = u, PreEdge[e[i].v] = i;
          flow[e[i].v] = std :: min(flow[u], e[i].w);
          if(! vis[e[i].v]) vis[e[i].v] = true, q.push(e[i].v);
        }
    }
    return (PreNode[T] != - 1);
}
void EK()
{
    while(Spfa())
    {
      maxflow += flow[T], mincost += flow[T] * dis[T];
      for(int now = T; now != S; now = PreNode[now])
        e[PreEdge[now]].w -= flow[T],
        e[PreEdge[now] ^ 1].w += flow[T];
    }
}
void Dfs(int x, int y, int u, int now)
{
	for(int i = head[u]; i; i = e[i].ne)
	{
	  if(e[i].v == S || e[i].v == T || e[i].v == u - N * M || e[i ^ 1].w == 0) continue;
	  e[i ^ 1].w --;
	  if(e[i].v > N * M) {Dfs(x, y, e[i].v, now); return ;}

	  int NextX = x, NextY = y, Dir;
	  if(e[i].v == Id[x][y] + 1) NextY ++, Dir = 1;
	  else NextX ++, Dir = 0;
	  printf("%d %d\n", now, Dir);
	  Dfs(NextX, NextY, e[i].v + N * M, now);
	  return ;
	}
}
//=============================================================
int main()
{
    CarNum = read(), M = read(), N = read(), S = 0, T = 2 * N * M + 1;
	for(int i = 1; i <= N; i ++)
	  for(int j = 1; j <= M; j ++)
	    Map[i][j] = read(), Id[i][j] = ++ ID;
	if(Map[1][1] != 1) AddEdge(S, 1, CarNum, 0);
	if(Map[N][M] != 1) AddEdge(Id[N][M] + M * N, T, CarNum, 0);
	for(int i = 1; i <= N; i ++)
	  for(int j = 1; j <= M; j ++)
	  {
		if(Map[i][j] == 1) continue;
		AddEdge(Id[i][j], Id[i][j] + N * M, INF, 0);
		if(Map[i][j] == 2) AddEdge(Id[i][j], Id[i][j] + N * M, 1, - 1);
		if(Map[i + 1][j] != 1 && Id[i + 1][j]) AddEdge(Id[i][j] + N * M, Id[i + 1][j], INF, 0);
		if(Map[i][j + 1] != 1 && Id[i][j + 1]) AddEdge(Id[i][j] + N * M, Id[i][j + 1], INF, 0);
	  }
	EK();
	for(int i = 1; i <= maxflow; i ++) Dfs(1, 1, 1, i);
    system("pause");
    return 0;
}

最长k可重线段集问题

将线段按照左右端点进行转化,
即为P3358 最长k可重区间问题

\(i \rightarrow i + 1\), 容量为inf, 费用为0。
每个区间, \(left \rightarrow right\), 容量为1, 费用为 \(-1 \times\) 区间长度
限定最大流最大为k,输出最小费的相反数即可,

可发现 当两区间无交集时,只需要1流量就可全部经过。
若有交集,需要2流量才可全部经过。
最大流 = k,说明有一个数 被不同的区间相交了k次。
限定最大流最大为k 即限定了数最多只能选k次
注意开区间 的 区间长度



注意与x轴垂直的线段.

//知识点:最小费用最大流
/*
By:Luckyblock
*/
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define int long long
const int MARX = 5e4 + 10;
const int INF = 2e9 + 10;
//===========================================================
struct Segment
{
	int L, R, Lth;
} I[MARX];
struct Edge
{
	int u, v, w, cost, ne;
} e[MARX << 1];
int N, K, s, S, T, mincost, edgenum = 1, head[MARX];
int L[MARX], R[MARX], Length[MARX], Data[MARX << 1];
int dis[MARX], flow[MARX];
int pre[MARX], pren[MARX];
bool vis[MARX];;
//===========================================================
inline int read()
{
	int f = 1, w = 0; char ch = getchar();
	for(; ! isdigit(ch); ch = getchar()) if(ch == '-') f = - 1;
	for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
	return f * w;
}
void AddEdge(int u, int v, int w, int cost)
{
	e[++ edgenum].u = u, e[edgenum].v = v, e[edgenum].w = w, e[edgenum].cost = cost;
	e[edgenum].ne = head[u], head[u] = edgenum; 
	
	e[++ edgenum].u = v, e[edgenum].v = u, e[edgenum].w = 0, e[edgenum].cost = - cost;
	e[edgenum].ne = head[v], head[v] = edgenum; 
}
bool CMP(Segment fir, Segment sec) {return fir.L == sec.L ? fir.R < sec.R : fir.L < sec.L;}
bool Spfa(int S, int T)
{
	std :: queue <int> q;
	memset(dis, 0x7f, sizeof(dis));
	memset(flow, 0x7f, sizeof(flow));
	memset(vis, 0, sizeof(vis));
	q.push(S); vis[S] = 1; dis[S] = 0, pren[T] = - 1;
	
	while(! q.empty())
	{
	  int now = q.front(); q.pop(); vis[now] = false;
	  for(int i = head[now]; i; i = e[i].ne)
	    if(e[i].w > 0 && dis[e[i].v] > dis[now] + e[i].cost)
	    {
	      dis[e[i].v] = dis[now] + e[i].cost;
	      pren[e[i].v] = now, pre[e[i].v] = i;
	      flow[e[i].v] = std :: min(flow[now], e[i].w);
	      if(! vis[e[i].v]) vis[e[i].v] = true, q.push(e[i].v);
		}
	}
	return (pren[T] != - 1);
}
void EK(int S, int T)
{
	while(Spfa(S, T))
	{
	  mincost += flow[T] * dis[T];
	  for(int now = T; now != S; now = pren[now])
	  	e[pre[now]].w -= flow[T],
	  	e[pre[now] ^ 1].w += flow[T];
	}
}
//===========================================================
signed main()
{
	N = read(), K = read(), s = 2 * N + 1, S = s + 1, T = S + 1;
	for(int i = 1; i <= N; i ++)
	{
	  int x0 = read(), y0 = read(), x1 = read(), y1 = read();
	  I[i].L = std :: min(x0, x1), I[i].R = std :: max(x0, x1);
	  I[i].Lth = floor(sqrt((x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1)));
	}
	std :: sort(I + 1, I + N + 1, CMP);

	AddEdge(S, s, K, 0);
	for(int i = 1; i <= N; i ++)
	{
	  AddEdge(i, i + N, 1, - I[i].Lth);
	  AddEdge(s, i, 1, 0); 
	  AddEdge(i + N, T, 1, 0);
	  for(int j = i + 1; j <= N; j ++)
	    if(I[i].L == I[i].R && I[j].L == I[j].R && I[i].L == I[j].L) continue;
		else if(I[i].R <= I[j].L || I[i].L > I[j].R) AddEdge(i + N, j, 1, 0);
	}
	EK(S, T);
	printf("%lld", - mincost);
	system("pause");
	return 0;
}

最长k可重区间集问题

求最大费用最大流.
\(i \rightarrow i + 1\), 容量为inf, 费用为0.
每个区间, \(left \rightarrow right\), 容量为1, 费用为 \(-1 \times\) 区间长度
限定最大流最大为k,输出最小费的相反数即可,


可发现 当两区间无交集时,只需要 1 流量就可全部经过
若有交集,需要 2 流量才可全部经过。
最大流 = k,说明有一个数 被不同的区间相交了 k 次。
限定最大流最大为k 即限定了数最多只能选 k 次
注意开区间 的 区间长度



//知识点:网络流
/*
By:Luckyblock
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <queue>
#define min std::min
#define max std::max
#define ll long long
const int MARX = 5e4 + 10;
const int INF = 2e9 + 10;
//===========================================================
struct Edge
{
	int u, v, w, cost, ne;
} e[MARX << 1];
int N, M, K, S, T, mincost, edgenum = - 1, head[MARX];
int L[MARX], R[MARX], Length[MARX], Data[MARX << 1];
int dis[MARX], flow[MARX];
int pre[MARX], pren[MARX];
bool vis[MARX];;
//===========================================================
inline int read()
{
	int f = 1, w = 0; char ch = getchar();
	for(; ! isdigit(ch); ch = getchar()) if(ch == '-') f = - 1;
	for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
	return f * w;
}
void AddEdge(int u, int v, int w, int cost)
{
	e[++ edgenum].u = u, e[edgenum].v = v, e[edgenum].w = w, e[edgenum].cost = cost;
	e[edgenum].ne = head[u], head[u] = edgenum; 
	
	e[++ edgenum].u = v, e[edgenum].v = u, e[edgenum].w = 0, e[edgenum].cost = - cost;
	e[edgenum].ne = head[v], head[v] = edgenum; 
}
bool Spfa(int S, int T)
{
	std :: queue <int> q;
	memset(dis, 0x7f, sizeof(dis));
	memset(flow, 0x7f, sizeof(flow));
	memset(vis, 0, sizeof(vis));
	q.push(S); vis[S] = 1; dis[S] = 0, pren[T] = - 1;
	
	while(! q.empty())
	{
	  int now = q.front(); q.pop(); vis[now] = false;
	  for(int i = head[now]; i != - 1; i = e[i].ne)
	    if(e[i].w > 0 && dis[e[i].v] > dis[now] + e[i].cost)
	    {
	      dis[e[i].v] = dis[now] + e[i].cost;
	      pren[e[i].v] = now, pre[e[i].v] = i;
	      flow[e[i].v] = min(flow[now], e[i].w);
	      if(! vis[e[i].v]) vis[e[i].v] = true, q.push(e[i].v);
		}
	}
	return (pren[T] != - 1);
}
void EK(int S, int T)
{
	while(Spfa(S, T))
	{
	  mincost += flow[T] * dis[T];
	  for(int now = T; now != S; now = pren[now])
	  	e[pre[now]].w -= flow[T],
	  	e[pre[now] ^ 1].w += flow[T];
	}
}
//===========================================================
int main()
{
	N = read(), K = read(), S = 0, T = 0;
	memset(head, - 1, sizeof(head)); 
	
	for(int i = 1, now = 0; i <= N; i ++) 
	  Data[++ now] = L[i] = read(), 
	  Data[++ now] = R[i] = read(),
	  Length[i] = R[i] - L[i];
	std :: sort(Data + 1, Data + 2 * N + 1);
	for(int i = 1; i <= N; i ++) 
	  L[i] = std :: lower_bound(Data + 1, Data + 2 * N + 1, L[i]) - Data, 
	  R[i] = std :: lower_bound(Data + 1, Data + 2 * N + 1, R[i]) - Data;
	
	for(int i = 1; i <= N; i ++) T = max(T, R[i]), AddEdge(L[i], R[i], 1, - Length[i]);
	for(int i = 1; i < T; i ++) AddEdge(i, i + 1, INF, 0);
	AddEdge(S, 1, K, 0), AddEdge(T, T + 1, K, 0);
	T ++;
	
	EK(S, T);
	printf("%d", - mincost);
	system("pause");
	return 0;
}

汽车加油行驶问题

按照当前油量进行分层。
使用 spfa 进行更新。
根据当前位置有无加油站,当前油量是否为0进行讨论转移。
最后找到终点每层的答案,取最小值。


//知识点:分层图,spfa
/*
By:Luckyblock
*/
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define ll long long
const int MARX = 110;
int ex[4] = {1, - 1, 0, 0};
int ey[4] = {0, 0, 1, - 1};
//=============================================================
int N, K, A, B, C, dis[MARX][MARX][15];
bool Map[MARX][MARX], vis[MARX][MARX][15];
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void Spfa()
{
    std :: queue <int> qx, qy, qk;
    memset(dis, 0x3f, sizeof(dis));
    dis[1][1][K] = 0, vis[1][1][K] = true;
    qx.push(1), qy.push(1), qk.push(K);

    while(! qx.empty())
    {
      int x = qx.front(); qx.pop();
      int y = qy.front(); qy.pop();
      int k = qk.front(); qk.pop();
      vis[x][y][k] = false;

      if(Map[x][y] && k != K)
      {
        if(dis[x][y][K] > dis[x][y][k] + A)
        {
          dis[x][y][K] = dis[x][y][k] + A;
          if(! vis[x][y][K]) 
            vis[x][y][K] = true, 
            qx.push(x), qy.push(y), qk.push(K);
        }
        continue;
      }
      if(dis[x][y][K] > dis[x][y][k] + A + C)
      {
        dis[x][y][K] = dis[x][y][k] + A + C;
        if(! vis[x][y][K]) 
          vis[x][y][K] = true, 
          qx.push(x), qy.push(y), qk.push(K);
      }
      if(k <= 0) continue; //大小写区分
      for(int i = 0; i < 4; i ++)
      {
        int nx = x + ex[i], ny = y + ey[i];
        if(nx < 1 || nx > N || ny < 1 || ny > N) continue;
        int cost = (nx < x || ny < y) ? B : 0;

        if(dis[nx][ny][k - 1] > dis[x][y][k] + cost)
        {
          dis[nx][ny][k - 1] = dis[x][y][k] + cost;
          if(! vis[nx][ny][k - 1]) //锅
            vis[nx][ny][k - 1] = true,
            qx.push(nx), qy.push(ny), qk.push(k - 1);
        }
      }
    }
}
//=============================================================
int main()
{
    N = read(), K = read(), A = read(), B = read(), C = read();
    for(int i = 1; i <= N; i ++)
      for(int j = 1; j <= N; j ++)
        Map[i][j] = read();

    Spfa();

    int ans = 2e9 + 10;
    for(int i = 0; i <= K; i ++) ans = std :: min(ans, dis[N][N][i]);
    printf("%d", ans);

    system("pause");
    return 0;
}

孤岛营救问题

使用二进制状压,
维护到达某个节点时, 身上钥匙的携带情况。
则可极其简单的求得 一扇门是否可以打开.

由于各点之间距离均为1, 矩阵大小较小,
可考虑使用01最短路解决本题.
维护到达某点时, 携带钥匙为某状态的最短时间,
由于是01 bfs, 第一次搜到终点时 一定为最短路


//知识点:状压 + 01bfs
/*
By:Luckyblock
*/
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <algorithm>
#define ll long long
const int MARX = (1 << 11);
const int ex[4] = {0, 0, 1, - 1};
const int ey[4] = {1, - 1, 0, 0};
//=============================================================
int N, M, P, K, S;
bool vis[11][11][MARX];
int Map[11][11][11][11];
int Key[11][11][11], Num[11][11];
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
int Bfs()
{
	std :: queue <int> q; int now = 0;
	for(int i = 1; i <= Num[1][1]; i ++) now |= (1 << (Key[1][1][i] - 1));
	vis[1][1][now] = true;
	q.push(1), q.push(1), q.push(0), q.push(now);
	
	while(! q.empty())
	{
	  int x = q.front(); q.pop();
	  int y = q.front(); q.pop();
	  int step = q.front(); q.pop();
	  int key = q.front(); q.pop();
	  if(x == N && y == M) return step;
	  for(int i = 0; i < 4; i ++)
	  {
		int xx = x + ex[i], yy = y + ey[i], type = Map[x][y][xx][yy];
		if(xx < 1 || yy < 1 || xx > N || yy > M) continue;
		if(type != 0 && (key & (1 << type - 1)) == 0) continue;
		if(type == - 1) continue;
		
		now = key;
		for(int j = 1; j <= Num[xx][yy]; j ++) now |= (1 << Key[xx][yy][j] - 1);
		if(vis[xx][yy][now]) continue;
		vis[xx][yy][now] = 1;
		q.push(xx), q.push(yy), q.push(step + 1), q.push(now);
	  }
	}
	return - 1;
}
//=============================================================
int main()
{
    N = read(), M = read(), P = read(), K = read();
    for(int i = 1; i <= K; i ++)
    {
      int x1 = read(), y1 = read(), x2 = read(), y2 = read(), g = read();
      if(! g) Map[x1][y1][x2][y2] = Map[x2][y2][x1][y1] = - 1;
      else Map[x1][y1][x2][y2] = Map[x2][y2][x1][y1] = g;
    }
    S = read();
	for(int i = 1; i <= S; i ++)
	{
	  int x = read(), y = read(), q = read();
	  Key[x][y][++ Num[x][y]] = q;
	}
	printf("%d\n", Bfs());
    system("pause");
    return 0;
}

深海机器人问题

知识点:最小费用最大流

将每个机器人看做1流量。
一个机器人可采集路上所有标本,
则一条边上生物标本的价值 即为1流量的费用。
显然可用最大费用最大流求解。


按照下列策略建图:

  1. 超级源各机器人起点 连边,容量为 该点机器数,费用为0。
  2. 各机器终点超级汇 连边,容量为 允许将其作为终点机器数,费用为0。
  3. 网格中各边进行复制:一边容量为1,费用为标本价值;另一边容量无限,费用为0。

求得最大费用即为答案。

//知识点:最小费用最大流
/*
By:Luckyblock
*/
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define ll long long
const int MARX = 1e6 + 10;
const int INF = 2e9 + 10;
//=============================================================
struct Edge
{
    int v, w, cost, ne;
} e[MARX << 1];
int A, B, P, Q, S, T, mincost, edgenum = 1, head[MARX];
int dis[MARX], flow[MARX], PreEdge[MARX], PreNode[MARX];
bool vis[MARX];
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
int Pos(int x, int y) {return (x - 1) * Q + y;}
void AddEdge(int u, int v, int w, int cost)
{
	e[++ edgenum].v = v, e[edgenum].w = w, e[edgenum].cost = cost;
	e[edgenum].ne = head[u], head[u] = edgenum; 

	e[++ edgenum].v = u, e[edgenum].w = 0, e[edgenum].cost = - cost;
	e[edgenum].ne = head[v], head[v] = edgenum; 
}
bool Spfa()
{
    std :: queue <int> q;
    memset(dis, 0x3f, sizeof(dis));
	memset(flow, 0x3f, sizeof(flow));
	memset(vis, 0, sizeof(vis));
    q.push(S); vis[S] = 1; dis[S] = 0, PreNode[T] = - 1;

    while(! q.empty())
    {
      int u = q.front(); q.pop(); vis[u] = false;
      for(int i = head[u]; i; i = e[i].ne)
        if(e[i].w > 0 && dis[e[i].v] > dis[u] + e[i].cost)
        {
          dis[e[i].v] = dis[u] + e[i].cost;
          PreNode[e[i].v] = u, PreEdge[e[i].v] = i;
          flow[e[i].v] = std :: min(flow[u], e[i].w);
          if(! vis[e[i].v]) vis[e[i].v] = true, q.push(e[i].v);
        }
    }
    return (PreNode[T] != - 1);
}
void EK()
{
    while(Spfa())
    {
      mincost += flow[T] * dis[T];
      for(int now = T; now != S; now = PreNode[now])
        e[PreEdge[now]].w -= flow[T],
        e[PreEdge[now] ^ 1].w += flow[T];
    }
}
//=============================================================
int main()
{
    A = read(), B = read(), P = read() + 1, Q = read() + 1, S = 0, T = 1010;
	for(int i = 1; i <= P; i ++)
	  for(int j = 1; j < Q; j ++)
	  {
		int val = read(), u = Pos(i, j), v = u + 1;
		AddEdge(u, v, 1, - val); //只做一次贡献
		AddEdge(u, v, INF, 0); //可多次经过
	  }
	for(int j = 1; j <= Q; j ++)
	  for(int i = 1; i < P; i ++)
	  {
		int val = read(), u = Pos(i, j), v = u + Q;
		AddEdge(u, v, 1, - val);
		AddEdge(u, v, INF, 0);
	  }
	for(int i = 1; i <= A; i ++)
	{
	  int k = read(), x = read() + 1, y = read() + 1;
	  AddEdge(S, Pos(x, y), k, 0);
	}
	for(int i = 1; i <= B; i ++)
	{
	  int k = read(), x = read() + 1, y = read() + 1;
	  AddEdge(Pos(x, y), T, k, 0);
	}
	EK();
	printf("%d\n", - mincost);
    system("pause");
    return 0;
}

数字梯形问题

路径相交 = 路径中出现重复的点 + 路径中出现重复的边。
路径不相交 = 每个点只能使用一次

//֪知识点:网络流
/*
By:Luckyblock
*/
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define ll long long
const int MARX = 1e5 + 10;
const int INF = 0x3f3f3f3f;
//=============================================================
struct Edge
{
    int v, w, cost, ne;
} e[MARX << 1];
int N, M, S, T, IdCnt, mincost, edgenum = 1, head[MARX];
int Trapezoid[21][41], Id[21][41];
int dis[MARX], flow[MARX];
int PreEdge[MARX], PreNode[MARX];
bool vis[MARX];
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void AddEdge(int u, int v, int w, int cost)
{
	e[++ edgenum].v = v, e[edgenum].w = w, e[edgenum].cost = cost;
	e[edgenum].ne = head[u], head[u] = edgenum; 

    e[++ edgenum].v = u, e[edgenum].w = 0, e[edgenum].cost = -cost;
	e[edgenum].ne = head[v], head[v] = edgenum; 
}
bool Spfa()
{
    std :: queue <int> q;
    memset(dis, 0x3f, sizeof(dis));
	memset(flow, 0x3f, sizeof(flow));
	memset(vis, 0, sizeof(vis));
    q.push(S); vis[S] = 1; dis[S] = 0, PreNode[T] = - 1;

    while(! q.empty())
    {
      int u = q.front(); q.pop(); vis[u] = false;
      for(int i = head[u]; i; i = e[i].ne)
        if(e[i].w > 0 && dis[e[i].v] > dis[u] + e[i].cost)
        {
          dis[e[i].v] = dis[u] + e[i].cost;
          PreNode[e[i].v] = u, PreEdge[e[i].v] = i;
          flow[e[i].v] = std :: min(flow[u], e[i].w);
          if(! vis[e[i].v]) vis[e[i].v] = true, q.push(e[i].v);
        }
    }
    return (PreNode[T] != - 1);
}
void EK()
{
    while(Spfa())
    {
      mincost += flow[T] * dis[T];
      for(int now = T; now != S; now = PreNode[now])
        e[PreEdge[now]].w -= flow[T],
        e[PreEdge[now] ^ 1].w += flow[T];
    }
}
void Clear()
{
    edgenum = 1, mincost = 0;
    memset(head, 0, sizeof(head));
}
void Solve1()
{
    for(int i = 1; i <= M; i ++) AddEdge(S, Id[1][i], 1, 0);
    for(int i = 1; i < N; i ++)
      for(int j = 1; j <= M + i - 1; j ++)
        AddEdge(Id[i][j], Id[i][j] + IdCnt, 1, - Trapezoid[i][j]),
        AddEdge(Id[i][j] + IdCnt, Id[i + 1][j], 1, 0),
        AddEdge(Id[i][j] + IdCnt, Id[i + 1][j + 1], 1, 0);
    for(int i = 1; i <= M + N - 1; i ++)
      AddEdge(Id[N][i], Id[N][i] + IdCnt, 1, - Trapezoid[N][i]),
      AddEdge(Id[N][i] + IdCnt, T, 1, 0);
    EK(); printf("%d\n", - 1 * mincost);
}
void Solve2()
{
    for(int i = 1; i <= M; i ++) AddEdge(S, Id[1][i], 1, 0);
    for(int i = 1; i < N; i ++)
      for(int j = 1; j <= M + i - 1; j ++)
        AddEdge(Id[i][j], Id[i + 1][j], 1, - Trapezoid[i][j]),
        AddEdge(Id[i][j], Id[i + 1][j + 1], 1, - Trapezoid[i][j]);
    for(int i = 1; i <= M + N - 1; i ++)
      AddEdge(Id[N][i], T, INF, - Trapezoid[N][i]);
    EK(); printf("%d\n", - 1 * mincost);
}
void Solve3()
{
    for(int i = 1; i <= M; i ++) AddEdge(S, Id[1][i], 1, 0);
    for(int i = 1; i < N; i ++)
      for(int j = 1; j <= M + i - 1; j ++)
        AddEdge(Id[i][j], Id[i + 1][j], INF, - Trapezoid[i][j]),
        AddEdge(Id[i][j], Id[i + 1][j + 1], INF, - Trapezoid[i][j]);
    for(int i = 1; i <= M + N - 1; i ++) 
      AddEdge(Id[N][i], T, INF, - Trapezoid[N][i]);
    EK(); printf("%d\n", - 1 * mincost);
}
//=============================================================
int main()
{
    M = read(), N = read(), S = 0;
    for(int i = 1; i <= N; i ++)
      for(int j = 1; j <= M + i - 1; j ++)
        Trapezoid[i][j] = read(), Id[i][j] = ++ IdCnt;
    T = IdCnt * 2 + 10;
    Solve1(); Clear(); Solve2(); Clear(); Solve3();
    system("pause");
    return 0;
}

分配问题

知识点:二分图完备匹配,最小费用最大流。

将人与任务 分别看作两个独立集。
以做工效益为边权连边,可建立一张二分图。
由于一人只可做一项工作,显然答案即为 该二分图的最小、最大完备匹配。

按照下列策略建图:

  1. 超级源 向各 人员 连边,容量为 1,费用为 0。
  2. 人员超级汇 连边,容量为 1,费用为 0。
  3. 人员\(i\)工作\(j\) 连边,容量为 1,费用为 \(\large c_{ij}\)

根据图形性质,显然必可满流。
使用最小费用最大流算法,即可求得最小费用。
各边费用取反,即可求得最大费用。

代码中建了两遍图,分别求最小、最大完备匹配。

//֪知识点:最小费用最大流,二分图完备匹配
/*
By:Luckyblock
*/
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define ll long long
const int MARX = 1e5 + 10;
const int INF = 2e9 + 10;
//=============================================================
struct Edge
{
    int v, w, cost, ne;
} e[MARX << 1];
int N, M, S, T, edgenum = 1, mincost, head[MARX], cost[110][110];
int PreEdge[MARX], PreNode[MARX];
int dis[MARX], flow[MARX];
bool vis[MARX];
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void AddEdge(int u, int v, int w, int cost)
{
	e[++ edgenum].v = v, e[edgenum].w = w, e[edgenum].cost = cost;
	e[edgenum].ne = head[u], head[u] = edgenum; 
}
bool Spfa()
{
    std :: queue <int> q;
    memset(dis, 0x3f, sizeof(dis));
	memset(flow, 0x3f, sizeof(flow));
	memset(vis, 0, sizeof(vis));
    q.push(S); vis[S] = 1; dis[S] = 0, PreNode[T] = - 1;

    while(! q.empty())
    {
      int u = q.front(); q.pop(); vis[u] = false;
      for(int i = head[u]; i; i = e[i].ne)
        if(e[i].w > 0 && dis[e[i].v] > dis[u] + e[i].cost)
        {
          dis[e[i].v] = dis[u] + e[i].cost;
          PreNode[e[i].v] = u, PreEdge[e[i].v] = i;
          flow[e[i].v] = std :: min(flow[u], e[i].w);
          if(! vis[e[i].v]) vis[e[i].v] = true, q.push(e[i].v);
        }
    }
    return (PreNode[T] != - 1);
}
void EK()
{
    while(Spfa())
    {
      mincost += flow[T] * dis[T];
      for(int now = T; now != S; now = PreNode[now])
        e[PreEdge[now]].w -= flow[T],
        e[PreEdge[now] ^ 1].w += flow[T];
    }
}
//=============================================================
int main()
{
    N = read(), S = 0, T = 2 * N + 1;
	for(int i = 1; i <= N; i ++) AddEdge(S, i, 1, 0), AddEdge(i, S, 0, 0);
	for(int i = N + 1; i <= 2 * N; i ++) AddEdge(i, T, 1, 0), AddEdge(T, i, 0, 0);
	for(int i = 1; i <= N; i ++)
	  for(int j = 1; j <= N; j ++)
	    cost[i][j] = read(),
		AddEdge(i, j + N, 1, cost[i][j]),
		AddEdge(j + N, i, 0, - cost[i][j]);
	EK();
	printf("%d\n", mincost);

	edgenum = 1, mincost = 0;
	memset(head, 0, sizeof(head));
	for(int i = 1; i <= N; i ++) AddEdge(S, i, 1, 0), AddEdge(i, S, 0, 0);
	for(int i = N + 1; i <= 2 * N; i ++) AddEdge(i, T, 1, 0), AddEdge(T, i, 0, 0);
	for(int i = 1; i <= N; i ++)
	  for(int j = 1; j <= N; j ++)
		AddEdge(i, j + N, 1, - cost[i][j]),
		AddEdge(j + N, i, 0, cost[i][j]);
	EK();
	printf("%d\n", - 1 * mincost);

    system("pause");
    return 0;
}

运输问题

知识点:二分图完备匹配,最小费用最大流。

各仓库之间相互独立,各商店之间相互独立,构成了两个独立集。
仓库与商店之间 按照费用连边,可得一二分图。
题目要求 即为该二分图的带权完备匹配的 最小/最大值。

建立超级源汇,按照下列策略连边:

  1. 超级源各仓库 连边,容量为库存,费用为0。
  2. 各商店超级汇 连边,容量为需求,费用为0.
  3. 仓库\(i\)商店\(j\) 连边,容量为商店需求,费用为\(c_{ij}\)

观察可得,该图必然可以满流。
求得最小费用/最大费用 最大流即为答案。

//֪知识点:最小费用最大流,二分图完备匹配
/*
By:Luckyblock
*/
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define ll long long
const int MARX = 1e5 + 10;
const int INF = 2e9 + 10;
//=============================================================
struct Edge
{
    int v, w, cost, ne;
} e[MARX << 1];
int N, M, S, T, edgenum = 1, mincost, head[MARX], have[210], need[210], cost[110][110];
int PreEdge[MARX], PreNode[MARX];
int dis[MARX], flow[MARX];
bool vis[MARX];
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void AddEdge(int u, int v, int w, int cost)
{
	e[++ edgenum].v = v, e[edgenum].w = w, e[edgenum].cost = cost;
	e[edgenum].ne = head[u], head[u] = edgenum; 
}
bool Spfa()
{
    std :: queue <int> q;
    memset(dis, 0x3f, sizeof(dis));
	memset(flow, 0x3f, sizeof(flow));
	memset(vis, 0, sizeof(vis));
    q.push(S); vis[S] = 1; dis[S] = 0, PreNode[T] = - 1;

    while(! q.empty())
    {
      int u = q.front(); q.pop(); vis[u] = false;
      for(int i = head[u]; i; i = e[i].ne)
        if(e[i].w > 0 && dis[e[i].v] > dis[u] + e[i].cost)
        {
          dis[e[i].v] = dis[u] + e[i].cost;
          PreNode[e[i].v] = u, PreEdge[e[i].v] = i;
          flow[e[i].v] = std :: min(flow[u], e[i].w);
          if(! vis[e[i].v]) vis[e[i].v] = true, q.push(e[i].v);
        }
    }
    return (PreNode[T] != - 1);
}
void EK()
{
    while(Spfa())
    {
      mincost += flow[T] * dis[T];
      for(int now = T; now != S; now = PreNode[now])
        e[PreEdge[now]].w -= flow[T],
        e[PreEdge[now] ^ 1].w += flow[T];
    }
}
//=============================================================
int main()
{
    M = read(), N = read(), S = 0, T = M + N + 1;
	for(int i = 1; i <= M; i ++) have[i] = read(), AddEdge(S, i, have[i], 0), AddEdge(i, S, 0, 0);
	for(int i = 1; i <= N; i ++) need[i] = read(), AddEdge(i + M, T, need[i], 0), AddEdge(T, i + M, 0, 0);
    for(int i = 1; i <= M; i ++)
	  for(int j = 1; j <= N; j ++)
	    cost[i][j] = read(),
		AddEdge(i, j + M, need[j], cost[i][j]),
		AddEdge(j + M, i, 0, - cost[i][j]);
	EK();
	printf("%d\n", mincost);

	edgenum = 1, mincost = 0;
	memset(head, 0, sizeof(head));
	for(int i = 1; i <= M; i ++) AddEdge(S, i, have[i], 0), AddEdge(i, S, 0, 0);
	for(int i = 1; i <= N; i ++) AddEdge(i + M, T, need[i], 0), AddEdge(T, i + M, 0, 0);
	for(int i = 1; i <= M; i ++)
	  for(int j = 1; j <= N; j ++)
		AddEdge(i, j + M, need[j], - cost[i][j]),
		AddEdge(j + M, i, 0, cost[i][j]);
	EK();
	printf("%d\n", - 1 * mincost);

    system("pause");
    return 0;
}

负载平衡问题

按照代码所述建图,
求当每个点向汇点流量均为平均数时,
总共的花费.

//知识点:网络流 
/*
By:Luckyblock
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <queue>
#define min std::min
#define ll long long
const int MARX = 1e5 + 10;
const int INF = 2e9 + 10;
//===========================================================
struct Edge
{
	int u, v, w, cost, ne;
} e[MARX << 1];
int N, S, T, Sum, mincost, edgenum = - 1, head[MARX];
int dis[MARX], flow[MARX];
int pre[MARX], pren[MARX];
bool vis[MARX];
//===========================================================
inline int read()
{
	int f = 1, w = 0; char ch = getchar();
	for(; ! isdigit(ch); ch = getchar()) if(ch == '-') f = - 1;
	for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
	return f * w;
}
void AddEdge(int u, int v, int w, int cost)
{
	e[++ edgenum].u = u, e[edgenum].v = v, e[edgenum].w = w, e[edgenum].cost = cost;
	e[edgenum].ne = head[u], head[u] = edgenum; 
	
	e[++ edgenum].u = v, e[edgenum].v = u, e[edgenum].w = 0, e[edgenum].cost = - cost;
	e[edgenum].ne = head[v], head[v] = edgenum; 
}
bool Spfa(int S, int T)
{
	std :: queue <int> q;
	memset(dis, 0x7f, sizeof(dis));
	memset(flow, 0x7f, sizeof(flow));
	memset(vis, 0, sizeof(vis));
	q.push(S); vis[S] = 1; dis[S] = 0, pren[T] = - 1;

	while(! q.empty())
	{
	  int now = q.front(); q.pop(); vis[now] = false;
	  for(int i = head[now]; i != - 1; i = e[i].ne)
	    if(e[i].w > 0 && dis[e[i].v] > dis[now] + e[i].cost)
	    {
	      dis[e[i].v] = dis[now] + e[i].cost;
	      pren[e[i].v] = now, pre[e[i].v] = i;
	      flow[e[i].v] = min(flow[now], e[i].w);
	      if(! vis[e[i].v]) vis[e[i].v] = true, q.push(e[i].v);
		}
	}
	return (pren[T] != - 1);
}
void EK(int S, int T)
{
	while(Spfa(S, T))
	{
	  mincost += flow[T] * dis[T];
	  for(int now = T; now != S; now = pren[now])
	  	e[pre[now]].w -= flow[T],
	  	e[pre[now] ^ 1].w += flow[T];
	}
}
//===========================================================
int main()
{
	N = read(), S = 0, T = N + 1;
	memset(head, - 1, sizeof(head)); 
	for(int i = 1; i <= N; i ++) 
	{
	  int Val = read(); Sum += Val;
	  int L = i - 1, R = i + 1;
	  if(L == 0) L = N; if(R == N + 1) R = 1;
	  AddEdge(i, L, INF, 1), AddEdge(i, R, INF, 1), AddEdge(S, i, Val, 0);
	}
	
	Sum /= N;
	for(int i = 1; i <= N; i ++) AddEdge(i, T, Sum, 0);
	EK(S, T);
	printf("%d", mincost);
	return 0;
}


写在最后

先贴了代码,解析就。。。
咕咕咕咕咕

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部