【知识】网络流模板梳理&题型总结

Star_F等级-LV1-牛翰网6个月前更新
80

基础知识 ，OI-Wiki ，网络流24题 ，大佬博客

模板：

EK 求最大流

here 

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1005, M = 20005,INF=1e8;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], pre[N];
bool st[N];
void add(int a,int b,int c){
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs(){
    int hh = 0, tt = 0;
    memset(st, 0, sizeof(st));
    q[0] = S, st[S] = 1,d[S] = INF;

    while(hh<=tt){
        int t = q[hh++];
        for (int i = h[t]; ~i;i=ne[i]){
            int ver = e[i];
            if(!st[ver]&&f[i]){
                st[ver] = 1;
                d[ver] = min(d[t], f[i]);
                pre[ver] = i;
                if(ver==T) return 1;
                    q[++tt] = ver;
            }
        }
    }
    return 0;
}
int EK(){
    int r = 0; 
    while(bfs()){
        r += d[T];
        for (int i = T; i != S;i=e[pre[i]^1])
            f[pre[i]] -= d[T], f[pre[i]^1] += d[T];
    }
    return r;
}
int main(){
    memset(h, -1, sizeof(h));
    cin >> n >> m >> S >> T;
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << EK() << endl;
    return 0;
}

Dinic 求最大流

here 

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

const int N = 10005, M = 200005, INF = 1e8;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];

void add(int a,int b,int c){
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool bfs(){
    int hh = 0, tt = 0;
    memset(d, -1, sizeof(d));
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while(hh<=tt){
        int t = q[hh++];
        for (int i = h[t]; ~i;i=ne[i]){
            int ver = e[i];
            if(d[ver]==-1&&f[i]){
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if(ver==T)
                    return 1;
                q[++tt] = ver;
            }
        }
    }
    return 0;
}

int find(int u,int limit){
    if(u==T)
        return limit;
    int flow = 0;
    for (int i = cur[u]; ~i&&flow<limit;i=ne[i]){
        cur[u] = i;
        int ver = e[i];
        if(d[ver]==d[u]+1&&f[i]){
            int t = find(ver, min(f[i], limit - flow));
            if(!t) d[ver]=-1;
            f[i] -= t, f[i ^ 1] += t;
            flow += t;
        }
    }
    return flow;
}
int dinic(){
    int r = 0, flow;
    while(bfs()){
        while(flow=find(S,INF))
            r += flow;
    }
    return r;
}
int main(){
    memset(h, -1, sizeof(h));
    cin >> n >> m >> S >> T;
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, 0);
    }

    cout << dinic() << endl;
    return 0;
}

匈牙利算法

here 

#include <bits/stdc++.h>
using namespace std;
const int N = 10005, M = 200005;
int h[N], ne[M], cnt, e[M];
int match[N],vis[N];
int ans;
void add(int a,int b){
    e[++cnt] = b,ne[cnt] = h[a],h[a] = cnt;
}
bool dfs(int x){
    for (int i = h[x]; i;i=ne[i]){
        int to = e[i];
        if(vis[to])
            continue;
        vis[to] = 1;
        if(match[to]==0||dfs(match[to])){
            match[to] = x;
            return true;
        }
    }
    return false;
}
int main(){
    int n, m, e;
    cin >> n >> m >> e;
    for (int i = 1; i <= e;i++){
        int u, v;
        cin >> u >> v;
        add(u, v + n);
        add(v + n, u);
    }
    for (int i = 1; i <= n;i++){
        memset(vis, 0, sizeof(vis));
        if(dfs(i))
            ans++;
    }
    cout << ans << endl;
    return 0;
}

Minimum Cut(最小割)

点击查看代码 

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010, M = 200010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];

void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0, flow;
    while (bfs()) while (flow = find(S, INF)) r += flow;
    return r;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &S, &T);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    printf("%d\n", dinic());
    return 0;
}

题型思路总结：

  • P2756 飞行员配对方案问题

  • 思路：

    • 解法一：
      观察到给定的图是一个二分图，求的就是二分图的最大匹配即可，时间复杂度 \(\mathcal{O}(nm)\)
    • 解法二：
      网络流算法。从源点 \(S\) 向 点集 \(N\) 的每个点连接一个容量为 \(1\) 的边，代表每名飞行员只能匹配一次。 从点集 \(M\) 向汇点 \(T\) 连接一个容量为 \(1\) 的边，因为能量守恒，所以代表 \(M\) 点集里的同一个点不能多次使用，因为一旦多次使用会违背能量守恒定律。建图后跑 dinic 求最大流即可。时间复杂度 \(\mathcal{O}(\sqrt nm)\)

  • 代码：

    here 

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

const int N = 10005, M = 200005, INF = 1e8;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];

void add(int a,int b,int c){
	e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool bfs(){
	int hh = 0, tt = 0;
	memset(d, -1, sizeof(d));
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while(hh<=tt){
		int t = q[hh++];
		for (int i = h[t]; ~i;i=ne[i]){
			int ver = e[i];
			if(d[ver]==-1&&f[i]){
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if(ver==T)
					return 1;
				q[++tt] = ver;
			}
		}
	}
	return 0;
}

int find(int u,int limit){
	if(u==T)
		return limit;
	int flow = 0;
	for (int i = cur[u]; ~i&&flow<limit;i=ne[i]){
		cur[u] = i;
		int ver = e[i];
		if(d[ver]==d[u]+1&&f[i]){
			int t = find(ver, min(f[i], limit - flow));
			if(!t) d[ver]=-1;
			f[i] -= t, f[i ^ 1] += t;
			flow += t;
		}
	}
	return flow;
}
int dinic(){
	int r = 0, flow;
	while(bfs()){
		while(flow=find(S,INF))
			r += flow;
	}
	return r;
}
int main(){
	memset(h, -1, sizeof(h));
	cin >> m >> n;
	S = 0, T = n + 1;
	for (int i = 1; i <= m;i++)
		add(S, i, 1), add(i, S, 0);
	for (int i = m + 1; i <= n;i++)
		add(i, T, 1), add(T, i, 0);
	int a, b;
	while(cin>>a>>b,a!=-1)
		add(a, b, 1), add(b, a, 0);
	cout << dinic() << endl;

	for (int i = 0; i < idx;i+=2){
		if(e[i]>m&&e[i]<=n&&!f[i])
			cout << e[i ^ 1] << " " << e[i] << endl;
	}
		return 0;
}

  • P3254 圆桌问题

  • 思路：

    • 建一个超级源点，向每个单位连一条为单位人数的边
    • 建个单位向每个桌子连一条为1的边(同一个单位的人不能在同一个桌子上)
    • 建一个超级汇点，每个桌子向汇点连一条为桌子容量的边

    跑一遍最大流，如果最大流量等于所有单位人数之和，则存在解，否则无解。

    输出方案：从每个单位出发的所有满流边指向的桌子就是该单位人员的安排情况。

  • 代码：

    here 

      #include <bits/stdc++.h>
  using namespace std;
  const int N = 430, M = (150 * 270 + N) * 2, INF = 1e8;
  int m, n, S, T;
  int h[N], e[M], f[M], ne[M], idx;
  int q[N], d[N], cur[N];
  void add(int a, int b, int c){
  	e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
  	e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
  }

  bool bfs(){
  	int hh = 0, tt = 0;
  	memset(d, -1, sizeof d);
  	q[0] = S, d[S] = 0, cur[S] = h[S];
  	while (hh <= tt){
  		int t = q[hh ++ ];
  		for (int i = h[t]; ~i; i = ne[i]){
  			int ver = e[i];
  			if (d[ver] == -1 && f[i]){
  				d[ver] = d[t] + 1;
  				cur[ver] = h[ver];
  				if (ver == T) return true;
  				q[ ++ tt] = ver;
  			}
  		}
  	}
  	return false;
  }

  int find(int u, int limit){
  	if (u == T) return limit;
  	int flow = 0;
  	for (int i = cur[u]; ~i && flow < limit; i = ne[i]){
  		cur[u] = i;
  		int ver = e[i];
  		if (d[ver] == d[u] + 1 && f[i]){
  			int t = find(ver, min(f[i], limit - flow));
  			if (!t) d[ver] = -1;
  			f[i] -= t, f[i ^ 1] += t, flow += t;
  		}
  	}
  	return flow;
  }

  int dinic(){
  	int r = 0, flow;
  	while (bfs()) while (flow = find(S, INF)) r += flow;
  	return r;
  }

  int main(){
  	scanf("%d%d", &m, &n);
  	S = 0, T = m + n + 1;
  	memset(h, -1, sizeof h);

  	int tot = 0;
  	for (int i = 1; i <= m; i ++ ){
  		int c;
  		scanf("%d", &c);
  		add(S, i, c);
  		tot += c;
  	}
  	for (int i = 1; i <= n; i ++ ){
  		int c;
  		scanf("%d", &c);
  		add(m + i, T, c);
  	}
  	for (int i = 1; i <= m; i ++ )
  		for (int j = 1; j <= n; j ++ )
  			add(i, m + j, 1);

  	if (dinic() != tot) puts("0");
  	else{
  		puts("1");
  		for (int i = 1; i <= m; i ++ ){
  			for (int j = h[i]; ~j; j = ne[j])
  				if (e[j] > m && e[j] <= m + n && !f[j])
  					printf("%d ", e[j] - m);
  			puts("");
  		}
  	}

  	return 0;
  }

  • 上下界网络流

    设 \(\operatorname{l}(u,\,v)\) 为 \(u \to v\) 的下界函数，特别的，当 \(u \to v \notin {\mathrm E}\) 时，\(\operatorname{l}(u,\,v) = 0\)。

    定义图 \(\mathrm G = \langle \mathrm {V,\,E} \rangle\) 上的流函数 \(\operatorname{f} : \mathrm {V \times V} \to \mathbb R\)，满足如下限制：

    • 容量限制： 对于 \(\forall u,\,v \in {\mathrm V}\) 有 \(\operatorname{l}(u,\,v) \le \operatorname{f}(u,\,v) \le \operatorname{c}(u,\,v)\)。
    • 流量守恒： 对于 \(\forall u \in {\mathrm{V}}-\{s,\,t\}\)，要求：\(\begin{aligned} & \sum_{v \in {\mathrm{V}}}\operatorname{f}(u,\,v)=\sum_{v \in {\mathrm{V}}}\operatorname{f}(v,\,u) \end{aligned}\)

    则称非负值 \(\operatorname{f}(u,\,v)\) 为图 \(\mathrm {G = \langle V,\,E \rangle}\) 的一个可行流。

    一个流的流值 \(|f|\) 定义如下：

    \[\begin{aligned} & |f| = \sum_{v \in {\mathrm{V}}}\operatorname{f}(s,\,v)-\sum_{v \in {\mathrm{V}}}\operatorname{f}(v,\,s) \end{aligned} \]

  • 无源汇上下界可行流

    给定一个特殊点 \(s\) 和一个特殊点 \(t\)，找出从 \(s\) 到 \(t\) 的一个流 \(\operatorname{f}(s,\,t)\)，使得 \(|f|\) 的值最大。

    无源汇上下界可行流就是没有源汇的情况下，求出图 \(\mathrm G = \langle \mathrm{V,\,E} \rangle\) 的一个可行流。

    对于每条边，我们可以用上界减去下界得到差值网络。

    建模方法如下：

    • 设 \(\operatorname{in}(u)\) 为 \(u\) 的所有入边的容量的总和，\(\operatorname{out}(u)\) 为 \(u\) 的所有出边的容量的总和。
    • 计算 \(w = \operatorname{in}(u)-\operatorname{out}(u)\)。
    • 如果 \(w > 0\)，则从超级源点 \(s\) 向 \(u\) 连一条容量为 \(w\) 的边。如果 \(w <0\)，则从 \(u\) 向超级汇点 \(t\) 连容量为 \(-w\) 的边。
    • 跑最大流，如果存在附加边没满流，则不存在可行流，否则 \(\mathrm maxflow\) 加上所有边的下界的和即为可行流的流值。

    添加附加边维护了平衡条件，加上 下界网络就相当于得到了一个流量平衡的残余网络。

    here 

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, M = (10200 + N) * 2, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], l[M], ne[M], idx;
int q[N], d[N], cur[N], A[N];

void add(int a, int b, int c, int d)
{
    e[idx] = b, f[idx] = d - c, l[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0, flow;
    while (bfs()) while (flow = find(S, INF)) r += flow;
    return r;
}

int main()
{
    scanf("%d%d", &n, &m);
    S = 0, T = n + 1;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        add(a, b, c, d);
        A[a] -= c, A[b] += c;
    }

    int tot = 0;
    for (int i = 1; i <= n; i ++ )
        if (A[i] > 0) add(S, i, 0, A[i]), tot += A[i];
        else if (A[i] < 0) add(i, T, 0, -A[i]);

    if (dinic() != tot) puts("NO");
    else
    {
        puts("YES");
        for (int i = 0; i < m * 2; i += 2)
            printf("%d\n", f[i ^ 1] + l[i]);
    }
    return 0;
}

  • 有源汇上下界可行流

    即使添加了源点 \(s\) 和汇点 \(t\)，我们仍然可以通过从 \(t\) 到 \(s\) 添加一条下界为 0、上界为 \(+\infty\) 的边，将问题转化为无源汇上下界可行流问题，直接求解。此时，可行流的容量等于从 \(t\) 到 \(s\) 的边的容量。

    此时，原图的源点和汇点已视为普通点，而添加的超级源点和汇点分别为 \(s’\) 和 \(t’\)。可行流的容量就是从 \(t\) 到 \(s\) 的附加边的容量。

  • 有源汇上下界最大流

    在可行流的基础上，删除所有附加边后，使用原源汇节点求解一次最大流，再加上可行流的值即为最终答案。

    因为如果存在可行流，原网络一定是平衡的，当前网络同样平衡，满足平衡条件，因此是正确的。

    实际上，不必删除所有附加边，只需要删除 \(t\) 到 \(s\) 的附加边，因为这两个入度为 0 或出度为 0 的节点对最大流的计算没有影响。

    here 

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, M = (N + 10000) * 2, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N], A[N];

void add(int a, int b, int c)
{
	e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i])
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

int find(int u, int limit)
{
	if (u == T) return limit;
	int flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i])
		{
			int t = find(ver, min(f[i], limit - flow));
			if (!t) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r;
}

int main()
{
	int s, t;
	scanf("%d%d%d%d", &n, &m, &s, &t);
	S = 0, T = n + 1;
	memset(h, -1, sizeof h);
	while (m -- )
	{
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		add(a, b, d - c);
		A[a] -= c, A[b] += c;
	}

	int tot = 0;
	for (int i = 1; i <= n; i ++ )
		if (A[i] > 0) add(S, i, A[i]), tot += A[i];
		else if (A[i] < 0) add(i, T, -A[i]);

	add(t, s, INF);
	if (dinic() < tot) puts("No Solution");
	else
	{
		int res = f[idx - 1];
		S = s, T = t;
		f[idx - 1] = f[idx - 2] = 0;
		printf("%d\n", res + dinic());
	}
	return 0;
}

  • 有源汇上下界最小流

    和 有源汇上下界最小流 思路基本相同。
    反向跑一边最大流，相当于流回去最大，那么就是最小流。
    答案 \(=\) 可行流 \(-\) 反向最大流

    点击查看代码 

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010, M = (N + 125003) * 2, INF = 2147483647;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N], A[N];

void add(int a, int b, int c)
{
	e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i])
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

int find(int u, int limit)
{
	if (u == T) return limit;
	int flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i])
		{
			int t = find(ver, min(f[i], limit - flow));
			if (!t) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r;
}

int main()
{
	int s, t;
	scanf("%d%d%d%d", &n, &m, &s, &t);
	S = 0, T = n + 1;
	memset(h, -1, sizeof h);
	while (m -- )
	{
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		add(a, b, d - c);
		A[a] -= c, A[b] += c;
	}

	int tot = 0;
	for (int i = 1; i <= n; i ++ )
		if (A[i] > 0) add(S, i, A[i]), tot += A[i];
		else if (A[i] < 0) add(i, T, -A[i]);

	add(t, s, INF);

	if (dinic() < tot) puts("No Solution");
	else
	{
		int res = f[idx - 1];
		S = t, T = s;
		f[idx - 1] = f[idx - 2] = 0;
		printf("%d\n", res - dinic());
	}

	return 0;
}

  • 多源汇最大流

    • 建立一个超级源点 \(S\)，向每个 \(s\) 连一条容量为 $+\infty $ 的边。
    • 建立一个超级汇点 \(T\)，每个 \(t\) 向 \(T\) 连一条容量为 $+\infty $ 的边。

    \(S \to T\) 的最大流即为原图多源汇最大流。

    here 

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010, M = (100000 + N) * 2, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];

void add(int a, int b, int c)
{
	e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i])
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

int find(int u, int limit)
{
	if (u == T) return limit;
	int flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i])
		{
			int t = find(ver, min(f[i], limit - flow));
			if (!t) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r;
}

int main()
{
	int sc, tc;
	scanf("%d%d%d%d", &n, &m, &sc, &tc);
	S = 0, T = n + 1;
	memset(h, -1, sizeof h);
	while (sc -- )
	{
		int x;
		scanf("%d", &x);
		add(S, x, INF);
	}
	while (tc -- )
	{
		int x;
		scanf("%d", &x);
		add(x, T, INF);
	}

	while (m -- )
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}

	printf("%d\n", dinic());
	return 0;
}

  • Ikki’s Story I – Road Reconstruction

    简要题意：改变一条边的容量使得最大流变大。

    先求一遍最大流，可以发现关键边一定是满流的边
    证明：如果存在某条边没有满流且是关键边，即会有流量经过该条边，同样可以整体将流量减少至其原容量其仍然有流量增加，即存在增广路，与最大流不存在增广路矛盾，故关键边只可能是满流的边。
    同时，对于满流的边也不一定是关键边，对于一条 \(u \to v\) 满流的边，增加其容量的同时，要找到一条增广路，即必须找到 \(s \to u\)，\(v \to t\) 的路径，且路径上所有边未满流，可以 dfs 预处理这样的点

    时间复杂度：\(\mathcal{O}(n^2m)\)

    here 

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
bool vis_s[N], vis_t[N];

void add(int a, int b, int c)
{
	e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i])
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

int find(int u, int limit)
{
	if (u == T) return limit;
	int flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i])
		{
			int t = find(ver, min(f[i], limit - flow));
			if (!t) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r;
}

void dfs(int u, bool st[], int t)
{
	st[u] = true;
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = i ^ t, ver = e[i];
		if (f[j] && !st[ver])
			dfs(ver, st, t);
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	S = 0, T = n - 1;
	memset(h, -1, sizeof h);
	for (int i = 0; i < m; i ++ )
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}

	dinic();
	dfs(S, vis_s, 0);
	dfs(T, vis_t, 1);

	int res = 0;
	for (int i = 0; i < m * 2; i += 2)
		if (!f[i] && vis_s[e[i ^ 1]] && vis_t[e[i]])
			res ++ ;

	printf("%d\n", res);
	return 0;
}

  • P1674 [USACO05FEB] Secret Milking Machine G

    二分 + dinic

    二分，把边权小于等于 mid 的边的边权改为 1，大于的改为 0。

    设源点为 1，汇点为 N，将无向图变为有向图（就是无向图中的每一条边都建正反两边），然后每次在二分时判断一下新建好的这个图中的最大流是否大于 T 即可。

    但是，这里有一个问题：在题目中，要求一条路只能走一次，但在我们新建的有向图中，无向图中的边都已转化成两条边，所以相当于每一条路都有可能走两边。

    其实我们不用担心，因为在网络流中，正向流一次，再反向流一次后，就相当于没流，抵消了。

    进一步，我们发现，在代码上有一个空间上的小优化：在建残余网络时，我们还需要原网络中的每一条边再建一个正边和反边。也就是说题目中无向图的每一条边对应到我们的残余网络中，都有 \(4\) 条边。所以为了节省一下空间，我们可以将方向相同的两条边合并。

    时间复杂度：\(\mathcal{O}(n^2 \times m \times \log m)\)

    here 

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, M = 80010, INF = 1e8;

int n, m, K, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], cur[N];

void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, w[idx] = c, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i])
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

int find(int u, int limit)
{
	if (u == T) return limit;
	int flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i])
		{
			int t = find(ver, min(f[i], limit - flow));
			if (!t) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r;
}

bool check(int mid)
{
	for (int i = 0; i < idx; i ++ )
		if (w[i] > mid) f[i] = 0;
		else f[i] = 1;

	return dinic() >= K;
}

int main()
{
	scanf("%d%d%d", &n, &m, &K);
	S = 1, T = n;
	memset(h, -1, sizeof h);
	while (m -- )
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}

	int l = 1, r = 1e6;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}

	printf("%d\n", r);

	return 0;
}

  • P2754 [CTSC1999] 家园 / 星际转移问题

    分层图+dinic。

    注意到时间不好处理，加上数据非常小，考虑分层图。所有的点代表第 \(i\) 个星际站或星体在第 \(t\) 个时刻的情况。

    建立超级源点和汇点 \(S,T\)。

    • 源点向初始地球连边，初始月球向汇点连边，地球月球和空间站向它们下一个时刻的位置连边，以上边容量都是 \(+\infty\)。
    • 星际飞船 \(i\)，从当前位置连向下一个时刻的下一个位置连一条容量为可容纳的人数 \(H_i\) 的边。

    每次图会扩展一层，重新跑一遍 dinic，若最大流 \(\geq k\) 则当前时刻可行，输出即可。

    初始的时候用并查集判一下月地是否连通，不连通则无解。

    here 

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1101 * 50 + 10, M = (N + 1100 + 20 * 1101) + 10, INF = 1e8;

int n, m, k, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
struct Ship
{
	int h, r, id[30];
}ships[30];
int p[30];

int find(int x)
{
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}

int get(int i, int day)
{
	return day * (n + 2) + i;
}

void add(int a, int b, int c)
{
	e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i])
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

int find(int u, int limit)
{
	if (u == T) return limit;
	int flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i])
		{
			int t = find(ver, min(f[i], limit - flow));
			if (!t) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r;
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	S = N - 2, T = N - 1;
	memset(h, -1, sizeof h);
	for (int i = 0; i < 30; i ++ ) p[i] = i;
	for (int i = 0; i < m; i ++ )
	{
		int a, b;
		scanf("%d%d", &a, &b);
		ships[i] = {a, b};
		for (int j = 0; j < b; j ++ )
		{
			int id;
			scanf("%d", &id);
			if (id == -1) id = n + 1;
			ships[i].id[j] = id;
			if (j)
			{
				int x = ships[i].id[j - 1];
				p[find(x)] = find(id);
			}
		}
	}
	if (find(0) != find(n + 1)) puts("0");
	else
	{
		add(S, get(0, 0), k);
		add(get(n + 1, 0), T, INF);
		int day = 1, res = 0;
		while (true)
		{
			add(get(n + 1, day), T, INF);
			for (int i = 0; i <= n + 1; i ++ )
				add(get(i, day - 1), get(i, day), INF);
			for (int i = 0; i < m; i ++ )
			{
				int r = ships[i].r;
				int a = ships[i].id[(day - 1) % r], b = ships[i].id[day % r];
				add(get(a, day - 1), get(b, day), ships[i].h);
			}
			res += dinic();
			if (res >= k) break;
			day ++ ;
		}

		printf("%d\n", day);
	}

	return 0;
}

  • P2891 [USACO07OPEN] Dining G

    拆点 + dinic

    构建图时，左边是食物，中间是奶牛，右边是饮料。源点 \(S\) 连向所有食物，汇点 \(T\) 连向所有饮料，每条边的容量为 \(1\)。奶牛与食物、饮料的连接按其喜好建立反向和正向边，容量为 \(1\)。

    由于每只奶牛只能使用一次流量，我们将每个奶牛节点拆成两个节点：入点和出点。食物连向入点，出点连向饮料，入点和出点之间建一条容量为 1 的边，确保流量只能经过一个奶牛节点一次。

    最后，通过最大流算法求解最大配对数，即最大流量。

    时间复杂度为 \(\mathcal{O}(n^2 m)\)。

    here 

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 410, M = 40610, INF = 1e8;

int n, F, D, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];

void add(int a, int b, int c)
{
	e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i])
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

int find(int u, int limit)
{
	if (u == T) return limit;
	int flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i])
		{
			int t = find(ver, min(f[i], limit - flow));
			if (!t) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r;
}

int main()
{
	scanf("%d%d%d", &n, &F, &D);
	S = 0, T = n * 2 + F + D + 1;
	memset(h, -1, sizeof h);
	for (int i = 1; i <= F; i ++ ) add(S, n * 2 + i, 1);
	for (int i = 1; i <= D; i ++ ) add(n * 2 + F + i, T, 1);
	for (int i = 1; i <= n; i ++ )
	{
		add(i, n + i, 1);
		int a, b, t;
		scanf("%d%d", &a, &b);
		while (a -- )
		{
			scanf("%d", &t);
			add(n * 2 + t, i, 1);
		}
		while (b -- )
		{
			scanf("%d", &t);
			add(i + n, n * 2 + F + t, 1);
		}
	}
	printf("%d\n", dinic());
	return 0;
}

  • P2766 最长不下降子序列问题

    Task 1：

    经典 DP 令 \(f(i)\) 表示选择 \(a_i\) 作为递增子序列的最后一个数所能得到的最长长度，易得

    \[f(i) = \max_{j < i, a_j \le a_i}\lbrace f(j)\rbrace + 1 \]

    \(\max\lbrace f(i)\rbrace\) 记作 \(s\)

    Task 2：
    我们考虑子序列是怎么生成的：设当前序列的结尾是 \(a_i\)，往后拓展序列时，我们会选择\(a_i \le a_j, i < j\) 的 \(a_j\)

    于是我们将所有\(a_i \le a_j, i < j\)的点对\((i, j)\)连边，形成的图记作 G

    对于所有入度为0的点

    从超级源点向其连边，容量均为 \(1\)。表示可以从这个点开始进行子序列的选择。
    从这个点进行BFS，找出 G 中从该点经\(s – 1\)个点能到达的全部点，打上标记。表示该点与搜索出的点能形成 \(s\) 个点组成的路径，即能构造出长度为 \(s\) 的子序列
    接着对于打上标记的点，向超级汇点连边，容量均为 \(1\)

    跑一遍最大流即可

    Task 3：

    这就简单了，将超级源点向 \(1\) 的边与 \(n\) 向超级汇点的容量设为 \(+\infty\) 即可

    here 

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010, M = 251010, INF = 1e8;

int n, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
int g[N], w[N];

void add(int a, int b, int c)
{
	e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i])
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

int find(int u, int limit)
{
	if (u == T) return limit;
	int flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i])
		{
			int t = find(ver, min(f[i], limit - flow));
			if (!t) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r;
}

int main()
{
	scanf("%d", &n);
	S = 0, T = n * 2 + 1;
	memset(h, -1, sizeof h);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
	int s = 0;
	for (int i = 1; i <= n; i ++ )
	{
		add(i, i + n, 1);
		g[i] = 1;
		for (int j = 1; j < i; j ++ )
			if (w[j] <= w[i])
				g[i] = max(g[i], g[j] + 1);
		for (int j = 1; j < i; j ++ )
			if (w[j] <= w[i] && g[j] + 1 == g[i])
				add(n + j, i, 1);
		s = max(s, g[i]);
		if (g[i] == 1) add(S, i, 1);
	}

	for (int i = 1; i <= n; i ++ )
		if (g[i] == s)
			add(n + i, T, 1);

	printf("%d\n", s);
	if (s == 1) printf("%d\n%d\n", n, n);
	else
	{
		int res = dinic();
		printf("%d\n", res);
		for (int i = 0; i < idx; i += 2)
		{
			int a = e[i ^ 1], b = e[i];
			if (a == S && b == 1) f[i] = INF;
			else if (a == 1 && b == n + 1) f[i] = INF;
			else if (a == n && b == n + n) f[i] = INF;
			else if (a == n + n && b == T) f[i] = INF;
		}
		printf("%d\n", res + dinic());
	}

	return 0;
}

  • March of the Penguins

    拆点 + dinic
    因为有很多冰块上有企鹅，所以建立一个超级源点，把有源点向冰块连一条边，容量为当前冰块上企鹅的数量。

    把最终的终点看做汇点，由于本题的汇点不确定，而且数据范围很小，所以可以枚举汇点。

    再考虑冰块之间如何连边，如果两个冰块可以相互跳跃，即两个冰块的距离是在企鹅可以跳跃距离的范围内的，就可以连一条双向边，也就是互相连边。

    现在思考如何将次数限制加到流网络中，如果把冰块的起跳次数直接加到当前冰块的出边上，会发现可能会超过冰块起跳的限制，所以不能这样做。

    因为这个问题是对点有流量限制，所以我们考虑如何拆点。

    把每一个点都拆成一个入点和一个出点。

    现在，我们就可以把到这个点的边连到这个点的入点上，把离开这个点的边连到出点上，当然，入点到出点也要连一条边，这条边的容量为这个冰块的可以起跳的次数，这样是为了限制从这个冰块起跳的企鹅数量。

    这样，本题的图就建立完成了。

    以下分析本流网络的可行流是不是与原问题的解是一一对应的。

    我们可以把每只企鹅跳过的边的流量加一，这样就得到了一个可行流。

    判断可行流只需要判断两点，一是流量守恒，还有一个是容量限制。

    容量限制显然是满足的，因为刚才我们已经把所以限制都加到了流网络里了。

    流量守恒也是满足的，因为企鹅不可能在除了源点和汇点停留的，所以流量也是守恒的。

    反推回去也是可以得到一个合法解的，所以原问题任何一个企鹅跳跃的方案都是可以对应到我们建立的流网络里的可行流。

    如何判断一个方案是不是合法的呢？相当于判断流网络里的企鹅是不是都能流到汇点，直接求一下最大可行流是不是企鹅的总数就可以了，如果是，就说明当前汇点是一个可行点。

    here 

    #include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 210, M = 20410, INF = 1e8;
const double eps = 1e-8;

int n, S, T;
double D;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
PII p[N];

bool check(PII a, PII b)
{
	double dx = a.x - b.x, dy = a.y - b.y;
	return dx * dx + dy * dy < D * D + eps;
}

void add(int a, int b, int c)
{
	e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i])
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

int find(int u, int limit)
{
	if (u == T) return limit;
	int flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i])
		{
			int t = find(ver, min(f[i], limit - flow));
			if (!t) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r;
}

int main()
{
	int cases;
	scanf("%d", &cases);
	while (cases -- )
	{
		memset(h, -1, sizeof h);
		idx = 0;
		scanf("%d%lf", &n, &D);
		S = 0;

		int tot = 0;
		for (int i = 1; i <= n; i ++ )
		{
			int x, y, a, b;
			scanf("%d%d%d%d", &x, &y, &a, &b);
			p[i] = {x, y};
			add(S, i, a);
			add(i, n + i, b);
			tot += a;
		}

		for (int i = 1; i <= n; i ++ )
			for (int j = i + 1; j <= n; j ++ )
				if (check(p[i], p[j]))
				{
					add(n + i, j, INF);
					add(n + j, i, INF);
				}

		int cnt = 0;
		vector<int> tmp;
		for (int i = 1; i <= n; i ++ )
		{
			T = i;
			for (int j = 0; j < idx; j += 2)
			{
				f[j] += f[j ^ 1];
				f[j ^ 1] = 0;
			}
			if (dinic() == tot)
			{
				tmp.push_back(i - 1);
				cnt ++ ;
			}
		}
		if (!cnt) cout<<-1<<endl;
		else{
			for (int i = 0; i < tmp.size()-1;i++)
				cout << tmp[i] <<" ";
			cout<<tmp[tmp.size()-1];
			cout<<endl;
		}
	}
	return 0;
}

  • PIGS

    我们总结一下，题目的操作。

    每名顾客按顺序进行

    • 将自己有钥匙的猪舍打开，从中挑选一些不超过自己想买的数量的猪。
    • 同时可以将，打开的猪舍中的猪进行调整

    这里面，我们需要一个逆向思维

    我们考虑打开的猪舍中的所有猪都先被顾客取走，然后只拿走自己想要的部分，其余部分在自由的返回给打开的猪舍中

    我们首先考虑的是，那我们是否可以直接，从顾客能打开的猪舍向顾客连一条边，接着再从顾客向所有能打开的猪舍连一条边，容量都是 \(+\infty\)。

    不行，这显然是不对的，因为我们需要考虑顺序问题，每一位顾客是在上一位的基础上挑选的。是不是发现了什么， 我们发现，这是逐层递推的，那我们可以建立分层图，以顾客的顺序建立，这样就能一步步递推了。

    以每个买猪的作为点，并建立原点和汇点。

    每个猪圈的第一个访客和原点连一条该猪圈中猪数量的边，每个猪圈的访客（除了以第一个）和上一个访问这个猪圈的人连一条 \(+\infty\) 的边，每个人向汇点连一条最多买的数量的边。

    here 

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 100200 * 2 + 10, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
int w[1010], belong[1010];

void add(int a, int b, int c)
{
	e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i])
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

int find(int u, int limit)
{
	if (u == T) return limit;
	int flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i])
		{
			int t = find(ver, min(f[i], limit - flow));
			if (!t) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int r = 0, flow;
	while (bfs())
	{
		r += find(S, INF);
		flow = find(S, INF);
		if (flow) puts("!");
		r += flow;
	}
	return r;
}

int main()
{
	scanf("%d%d", &m, &n);
	S = 0, T = n + 1;
	memset(h, -1, sizeof h);
	for (int i = 1; i <= m; i ++ ) scanf("%d", &w[i]);
	for (int i = 1; i <= n; i ++ )
	{
		int a, b;
		scanf("%d", &a);
		while (a -- )
		{
			int t;
			scanf("%d", &t);
			if (!belong[t]) add(S, i, w[t]);
			else add(belong[t], i, INF);
			belong[t] = i;
		}
		scanf("%d", &b);
		add(i, T, b);
	}

	printf("%d\n", dinic());
	return 0;
}

  • 最小割

  • 网络战争

    本题要求的是最小化一个形如 \(\frac{\sum_{e \in C} w_e}{|C|}\) 的表达式，其中 \(C\) 是图中的一个边割集，\(w_e\) 是边 \(e\) 的权值，\(|C|\) 是边割集 \(C\) 的大小。我们可以利用 01 分数规划的思想来求解。

    首先，我们考虑一个值 \(x\)，并通过这个值 \(x\) 来判断边割集 \(C\) 的平均权值 \(\frac{\sum_{e \in C} w_e}{|C|}\) 与 \(x\) 的关系。为了简化问题，我们先从以下两个情况进行分析：

    1. 假设 \(\frac{\sum_{e \in C} w_e}{|C|} > x\)，我们可以将其变形为：

    \[\sum_{e \in C} w_e – |C| \cdot x > 0 \quad \Longrightarrow \quad \sum_{e \in C} (w_e – x) > 0 \]

    这个不等式表示边割集 \(C\) 的加权和减去 \(x\) 后的权值和大于 0。

    1. 假设 \(\frac{\sum_{e \in C} w_e}{|C|} < x\)，同样可以得到：

    \[\sum_{e \in C} (w_e – x) < 0 \]

    根据上述推导，我们可以通过判断 \(\sum_{e \in C} (w_e – x)\) 是否大于 0 来确定 \(\frac{\sum_{e \in C} w_e}{|C|}\) 与 \(x\) 的大小关系。这个关系是二段性的，适合使用二分法进行求解。

    二分

    在整个范围内进行二分，每次计算中间值 \(x\)，并根据 \(\sum_{e \in C} (w_e – x)\) 的符号来调整二分的区间。如果 \(\sum_{e \in C} (w_e – x) > 0\)，则说明 \(\frac{\sum_{e \in C} w_e}{|C|} > x\)，此时我们可以继续对右半区间进行二分；反之，如果 \(\sum_{e \in C} (w_e – x) < 0\)，则说明 \(\frac{\sum_{e \in C} w_e}{|C|} < x\)，此时对左半区间进行二分。通过不断缩小区间，最终可以找到最小值。

    计算 \(\sum_{e \in C} (w_e – x)\)

    为了计算 \(\sum_{e \in C} (w_e – x)\)，我们可以将图中的每条边的权值减去 \(x\)，得到新的边权。在这个新图中，边权为 \(w_e – x\) 的边如果 \(w_e – x \leq 0\) 时，我们一定会选上这些边，因为这些边会减少边割集的总权值，从而使得 \(\sum_{e \in C} (w_e – x)\) 更小。

    接下来，对于剩下的边（即 \(w_e – x > 0\) 的边），我们需要根据最小割的性质来决定哪些边应该选择。由于流网络中的割与边割集有所不同，边割集中的边要么连接两个集合中的节点，要么不连接。为了最小化总权值和，我们需要选择能够有效将图割开的边，而这些边正好对应于流网络中的最小割。

    答案：边割集的权值和 \(=\) 非正边的权值和 \(+\) 正边的权值和（最小割）

    here 

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 810, INF = 1e8;
const double eps = 1e-8;

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx;
double f[M];
int q[N], d[N], cur[N];

void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, w[idx] = c, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i] > 0)
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

double find(int u, double limit)
{
	if (u == T) return limit;
	double flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i] > 0)
		{
			double t = find(ver, min(f[i], limit - flow));
			if (t < eps) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

double dinic(double mid)
{
	double res = 0;
	for (int i = 0; i < idx; i += 2)
		if (w[i] <= mid)
		{
			res += w[i] - mid;
			f[i] = f[i ^ 1] = 0;
		}
		else f[i] = f[i ^ 1] = w[i] - mid;

	double r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r + res;
}

int main()
{
	scanf("%d%d%d%d", &n, &m, &S, &T);
	memset(h, -1, sizeof h);
	while (m -- )
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}

	double l = 0, r = 1e7;
	while (r - l > eps)
	{
		double mid = (l + r) / 2;
		if (dinic(mid) < 0) r = mid;
		else l = mid;
	}

	printf("%.2lf\n", r);
	return 0;
}

  • OPTM – Optimal Marks

    本题给我们一个无向图，然后我们给没有标号的点进行标号，使得所有边的费用和最小。

    每条边的费用是两个端点标号的异或和，异或运算是按位运算，因此我们可以每一位单独看，最终的费用和应该是每一位的和加起来。

    由于每一位完全独立，因此最终费用和的最小值其实就是求每一位的最小值，再合在一起，就是答案。

    由于每一位只有 \(0\) 和 \(1\) 两种可能，因此所有点可以分成两类，一类是 \(0\)，一类是 \(1\)。

    然后看一下点与点之间的边有哪些情况，\(0\) 和 \(0\) 之间的边费用就是 \(0\)，\(1\) 和 \(1\) 之间的边费用就是 \(0\)，\(0\) 和 \(1\) 之间的边费用就是 \(1\)。

    由此可以发现，当两类集合中的点确定之后，整个费用和的最小值就等于两个集合之间的边的数量最小值，也就是割。

    假设现在要计算第 \(k\) 位，若第 \(k\) 位中的两个集合之间的边的最小数量是 \(m\)，也就是有 \(m\) 个数第 \(k\) 位是 \(1\)，一个数第 \(k\) 位是 \(1\) 的费用是 \(2^k\)，那么 \(m\) 个的费用就是 \(m \cdot 2^k\)

    因此如果考虑第 \(k\) 位，就是要将所有点的第 \(k\) 位分成两类，使得两类之间的边的数量最小，这个问题和流网络中的割非常相似。

    我们将原图的无向边都在流网络里建两条有向边。然后我们对点集做一个划分，可以对应到流网络里割的划分。原问题中两个点集之间的边的权值之和就可以对应到两个割之间的割的容量。由于割的容量只会算一个方向，所以权值和也只会算一次，因此原问题中对所有点的划分方式都可以对应到割的划分方式，因此最小费用和就等于最小割（将中间的边的容量设为 \(1\)）。

    求最小割还需要一个源点和汇点，我们可以建立虚拟源点和虚拟汇点。

    有些点最开始是有编号的，如果有些点的标号是 \(0\)，说明他一定要和源点在一个集合，那么我们就从源点向这些点连一条容量是 \(+\infty\) 的边，这样这些点就一定能从源点走到，这些点就必然不会和汇点在同一个集合，否则源点和汇点就在同一个集合，就矛盾了。如果有些点的标号是 \(1\)，说明这些点就必须和汇点在一个集合，同理从这些点向汇点连一条容量是 \(+\infty\) 的边。

    至于剩下的没有标号的点，有可能和源点一个集合也有可能和汇点一个集合，我们就不做多余的操作了，求最小割的时候按照最优情况分配即可。

    综上所述，我们只需要对于每一位分别去求一下最小割，那么每一位的费用就一定是最小的，把每一位的费用加到一块就是总费用的最小值。

    方案：每次遍历一下 \(n\) 个点属于哪个集合，属于 \(1\) 的加上 \(2^k\) 即可。

    注意，本题是无向图，无向边我们就建两条有向边即可，但是在残量网络中每条边有一个反向边，一条无向边会变成四条边，这里和前面一样采用合并的方式合成两条边。

    here 

    #include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 510, M = (3000 + N * 2) * 2, INF = 1e8;

int n, m, k, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
int p[N];
PII edges[3010];
int anss[N];
void add(int a, int b, int c1, int c2)
{
	e[idx] = b, f[idx] = c1, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, f[idx] = c2, ne[idx] = h[b], h[b] = idx ++ ;
}

void build(int k)
{
	memset(h, -1, sizeof h);
	idx = 0;
	for (int i = 0; i < m; i ++ )
	{
		int a = edges[i].x, b = edges[i].y;
		add(a, b, 1, 1);
	}
	for (int i = 1; i <= n; i ++ )
		if (p[i] >= 0)
		{
			if (p[i] >> k & 1) add(S, i, INF, 0);
			else add(i, T, INF, 0);
		}
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i])
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

int find(int u, int limit)
{
	if (u == T) return limit;
	int flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i])
		{
			int t = find(ver, min(f[i], limit - flow));
			if (!t) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

void dinic(int k)
{
	build(k);
	while (bfs())
		find(S, INF);
	for(int i=1;i<=n;i++) if(d[i]!=-1) anss[i] += 1 << k;
}

int main()
{
	int Q;
	scanf("%d", &Q);
	while(Q--){
		scanf("%d%d", &n, &m);
		S = 0, T = n + 1;
		for (int i = 0; i < m; i ++ ) scanf("%d%d", &edges[i].x, &edges[i].y);
		scanf("%d", &k);
		memset(p, -1, sizeof p);
		memset(anss, 0, sizeof(anss));
		while (k -- )
		{
			int a, b;
			scanf("%d%d", &a, &b);
			p[a] = b;
		}

		for (int i = 0; i <= 30; i ++ )
			dinic(i);
		for (int i = 1; i <= n;i++)
			cout << anss[i] << endl;
	}
	return 0;
}

  • 最小割之最大权闭合图

  • P4174 [NOI2006] 最大获利

    先来解释一下什么是最大权闭合子图：

    对于一个有向图的子图，若从其中的任意一个点出发都无法到达子图外的点，则称这个子图为闭合子图。最大权闭合子图则为所有闭合子图中点权和最大的一个。其实际意义为事件间的依赖关系，一个事件要发生，它需要的所有前提也都一定要发生。

    考虑如何求出最大权闭合子图的点权和：建立新的源点 \(s\) 和汇点 \(t\)，对于原图中的每个点，若其点权为正，将其与源点 \(s\) 连接，否则将其与汇点 \(t\) 连接，容量为其点权的绝对值；对于原图中的边，仍然按照原样连接，容量为 \(+\infty\)。正点权之和减去最小割（即最大流）即为最大权闭合子图的点权和。

    本题就是最大权闭合子图的模板题，我们可以这样建图：

    • 将每个通讯中转站与汇点 \(t\) 相连，边权为成本；
    • 将每个客户与源点 \(s\) 相连，边权为收益；
    • 将每个客户与其对应的两个通讯中转站相连，边权为 \(\infty\)。
    • 答案即为收益和减最小割（即最大流）。

    考虑这样做的实际意义：对于图 \(s\rightarrow a\rightarrow x,y\rightarrow t\)，有两个选择：

    割去边 \(s\rightarrow a\)，代表不满足客户 \(a\) 的要求，减去了满足 \(a\) 所能得到的收益；
    割去边 \(x,y\rightarrow t\)，代表满足客户 \(a\) 的要求，减去了建设 \(x,y\) 的成本，得到了满足 \(a\) 的收益。

    here 

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55010, M = (50000 * 3 + 5000) * 2 + 10, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];

void add(int a, int b, int c)
{
	e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i])
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

int find(int u, int limit)
{
	if (u == T) return limit;
	int flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i])
		{
			int t = find(ver, min(f[i], limit - flow));
			if (!t) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r;
}

int main()
{
	scanf("%d%d", &n, &m);
	S = 0, T = n + m + 1;
	memset(h, -1, sizeof h);
	for (int i = 1; i <= n; i ++ )
	{
		int p;
		scanf("%d", &p);
		add(m + i, T, p);
	}

	int tot = 0;
	for (int i = 1; i <= m; i ++ )
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(S, i, c);
		add(i, m + a, INF);
		add(i, m + b, INF);
		tot += c;
	}

	printf("%d\n", tot - dinic());

	return 0;
}

  • 最小割之最大密度子图

  • Hard Life

    给定无向图 \(G=(V,E)\) ，其子图记为 \(G’=(V’,E’)\) ，在所有子图构成的集合中，密度 \(D=\frac{|E’|}{|V’|}\) 最大的元素称为最大密度子图。

    首先我们进行二分答案，二分出一个 \(g\) ，对于 \(\max(|E’|-g|V’|)\) ，如果其大于 \(0\) ，那么说明答案更大，否则说明答案更小，如此下去便可求出答案。

    故下面我们来考察 \(\max(|E’|-g|V’|)\) ，方便起见，将它写成一个以 \(g\) 为自变量的函数： \(h(g) = |E’|-g|V’|\) ，最大化 \(h(g)\) 即可。

    注意到目前的式子没有太好的性质（可以和网络流中的最小割建立联系），考虑进一步变换。

    对于 \(|E’|\) ，我们有：

    \[|E’| = \frac{\sum_{u\in V’}d_u – cnt[V’,\overline{V’}]}{2} \]

    其中 \(d_u\) 表示 \(u\) 的度数，\(cnt[V’,\overline{V’}]\) 表示非子图 \(G’\) 内部边的个数，也就是 \(cnt[V’,\overline{V’}]\) 之间相连的边数。

    我们有 \(h(g) = \frac{\sum_{u\in V’}d_u – cnt[V’,\overline{V’}]}{2}-g|V’|\) ，整理一下

    \[h(g) = \frac{1}{2}(\sum_{u\in V’}d_u – cnt[V’,\overline{V’}]-2g|V’|) \]

    而 \(2g|V’| = \sum_{u\in V’}2g\) ，进一步有：

    \[h(g) = \frac{1}{2}(\sum_{u\in V’}{(d_u-2g)} – cnt[V’,\overline{V’}]) \]

    因为需要和最小割建立联系，所以问题变成最小化 \(-h(g)\) ：

    \[-h(g) = \frac{1}{2}(\sum_{u\in V’}{(2g-d_u)} + cnt[V’,\overline{V’}]) \]

    根据式子的特征，我们这样建图：\(V\) 中的点之间连接容量为 \(1\) 的边，\(V\) 中的点 \(u\) 向汇点 \(t\) 连接容量为 \(2g-d_u+U\) 的边（\(U\) 为一个足够保证容量非负的数），源点 \(s\) 向 \(V\) 中的点 \(u\) 连接容量为 \(U\) 的边。

    我们将从接下来的公式推导中看出如此建图是合理而且正确的。

    注意到割的容量由且只由 \(s \rightarrow \overline{V’}\) 、\(V’ \rightarrow t\) 以及 \(V’\rightarrow \overline{V’}\) 构成。

    因此对于一个割，其容量满足：

    \[c[s,t]=\sum_{u\in \overline{V’}}U + \sum_{u\in V’}(2g-d_u+U) + \sum_{u\in V’}\sum_{v\in \overline{V’}}c(u,v) \]

    进一步化为：

    \[c[s,t]=|V|U + \sum_{u\in V’}(2g-d_u) + \sum_{u\in V’}\sum_{v\in \overline{V’}}c(u,v) \]

    而 \(\sum_{u\in V’}(-d_u) + \sum_{u\in V’}\sum_{v\in \overline{V’}}c(u,v)\) 恰好为 \(-2|E’|\) ，故上式可进而得到：

    \[c[s,t]=|V|U + \sum_{u\in V’}(2g) – 2|E’| \]

    整理一下，有：

    \[c[s,t]=|V|U + 2(g|V’| – |E’|) \]

    这意味着最小割对应着最小的 \(-h(g) = g|V’|-|E’|\) ，也就是最大的 \(h(g) = |E’|-g|V’|\) 。

    答案：\(g|V^{\prime}|-|E^{\prime}|=\frac{U\cdot n-C(S,T)}{2}\)。

    那么在具体实现的时候， \(U\) 应该如何选取呢？

    注意到 \(U\) 是为了保证 \(2g-d_u\) 非负，所以取 \(U = |E’|\) 即可。

    点击查看代码 

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = (1000 + N * 2) * 2, INF = 1e8;

int n, m, S, T;
int h[N], e[M], ne[M], idx;
double f[M];
int q[N], d[N], cur[N];
int dg[N];

struct Edge
{
	int a, b;
}edges[M];

int ans;
bool st[N];

void add(int a, int b, double c1, double c2)
{
	e[idx] = b, f[idx] = c1, ne[idx] = h[a], h[a] = idx ++ ;
	e[idx] = a, f[idx] = c2, ne[idx] = h[b], h[b] = idx ++ ;
}

void build(double g)
{
	memset(h, -1, sizeof h);
	idx = 0;
	for (int i = 0; i < m; i ++ ) add(edges[i].a, edges[i].b, 1, 1);
	for (int i = 1; i <= n; i ++ )
	{
		add(S, i, m, 0);
		add(i, T, m + g * 2 - dg[i], 0);
	}
}

bool bfs()
{
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = h[S];
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if (d[ver] == -1 && f[i] > 0)
			{
				d[ver] = d[t] + 1;
				cur[ver] = h[ver];
				if (ver == T) return true;
				q[ ++ tt] = ver;
			}
		}
	}
	return false;
}

double find(int u, double limit)
{
	if (u == T) return limit;
	double flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		cur[u] = i;
		int ver = e[i];
		if (d[ver] == d[u] + 1 && f[i] > 0)
		{
			double t = find(ver, min(f[i], limit - flow));
			if (t <= 0) d[ver] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

double dinic(double g)
{
	build(g);
	double r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r;
}

void dfs(int u)
{
	st[u] = true;
	if (u != S) ans ++ ;
	for (int i = h[u]; ~i; i = ne[i])
	{
		int ver = e[i];
		if (!st[ver] && f[i] > 0)
			dfs(ver);
	}
}

int main()
{

	while((scanf("%d%d",&n,&m)!=EOF)){
		S = 0, T = n + 1;
		memset(h, -1, sizeof(h));
		memset(dg, 0, sizeof(dg));
		memset(st, 0, sizeof(st));
		idx = 0, ans = 0;
		for (int i = 0; i < m; i ++ )
		{
			int a, b;
			scanf("%d%d", &a, &b);
			dg[a] ++, dg[b] ++ ;
			edges[i] = {a, b};
		}

		double l = 0, r = m;
		while (r - l > 1e-8)
		{
			double mid = (l + r) / 2;
			double t = dinic(mid);
			if (m * n - t > 0) l = mid;
			else r = mid;
		}

		dinic(l);
		dfs(S);

		if (!ans) puts("1\n1\n");
		else
		{
			printf("%d\n", ans);
			for (int i = 1; i <= n; i ++ )
				if (st[i])
					printf("%d\n", i);
		}

	}

	return 0;
}
评分
欢迎为Ta评分
分享
请登录后发表评论

    没有回复内容

最新发布
剑指offer-26、二叉搜索树与双向链表-牛翰网

剑指offer-26、二叉搜索树与双向链表

从“匿名函数”到“代码简化神技”：彻底吃透 Lambda、函数式接口与方法引用的三角关系-牛翰网

从“匿名函数”到“代码简化神技”：彻底吃透 Lambda、函数式接口与方法引用的三角关系

12K+ Star！新一代的开源持续测试工具！-牛翰网

12K+ Star！新一代的开源持续测试工具！

PriorityQueue 数据结构底层原理、源码实现可视化分析及应用实战-牛翰网

PriorityQueue 数据结构底层原理、源码实现可视化分析及应用实战

Java深拷贝与浅拷贝核心解析-牛翰网

Java深拷贝与浅拷贝核心解析

Java项目打包成EXE全攻略-牛翰网

Java项目打包成EXE全攻略

protobuf

go数据类型-sync.map

Python中的函数未定义的错误

【matplotlib基础】–刻度

用go封装和实现扫码登录

掌握Go类型内嵌：设计模式与架构的新视角

标签云
C++ReactVueOracleJS鸿蒙开发sqlNETnode.js人工智能JavaScriptphpASP.NET计算机视觉正则表达式json前端AngularVue3C语言QtCoreServertypescript数据nodenodejs安装文件字符串图片npm数据库SQLServer函数报错uniapp人脸识别MariaDBmysql配置Excel组件上传API微信小程序数组java下载查询小程序对象路由验证使用pdfechartsHTTP请求NVM
发布文章发布帖子
扫码添加微信-牛翰网
在手机上浏览此页面