「网络流 24 题」星际转移题解：本题的难点在于问题中涉及到很多天，而对于这种涉及到很多天的问题我们一般用分层图的实现来解决。对于每一天建一层图，然后对于每个飞行器就从前一天向后一天的位置连边容量为飞船容量的边，然后对于每个点从前一天向后一天连边。枚举天数，当最大流大于总人数的时候输出天数#include <bits/stdc++.h> #define pb push_back ...
「网络流 24 题」方格取数题解：对每个点进行染色，将第一个染为黑色，然后相邻的为白色，这样交替染色然后将整个方格分成黑白两种不同的颜色，从源点向每个白色的方块连容量为权值的边，从黑色向汇点连接容量为权值的边，从白色的向相邻的黑色的点连容量为无穷大的边，跑最大点权独立集#include <bits/stdc++.h> const int MAXN = 1000000,INF ...
「网络流 24 题」试题库题解：从源点向每个题目连接一条容量为1的边，从每个题型向汇点连接容量为需要题量的边，从每个题目向题型连接容量为1的边，跑一遍最大流。然后如果最大流等于每个题型需要的题数总和就有解，否则无解。方案输出：每个题目属于自己满流对应的题型。直接加进去然后输出就好了#include <bits/stdc++.h> const int MAXN = 100000,...
「网络流 24 题」最长递增子序列题解：留坑#include <bits/stdc++.h> const int MAXN = 1000000,INF = 10000000; using namespace std; int n,t,s,Max = 1,e = 2,ans,tmp; int d[MAXN],cur[MAXN],head[MAXN],dp[MAXN],a[MA...
「网络流 24 题」圆桌聚餐题解：从源点向每个单位连接容量为单位人数的边，从每个饭桌向汇点连接容量为饭桌大小的边，从每个单位向每个饭桌连接容量为1的边。在这个二分图上跑出来的最大流等于单位人数的总和，那么存在可行解方案输出：从看每个单位的满流边连向的饭桌就坐着自己公司的员工#include <bits/stdc++.h> const int MAXN = 100000,INF ...