最大流

\(Dinic\)

直接上代码CwQwC。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int INF = 999999999;
const int N = 10050;
const int M = 200050;

int n, m, s, t, head[N], num = 1, dis[N];

struct Node
{
    int next, to, dis;
} edge[M * 2];

void Addedge(int u, int v, int w)
{
    edge[++num]= (Node){head[u], v, w};
    head[u] = num;
}

template <class T>
void Read(T &x)
{
    x = 0; int p = 0; char st = getchar();
    while (st < '0' || st > '9') p = (st == '-'), st = getchar();
    while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar();
    x = p ? -x : x;
    return;
}

template <class T>
void Put(T x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) Put(x / 10);
    putchar(x % 10 + '0');
    return;
}

bool Bfs()
{
    queue<int> q;
    for (int i = 1; i <= n; i++) dis[i] = 0;
    dis[s] = 1; q.push(s);
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = edge[i].next)
            if (!dis[edge[i].to] && edge[i].dis)
            {
                dis[edge[i].to] = dis[u] + 1;
                q.push(edge[i].to);
                if (edge[i].to == t) return 1;
            }
    }
    return 0;
}

int Dinic(int x, int flow)
{
    if (x == t || !flow) return flow;
    int rest = flow;
    for (int i = head[x]; i && rest; i = edge[i].next)
        if (edge[i].dis && dis[edge[i].to] == dis[x] + 1)
        {
            int v = edge[i].to;
            int tmp = Dinic(v, min(rest, edge[i].dis));
            rest -= tmp;
            edge[i].dis -= tmp;
            edge[i ^ 1].dis += tmp;
            if (!tmp) dis[v] = 0;
        }
    return flow - rest;
}

int main()
{
    Read(n); Read(m); Read(s); Read(t);
    int u, v, w;
    for (int i = 1; i <= m; i++)
    {
        Read(u); Read(v); Read(w);
        Addedge(u, v, w); Addedge(v, u, 0);
    }
    int maxflow = 0, tmp;
    while (Bfs())
    {
        tmp = Dinic(s, INF);
        if (tmp) maxflow += tmp;
    }
    Put(maxflow);
    return 0;
}

士兵占领

传送门

\(Dining\)

每个\(S\)向饮料连一条容量为\(1\)的有向边。

每个食物向\(T\)连一条容量为\(1\)的有向边。

这样是为了限制每个饮料和食物都只能用一次。

把每个奶牛拆成两个点，之间连上一条容量为\(1\)的有向边。

限制奶牛只会被满足一次要求。

然后每个奶牛喜欢的饮料向奶牛连容量为\(1\)的有向边，每个奶牛向它喜欢的食物连容量为\(1\)的有向边。

跑最大流即可。

最大获利

传送门

最小路径覆盖问题

首先每个点只能经过一次，所以把每个点\(i\)拆成两个点\(i_a\)和\(i_b\)之间连一条容量为\(1\)的有向边来限制。

\(S\)向每个\(i_a\)连一条容量为\(1\)的有向边。

每个\(i_b\)向\(T\)连容量为\(1\)的有向边。

这样连限制了每个点只能在一条路径上。

如果原图中有一条边\((u,v)\)，那么就从\(u_b\)向\(v_a\)连容量为\(1\)的有向边。

原图如果每个点都分配一条路径就是点数个路径。

如果照这样建图跑出来的最大流就是最多可以合并多少路径，每多合并一条路径，总的路径数量就减一。

那么需要的路径数就是点数减去最大流。

最长不下降子序列问题

首先动态规划求出\(f_i\)，表示以第\(i\)位为开头的最长上升序列的长度，求出最长上升序列长度\(k\)。

把序列每位\(i\)拆成两个点\(i_a\)和\(i_b\)，从\(i_a\)到\(i_b\)连接一条容量为\(1\)的有向边。

如果\(f_i = k\)，从\(S\)到\(i_a\)连接一条容量为\(1\)的有向边。

如果\(f_i = 1\)，从\(i_b\)到\(T\)连接一条容量为\(1\)的有向边。

如果\(j>i\)且\(a_i < a_j\)且\(f_j + 1 = f _i\)，从\(i_b\)到\(j_a\)连接一条容量为\(1\)的有向边。

求出最大流就是第二问的结果，第三问只要把\((1_a, 1_b)\)，\((n_a, n_b)\)，\((S, 1_a)\)，\((n_b, T)\)的容量改为\(INF\)即可。

方格取数问题

如果找出哪些点不取就变成最小割问题就可以跑最大流了。

如果取了一个点那么它四周的点都不能取，于是我们想到可以在中间连容量为\(INF\)的有向边边来限制。

继续观察发现不能同时取的两个点的横纵坐标之和的奇偶性不同。

那么我们按横纵坐标奇偶性分成两类，建立二分图。

\(S\)向每个横纵坐标之和为偶数位置连容量为权值的有向边，每个横纵坐标之和为奇数位置向\(T\)连容量为权值的有向边。

然后不能同时取的点连上就行了。

答案就是所有权值之和减去最大流。

魔术球问题

首先每个数拆成两个点\(i_a\)和\(i_b\)，如果\(j\)能放在\(i\)的上面就从\(i_b\)向\(j_a\)连容量为\(1\)的有向边。

然后和最小路径覆盖问题一样建图。

发现最小路径覆盖数就是最少所需要的柱子数量。

一个一个数加进残量网络直到最少所需柱子数量大于\(n\)，答案就是此时加进去的数的个数减一。

圆桌问题

\(S\)向每个单位连容量为\(r_i\)的有向边；每个桌子向\(T\)连容量为\(c_i\)的有向边。

每个单位向每个桌子连容量为\(1\)的有向边。

最大流如果是所有人的总数则有解。

\(happiness\)

传送门

文理分科

传送门

家园 / 星际转移问题

传送门

费用流

\(Dinic + Spfa\)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int INF = 1e9;
const int N = 100050;

int n, m, s, t, head[N], q[N], cur[N], vis[N], l, r, ans, maxflow, num = 1, dis[N], nxt[N];

struct Node
{
	int to, flow, dis;	
} edge[N * 2];

template <class T>
void Read(T &x)
{
	x = 0; int p = 0; char st = getchar();
	while (st < '0' || st > '9') p = (st == '-'), st = getchar();
	while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) +st - '0', st = getchar();	
	x = p ? -x : x;
	return;
} 

template <class T>
void Put(T x)
{
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) Put(x / 10);
	putchar(x % 10 + '0');
	return; 
}

void Addedge(int u, int v, int w, int c)
{
	edge[++num] = (Node){v, w, c};
	nxt[num] = head[u];
	head[u] = num;
	return;
}

int Bfs()
{
	for (int i = 1; i <= n; i++) vis[i] = 0, dis[i] = INF;
	dis[s] = 0; l = 0; r = 1; q[1] = s;
	while (l < r)
	{
		int u = q[++l]; vis[u] = 0;
		for(int i = head[u]; i != -1; i = nxt[i])
		{
			int v = edge[i].to;
			if (dis[u] + edge[i].dis < dis[v] && edge[i].flow > 0)
			{
				dis[v] = dis[u] + edge[i].dis;
				if (!vis[v])
				{
					if (dis[v] < dis[q[l + 1]]) q[l--] = v;
					else q[++r] = v;
					vis[v] = 1;
				}
			}
		}
	}
	return dis[t] != INF;
}

int Dinic(int x, int flow)
{
	if (x == t || !flow) return flow;
	int add = 0, f;
	vis[x] = 1;
	for (int i = cur[x]; i != -1 && flow > 0; i = nxt[i])
	{
		cur[x] = i;
		int v = edge[i].to;
		if (!vis[v] && dis[v] == dis[x] + edge[i].dis && edge[i].flow > 0 && (f = Dinic(v, min(edge[i].flow, flow))))
		{
			add += f;
			ans += f * edge[i].dis;
			edge[i].flow -= f;
			edge[i ^ 1].flow += f;
			flow -= f;
		}
	}
	vis[x] = 0;
	return add;
}

void Solve()
{
	while (Bfs())
	{
		for (int i = 1; i <= n; i++) cur[i] = head[i];
		maxflow += Dinic(s, INF);
	}
	return;
}

int main()
{
	Read(n); Read(m); Read(s); Read(t);
	for (int i = 1; i <= n; i++) head[i] = -1, dis[i] = INF;
	for (int i = 1; i <= m; i++)
	{
		int u, v, w, c;
		Read(u); Read(v); Read(w); Read(c);
		Addedge(u, v, w, c); Addedge(v, u, 0, -c);
	}
	Solve();
	Put(maxflow); putchar(' '); Put(ans);
	return 0;
}