题目链接：https://www.luogu.com.cn/problem/P1251

技巧：本题将每个天拆分为两个阶段 （白天，晚上）每天晚上会收到脏餐巾（来源：当天早上用完的餐巾，在这道题中可理解为从原点获得），每天早上又有干净的餐巾（来源：购买、快洗店、慢洗店）。

细节：这里在实现的时候，不需要在意买了新的之后才能去洗然后再用于之后，因为即使是先用了洗过之后的也没有关系，流量已经减少了，并且，能用洗过的一定是合法的，三个if已经判断过了。因为要保证最大流，所以一定会去买新的弥补之前不够的

//#define LOCAL #include <bits/stdc++.h> using namespace std; #define ll long long #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0) template<typename T> void read(T &x) { 
   x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){ 
   if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){ 
   x = x * 10 + ch - 48; ch = getchar();}x *= f;} template<typename T, typename... Args> void read(T &first, Args& ... args) { 
   read(first);read(args...);} template<typename T> void write(T arg) { 
   T x = arg;if(x < 0) { 
   putchar('-'); x =- x;}if(x > 9) { 
   write(x / 10);}putchar(x % 10 + '0');} template<typename T, typename ... Ts> void write(T arg, Ts ... args) { 
   write(arg);if(sizeof...(args) != 0) { 
   putchar(' ');write(args ...);}} using namespace std; ll gcd(ll a, ll b) { 
    return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { 
    return a / gcd(a, b) * b; } const int N = 2e5 + 5; int n , st , ed; int pp , mm , ff , nn , ss; int head[N], cnt, r[N]; struct node { 
    int f, t, next, w, c; }edge[N << 1]; void add (int f, int t, int w , int c) { 
    edge[cnt].f = f; edge[cnt].w = w; edge[cnt].c = c; edge[cnt].t = t; edge[cnt].next = head[f]; head[f] = cnt ++; } void addedge (int f, int t, int w, int c) { 
    add (f, t, w, c); add (t, f, 0, -c); } int fw[N], vis[N], pre[N]; ll dis[N]; queue <int> q; bool spfa() { 
    mem(dis,INF); mem(fw,INF); mem(vis,0); pre[st] = pre[ed] = -1; q.push(st); vis[st] = 1; dis[st] = 0; while(!q.empty()) { 
    int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u] ; i != -1 ; i = edge[i].next) { 
    int v = edge[i].t; int w = edge[i].w, c = edge[i].c; if(edge[i].w > 0 && dis[u] + c < dis[v]) { 
    dis[v] = dis[u] + c; fw[v] = min(fw[u], w); pre[v] = i; if(!vis[v]) { 
    q.push(v); vis[v] = 1; } } } } return pre[ed] != -1; } ll FYL() { 
    ll sum = 0 ; while(spfa()) { 
    cout << dis[ed] << ' ' << fw[ed] << endl; sum += 1ll * dis[ed] * fw[ed]; for (int i = pre[ed] ; i != -1 ; i = pre[edge[i].f]) { 
    edge[i].w -= fw[ed]; edge[i^1].w += fw[ed]; } } return sum; } int main () { 
    // read (n); mem(head,-1); st = 0, ed = 2 * n + 1; for (int i = 1 ; i <= n ; i ++) { 
    read (r[i]); // i 代表早上， i + n 代表晚上 addedge (st, i, r[i], 0); //每一天需要的干净餐巾 addedge (i + n , ed, r[i], 0); //使用干净的餐巾 } read (pp , mm , ff , nn , ss); for (int i = 1 ; i <= n ; i ++) { 
    addedge (st, i + n , INF, pp); //直接买干净的餐巾 if (i + 1 <= n) addedge (i , i + 1, INF, 0); //不送去洗 if (i + mm <= n) addedge (i , i + mm + n , INF , ff); //把早上用的餐巾送到晚上去洗，mm天后可以使用 if (i + nn <= n) addedge (i , i + nn + n , INF , ss); //把早上用的餐巾送到晚上去洗，nn天后可以使用 } write (FYL()), LF; } 

题目链接：https://www.luogu.com.cn/problem/P2754

技巧：对于一些看起来只有一个点，但是这个点对应着很多状态的时候，一般可以考虑拆点分层图，一般以时间（具体情况具体分析）为轴拆点，分层。这个技巧在建图过程中很常用
实现 ：枚举时间，对于每一个时间加边建立出符合当前时间的图

图的样子(引用luogu的)：

讯享网

讯享网//#define LOCAL #include <bits/stdc++.h> using namespace std; #define ll long long #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0) template<typename T> void read(T &x) { 
   x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){ 
   if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){ 
   x = x * 10 + ch - 48; ch = getchar();}x *= f;} template<typename T, typename... Args> void read(T &first, Args& ... args) { 
   read(first);read(args...);} template<typename T> void write(T arg) { 
   T x = arg;if(x < 0) { 
   putchar('-'); x =- x;}if(x > 9) { 
   write(x / 10);}putchar(x % 10 + '0');} template<typename T, typename ... Ts> void write(T arg, Ts ... args) { 
   write(arg);if(sizeof...(args) != 0) { 
   putchar(' ');write(args ...);}} using namespace std; ll gcd(ll a, ll b) { 
    return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { 
    return a / gcd(a, b) * b; } const int M = 1e6 + 5, N = 105; int st , ed; int n , m, k; int head[M], cnt; struct node { 
    int t, next, c; }edge[M << 1]; void add (int f, int t, int c) { 
    edge[cnt].c = c; edge[cnt].t = t; edge[cnt].next = head[f]; head[f] = cnt ++; } void addedge (int f, int t, int c) { 
    add (f, t, c); add (t, f, 0); } int cur[M], level[M]; bool DinicBfs(int s, int e) //利用广搜给网络图分层 { 
    mem(level,0); queue<int>q; q.push(s); level[s] = 1; while(!q.empty()) { 
    int root = q.front(); q.pop(); for(int i = head[root] ; i != -1 ; i = edge[i].next) { 
    int v = edge[i].t, c = edge[i].c; if(!level[v] && c > 0) { 
    level[v] = level[root] + 1; q.push(v); } } } return level[e] != 0; //如果当前网络能到达汇点说明存在增广路 } int DinicDfs(int root , int flow) //利用DFS在已经分好层的网络中寻找增广路 { 
    if(root == ed) return flow; int newflow , cost = 0; for(int& i = cur[root] ; i != -1 ; i = edge[i].next) //当前弧优化，&i代表i改动cur也会改动 { 
    int v = edge[i].t, c = edge[i].c; if(level[v] == level[root] + 1 && c > 0 && (newflow = DinicDfs(v,min(c,flow-cost))))//多路增广flow-cost { 
    cost += newflow; edge[i].c -= newflow; edge[i^1].c += newflow; if(cost == flow) break; } } return cost; //返回当前分层网络中能够寻找到的最大流 } int Dinic() { 
    int ans = 0; while (DinicBfs(st, ed)) { 
    for (int i = st ; i <= ed + 5 ; i ++) //如果顶点标号为0，则从0开始 cur[i] = head[i]; while (int add = DinicDfs(st, INF)) ans += add; } return ans; } int a[N][N]; int h[N], r[N]; int main () { 
    mem (head,-1); read (n, m, k); n += 2; // 地球为2 月亮为 1 其他星球编号集体加2 for (int i = 1 ; i <= m ; i ++) { 
    read (h[i], r[i]); for (int j = 1 ; j <= r[i] ; j ++) { 
    read (a[i][j]); a[i][j] += 2; } } int day = 0, sum = 0; st = 0 , ed = 10005; addedge (st, day * n + 2, INF); // 按时间轴分层，对每一层执行网络流 while (day < 500) { 
    //对于每个时间的月球都要连接上汇点，源点不用 addedge(day * n + 1, ed, INF); if (day) { 
    //当day不为0时，每个当前day点往day-1建边，表示停留在该星球 for (int i = 1 ; i <= n ; i ++) addedge ((day-1)*n+i, day*n+i, INF); } for (int i = 1; i <= m; i++) { 
    //往下一个day状态建边，可以往下继续走，容量为飞船容量 int x = a[i][(day + 1) % r[i] + 1]; int y = a[i][day % r[i] + 1]; addedge((day) * n + y, (day+1) * n + x, h[i]); } //对于每一个时间，跑一次最大流 sum += Dinic(); if (sum >= k) break; day ++; } if (day == 500) write (0), LF; else write (day) , LF; } 

题目链接：https://www.luogu.com.cn/problem/P2756

技巧：比较经典的一对多单向二分图模型，主要是代码理解，fa数组就是对应的链接点

//#define LOCAL #include <bits/stdc++.h> using namespace std; #define ll long long #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0) template<typename T> void read(T &x) { 
   x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){ 
   if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){ 
   x = x * 10 + ch - 48; ch = getchar();}x *= f;} template<typename T, typename... Args> void read(T &first, Args& ... args) { 
   read(first);read(args...);} template<typename T> void write(T arg) { 
   T x = arg;if(x < 0) { 
   putchar('-'); x =- x;}if(x > 9) { 
   write(x / 10);}putchar(x % 10 + '0');} template<typename T, typename ... Ts> void write(T arg, Ts ... args) { 
   write(arg);if(sizeof...(args) != 0) { 
   putchar(' ');write(args ...);}} using namespace std; ll gcd(ll a, ll b) { 
    return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { 
    return a / gcd(a, b) * b; } const int N = 2e5 + 5; int n, m; int head[N] , cnt; struct node { 
    int t, next; }edge[N]; void add (int f, int t) { 
    edge[cnt].t = t; edge[cnt].next = head[f]; head[f] = cnt ++; } int vis[N] , fa[N]; bool solve (int u) { 
    for (int i = head[u] ; i != -1 ; i = edge[i].next) { 
    int t = edge[i].t; if (!vis[t]) { 
    vis[t] = 1; if (!fa[t] || solve (fa[t])) { 
    fa[t] = u; return true; } } } return false; } int main () { 
    mem (head,-1); read (m, n); while (1) { 
    int u , v; read (u, v); if (u == -1 && v == -1) break; add (u, v); } int ans = 0; for (int i = 1 ; i <= m ; i ++) { 
    mem(vis, 0); if (solve (i)) ans ++; } cout << ans << endl; for (int i = 1 ; i <= n ; i ++) if (fa[i]) cout << fa[i] << ' ' << i << endl; } 

题目链接：https://www.luogu.com.cn/problem/P2761

技巧：比较典型的状态压缩+最短路，读懂题目之后直接模拟即可

讯享网//#define LOCAL #include <bits/stdc++.h> using namespace std; #define ll long long #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0) template<typename T> void read(T &x) { 
   x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){ 
   if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){ 
   x = x * 10 + ch - 48; ch = getchar();}x *= f;} template<typename T, typename... Args> void read(T &first, Args& ... args) { 
   read(first);read(args...);} template<typename T> void write(T arg) { 
   T x = arg;if(x < 0) { 
   putchar('-'); x =- x;}if(x > 9) { 
   write(x / 10);}putchar(x % 10 + '0');} template<typename T, typename ... Ts> void write(T arg, Ts ... args) { 
   write(arg);if(sizeof...(args) != 0) { 
   putchar(' ');write(args ...);}} using namespace std; ll gcd(ll a, ll b) { 
    return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { 
    return a / gcd(a, b) * b; } const int M = (1 << 21) - 1, N = 205; int n , m; struct node { 
    int b1 = 0, b2 = 0; int f1 = 0, f2 = 0; int w; }p[N]; int vis[M] , dis[M]; void spfa () { 
    queue <int> q; int s = (1 << n) - 1; mem(dis, INF); dis[s] = 0; vis[s] = 1; q.push(s); while (!q.empty()) { 
    int u = q.front(); q.pop (); vis[u] = 0; for (int i = 1 ; i <= m ; i ++) { 
    if (((u&p[i].b1)==p[i].b1)&&((u&p[i].b2)==0)) { 
    int v = (((u | p[i].f1) | p[i].f2) ^ p[i].f1); if (p[i].w + dis[u] < dis[v]) { 
    dis[v] = p[i].w + dis[u]; if (!vis[v]) { 
    q.push(v); vis[v] = 1; } } } } } } int main () { 
    read (n, m); for (int i = 1 ; i <= m ; i ++) { 
    read (p[i].w); string s1 , s2; cin >> s1 >> s2; for (int j = 0 ; j < s1.length() ; j ++) { 
    if (s1[j] == '+') p[i].b1 += 1 << j; else if (s1[j] == '-') p[i].b2 += 1 << j; } for (int j = 0 ; j < s2.length() ; j ++) { 
    if (s2[j] == '-') p[i].f1 += 1 << j; else if (s2[j] == '+') p[i].f2 += 1 << j; } } spfa (); if (dis[0] == INF) cout << "0" << endl; else cout << dis[0] << endl; } 

题目链接：https://www.luogu.com.cn/problem/P2762

技巧：最大权闭合子图经典题目，由于题目描述：如果选择了某个实验项目，那么实验器材也必须选，很明显的闭合子图性质。
细节：这里一定要注意，在构造闭合子图的时候，不可以只通过判断与源点相链的边得容量。需要从源点出发搜索，可达点均为闭合子图中的点

//#define LOCAL #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0) template<typename T> void read(T &x) { 
   x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){ 
   if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){ 
   x = x * 10 + ch - 48; ch = getchar();}x *= f;} template<typename T, typename... Args> void read(T &first, Args& ... args) { 
   read(first);read(args...);} template<typename T> void write(T arg) { 
   T x = arg;if(x < 0) { 
   putchar('-'); x =- x;}if(x > 9) { 
   write(x / 10);}putchar(x % 10 + '0');} template<typename T, typename ... Ts> void write(T arg, Ts ... args) { 
   write(arg);if(sizeof...(args) != 0) { 
   putchar(' ');write(args ...);}} using namespace std; ll gcd(ll a, ll b) { 
    return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { 
    return a / gcd(a, b) * b; } const int N = 1e6 + 5; int n , m , head[N] , cnt; struct node { 
    int t, next, c; }edge[N << 1]; void add (int f, int t, int c) { 
    edge[cnt].t = t; edge[cnt].c = c; edge[cnt].next = head[f]; head[f] = cnt ++; } void addedge (int f, int t, int c) { 
    add (f, t, c); add (t, f, 0); } int st , ed; int cur[N], level[N], vis[N]; vector <int> a[N]; bool DinicBfs(int s, int e) //利用广搜给网络图分层 { 
    mem(level,0); queue<int>q; q.push(s); level[s] = 1; while(!q.empty()) { 
    int root = q.front(); q.pop(); for(int i = head[root] ; i != -1 ; i = edge[i].next) { 
    int v = edge[i].t, c = edge[i].c; if(!level[v] && c > 0) { 
    level[v] = level[root] + 1; q.push(v); } } } return level[e] != 0; //如果当前网络能到达汇点说明存在增广路 } int DinicDfs(int root , int flow) //利用DFS在已经分好层的网络中寻找增广路 { 
    if(root == ed) return flow; int newflow , cost = 0; for(int& i = cur[root] ; i != -1 ; i = edge[i].next) //当前弧优化，&i代表i改动cur也会改动 { 
    int v = edge[i].t, c = edge[i].c; if(level[v] == level[root] + 1 && c > 0 && (newflow = DinicDfs(v,min(c,flow-cost))))//多路增广flow-cost { 
    cost += newflow; edge[i].c -= newflow; edge[i^1].c += newflow; if(cost == flow) break; } } return cost; //返回当前分层网络中能够寻找到的最大流 } int Dinic() { 
    int ans = 0; while (DinicBfs(st, ed)) { 
    for (int i = st ; i <= ed + 5 ; i ++) //如果顶点标号为0，则从0开始 cur[i] = head[i]; while (int add = DinicDfs(st, INF)) ans += add; } return ans; } char ch[N]; int ulen, num; int main () { 
    mem (head, -1); int sum = 0; read (m, n); st = 0 , ed = n + m + 1; for (int i = 1 ; i <= m ; i ++) { 
    int p; read (p); sum += p; addedge (st, i , p); memset(ch,0,sizeof(ch)); cin.getline(ch,10000); ulen=0; while (sscanf(ch+ulen,"%d",&num)==1) { 
    a[i].pb(num); addedge (i , m + num , INF); if (num==0) ulen++; else while (num) { 
    num/=10; ulen++; } ulen++; } } for (int i = 1 ; i <= n ; i ++) { 
    int p; read (p); addedge (m + i , ed , p); } int ans = Dinic(); //这里找出残余网络中S可到的点 //这里不能直接检查与S相连的边的容量，因为可能经过实验器材之后再走到实验 for (int i = 1 ; i <= m ; i ++) { 
    if (level[i] != 0) { 
    cout << i << ' '; vis[i] = 1; } } cout << endl; set <int> s; for (int i = 1 ; i <= m ; i ++) { 
    if (vis[i]) { 
    for (auto v : a[i]) s.insert (v); } } for (auto v : s) cout << v << ' '; cout << endl; cout << sum - ans << endl; } 

题目链接：https://www.luogu.com.cn/problem/P2763

技巧：无
细节：无

讯享网//#define LOCAL #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0) template<typename T> void read(T &x) { 
   x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){ 
   if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){ 
   x = x * 10 + ch - 48; ch = getchar();}x *= f;} template<typename T, typename... Args> void read(T &first, Args& ... args) { 
   read(first);read(args...);} template<typename T> void write(T arg) { 
   T x = arg;if(x < 0) { 
   putchar('-'); x =- x;}if(x > 9) { 
   write(x / 10);}putchar(x % 10 + '0');} template<typename T, typename ... Ts> void write(T arg, Ts ... args) { 
   write(arg);if(sizeof...(args) != 0) { 
   putchar(' ');write(args ...);}} using namespace std; ll gcd(ll a, ll b) { 
    return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { 
    return a / gcd(a, b) * b; } const int N = 1e6 + 5; int k , n , st , ed , m; int a[N]; int head[N], cnt; struct node { 
    int t, next, c; }edge[N << 1]; void add (int f, int t, int c) { 
    edge[cnt].c = c; edge[cnt].t = t; edge[cnt].next = head[f]; head[f] = cnt ++; } void addedge (int f, int t, int c) { 
    add (f, t, c); add (t, f, 0); } int cur[N], level[N]; bool DinicBfs(int s, int e) //利用广搜给网络图分层 { 
    mem(level,0); queue<int>q; q.push(s); level[s] = 1; while(!q.empty()) { 
    int root = q.front(); q.pop(); for(int i = head[root] ; i != -1 ; i = edge[i].next) { 
    int v = edge[i].t, c = edge[i].c; if(!level[v] && c > 0) { 
    level[v] = level[root] + 1; q.push(v); } } } return level[e] != 0; //如果当前网络能到达汇点说明存在增广路 } int DinicDfs(int root , int flow) //利用DFS在已经分好层的网络中寻找增广路 { 
    if(root == ed) return flow; int newflow , cost = 0; for(int& i = cur[root] ; i != -1 ; i = edge[i].next) //当前弧优化，&i代表i改动cur也会改动 { 
    int v = edge[i].t, c = edge[i].c; if(level[v] == level[root] + 1 && c > 0 && (newflow = DinicDfs(v,min(c,flow-cost))))//多路增广flow-cost { 
    cost += newflow; edge[i].c -= newflow; edge[i^1].c += newflow; if(cost == flow) break; } } return cost; //返回当前分层网络中能够寻找到的最大流 } int Dinic() { 
    int ans = 0; while (DinicBfs(st, ed)) { 
    for (int i = st ; i <= ed + 5 ; i ++) //如果顶点标号为0，则从0开始 cur[i] = head[i]; while (int add = DinicDfs(st, INF)) ans += add; } return ans; } int main () { 
    mem (head, -1); read (k , n); st = 0 , ed = k * n + k + 1; for (int i = 1 ; i <= k ; i ++) { 
    read(a[i]); m += a[i]; addedge (k * n + i , ed, a[i]); } for (int i = 1 ; i <= n ; i ++) { 
    cout << i << ":" << endl; int p; read (p); for (int j = 0 ; j < p ; j ++) { 
    int x; read (x); cout << i + (x-1) * n << ' ' << k * n + x << endl; addedge (st , i + (x-1) * n , 1); addedge (i + (x-1) * n, k * n + x , 1); } cout << endl; } int ans = Dinic (); if (ans != m) puts ("No Solution!"); else { 
    for (int u = k * n + 1 ; u <= k * n + k ; u ++) { 
    printf ("%d:", u % n); for (int i = head[u] ; i != -1 ; i = edge[i].next) { 
    int v = edge[i].t , c = edge[i].c; if (v != ed && c == 1) { 
    if (v % n == 0) printf (" %d",n); else printf(" %d",v%n); } } printf ("\n"); } } } 

题目链接：https://www.luogu.com.cn/problem/P2764
技巧：对原图中的每一个点拆点为(x , x + n)，如果存在一条边(x, y)则，新图中存在 (x , y + n)，那么 最少路径数 = 原图点数 - 新图最大匹配数， 同时，每一条路径的终点等于新图中未匹配到的点.,该类问题属于 最少不相交路径覆盖问题

//#define LOCAL #include <bits/stdc++.h> using namespace std; #define ll long long #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0) template<typename T> void read(T &x) { 
   x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){ 
   if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){ 
   x = x * 10 + ch - 48; ch = getchar();}x *= f;} template<typename T, typename... Args> void read(T &first, Args& ... args) { 
   read(first);read(args...);} template<typename T> void write(T arg) { 
   T x = arg;if(x < 0) { 
   putchar('-'); x =- x;}if(x > 9) { 
   write(x / 10);}putchar(x % 10 + '0');} template<typename T, typename ... Ts> void write(T arg, Ts ... args) { 
   write(arg);if(sizeof...(args) != 0) { 
   putchar(' ');write(args ...);}} using namespace std; ll gcd(ll a, ll b) { 
    return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { 
    return a / gcd(a, b) * b; } const int N = 20005; int head[N], cnt; int n , m; struct node { 
    int t, next; }edge[N]; void add (int f, int t) { 
    edge[cnt].t = t; edge[cnt].next = head[f]; head[f] = cnt ++; } int vis[N] , fa[N], t[N]; bool solve (int u) { 
    for (int i = head[u] ; i != -1 ; i = edge[i].next) { 
    int t = edge[i].t; if (!vis[t]) { 
    vis[t] = 1; if (!fa[t] || solve (fa[t])) { 
    fa[t] = u; return true; } } } return false; } vector <int> Edge[N]; vector <int> path; void dfs (int u) { 
    path.pb(u); for (auto v : Edge[u]) { 
    if (!vis[v]) { 
    vis[v] = 1; dfs (v); } } } int main () { 
    read (n , m); mem (head, -1); for (int i = 1 ; i <= m ; i++) { 
    int u , v; read (u, v); Edge[v].pb(u); add (u , v + n + 1); } int ans = 0; for (int i = 1 ; i <= n ; i ++) { 
    mem(vis, 0); if (solve (i)) { 
    t[i] = 1; ans++; } } for (int i = 1 ; i <= n ; i ++) { 
    if (!t[i]) { 
    vis[i] = 1; //cout << i << endl; path.clear(); dfs(i); reverse (path.begin(), path.end()); for (auto v : path) cout << v << ' '; cout << endl; } } cout << n - ans << endl; } 

题目链接：https://www.luogu.com.cn/problem/P2765
技巧：隐式图，图的特征不是很明显，但是可以分析出来，设有x个点，俩俩能组成平方数的数字连边，从而建立出图（按照求最少路径覆盖的方式拆点建图），接下来就是最少路径覆盖了

讯享网//#define LOCAL #include <bits/stdc++.h> using namespace std; #define ll long long #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0) template<typename T> void read(T &x) { 
   x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){ 
   if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){ 
   x = x * 10 + ch - 48; ch = getchar();}x *= f;} template<typename T, typename... Args> void read(T &first, Args& ... args) { 
   read(first);read(args...);} template<typename T> void write(T arg) { 
   T x = arg;if(x < 0) { 
   putchar('-'); x =- x;}if(x > 9) { 
   write(x / 10);}putchar(x % 10 + '0');} template<typename T, typename ... Ts> void write(T arg, Ts ... args) { 
   write(arg);if(sizeof...(args) != 0) { 
   putchar(' ');write(args ...);}} using namespace std; ll gcd(ll a, ll b) { 
    return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { 
    return a / gcd(a, b) * b; } const int M = 3e6 + 5; const int Base = 1e6+5; int n, a[2005], mark[M]; int head[M] , cnt; struct node { 
    int t, next; }edge[M << 1]; void add (int f, int t) { 
    edge[cnt].t = t; edge[cnt].next = head[f]; head[f] = cnt ++; } int vis[M] , fa[M], t[M], m , ans; bool solve (int u) { 
    for (int i = head[u] ; i != -1 ; i = edge[i].next) { 
    int t = edge[i].t; if (!vis[t]) { 
    vis[t] = 1; if (!fa[t] || solve (fa[t])) { 
    fa[t] = u; return true; } } } return false; } vector <int> path, Edge[M]; void dfs (int u) { 
    path.pb(u); for (auto v : Edge[u]) { 
    if (v == m + 1) continue; if (!vis[v]) { 
    vis[v] = 1; dfs (v); break; } } } int main () { 
    mem (head, -1); int dd = 1; for (int i = 1 ; i <= 1000 ; i ++) { 
    mark[dd * dd] = 1; dd += 1; } read (n); m = 0, ans = 0; while (1) { 
    m ++; for (int i = 1 ; i < m ; i ++) if (mark[i + m]) { 
    add(m, i + Base); Edge[i].pb(m); } mem (vis, 0); int p = solve (m); ans += p; if (p) t[m] = 1; if (m - ans > n) break; } mem (vis, 0); cout << --m << endl; for (int i = 1 ; i <= m ; i ++) { 
    if (!t[i]) { 
    vis[i] = 1; path.clear(); dfs(i); for (auto v : path) cout << v << ' '; cout << endl; } } } 

题目链接：https://www.luogu.com.cn/problem/P2766
技巧：拆点和建图的思想很精妙，通过dp数组和原数组建立出关系图，然后利用拆点作为限制，流量的控制满足不同题意

//#define LOCAL #include <bits/stdc++.h> using namespace std; #define ll long long #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0) template<typename T> void read(T &x) { 
   x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){ 
   if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){ 
   x = x * 10 + ch - 48; ch = getchar();}x *= f;} template<typename T, typename... Args> void read(T &first, Args& ... args) { 
   read(first);read(args...);} template<typename T> void write(T arg) { 
   T x = arg;if(x < 0) { 
   putchar('-'); x =- x;}if(x > 9) { 
   write(x / 10);}putchar(x % 10 + '0');} template<typename T, typename ... Ts> void write(T arg, Ts ... args) { 
   write(arg);if(sizeof...(args) != 0) { 
   putchar(' ');write(args ...);}} using namespace std; ll gcd(ll a, ll b) { 
    return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { 
    return a / gcd(a, b) * b; } const int N = 10005; int n, a[N], dp[N]; int ans, head[N], cnt, st , ed; struct node { 
    int next, t, c; }edge[N << 3]; void add (int f, int t, int c) { 
    edge[cnt].t = t; edge[cnt].c = c; edge[cnt].next = head[f]; head[f] = cnt ++; } void addedge (int f, int t, int c) { 
    add (f , t, c); add (t , f, 0); } int cur[N], level[N]; bool DinicBfs(int s, int e) //利用广搜给网络图分层 { 
    mem(level,0); queue<int>q; q.push(s); level[s] = 1; while(!q.empty()) { 
    int root = q.front(); q.pop(); for(int i = head[root] ; i != -1 ; i = edge[i].next) { 
    int v = edge[i].t, c = edge[i].c; if(!level[v] && c > 0) { 
    level[v] = level[root] + 1; q.push(v); } } } return level[e] != 0; //如果当前网络能到达汇点说明存在增广路 } int DinicDfs(int root , int flow) //利用DFS在已经分好层的网络中寻找增广路 { 
    if(root == ed) return flow; int newflow , cost = 0; for(int& i = cur[root] ; i != -1 ; i = edge[i].next) //当前弧优化，&i代表i改动cur也会改动 { 
    int v = edge[i].t, c = edge[i].c; if(level[v] == level[root] + 1 && c > 0 && (newflow = DinicDfs(v,min(c,flow-cost))))//多路增广flow-cost { 
    cost += newflow; edge[i].c -= newflow; edge[i^1].c += newflow; if(cost == flow) break; } } return cost; //返回当前分层网络中能够寻找到的最大流 } int Dinic() { 
    int ans = 0; while (DinicBfs(st, ed)) { 
    for (int i = st ; i <= ed + 5 ; i ++) //如果顶点标号为0，则从0开始 cur[i] = head[i]; while (int add = DinicDfs(st, INF)) ans += add; } return ans; } int main () { 
    mem (head,-1); read (n); if (n == 1) { 
    cout << 1 << endl; cout << 1 << endl; cout << 1 << endl; return 0; } for (int i = 1 ; i <= n ; i ++) read (a[i]); for (int i = 1 ; i <= n ; i ++) { 
    for (int j = 1 ; j < i ; j ++) if (a[j] <= a[i] && dp[j] > dp[i]) dp[i] = dp[j]; dp[i] ++; ans = max (dp[i], ans); } st = 0 , ed = 2 * n + 1; for(int i = 1 ; i <= n ; i ++) { 
    addedge (i , i + n , 1); if (dp[i] == 1) addedge(st, i, 1); // 不能是 else if 因为可能 1 == ans if (dp[i] == ans) addedge(i + n, ed, 1); } for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j < i ; j ++) if(a[j] <= a[i] && dp[j] == dp[i]-1) addedge(j + n , i ,1); int tot = Dinic (); cout << ans << endl; cout << tot << endl; addedge(1,1+n,INF), addedge(st,1,INF); if(dp[n]==ans) addedge(n+n,ed,INF),addedge(n,n+n,INF); tot += Dinic (); cout << tot << endl; } 

题目链接：https://www.luogu.com.cn/problem/P2770

技巧：最大费用最大流，拆点限制行走的次数，构造答案的时候对残余网络进行搜索即可

讯享网//#define LOCAL #include <bits/stdc++.h> using namespace std; #define ll long long #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0) #define sz(a) (int)a.size() template<typename T> void read(T &x) { 
   x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){ 
   if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){ 
   x = x * 10 + ch - 48; ch = getchar();}x *= f;} template<typename T, typename... Args> void read(T &first, Args& ... args) { 
   read(first);read(args...);} template<typename T> void write(T arg) { 
   T x = arg;if(x < 0) { 
   putchar('-'); x =- x;}if(x > 9) { 
   write(x / 10);}putchar(x % 10 + '0');} template<typename T, typename ... Ts> void write(T arg, Ts ... args) { 
   write(arg);if(sizeof...(args) != 0) { 
   putchar(' ');write(args ...);}} using namespace std; ll gcd(ll a, ll b) { 
    return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { 
    return a / gcd(a, b) * b; } const int N = ; int n , m, maxflow; string str[N]; map <string, int> ma; int head[N], cnt; int st , ed; struct node { 
    int f, t, next, w, c; }edge[N * 20]; void add (int f, int t, int w , int c) { 
    edge[cnt].f = f; edge[cnt].w = w; edge[cnt].c = c; edge[cnt].t = t; edge[cnt].next = head[f]; head[f] = cnt ++; } void addedge (int f, int t, int w, int c) { 
    add (f, t, w, c); add (t, f, 0, -c); } int fw[N], vis[N], pre[N]; ll dis[N]; queue <int> q; bool spfa() { 
    for (int i = 0; i <= ed + 5 ; i ++) dis[i] = -INF; mem(fw,INF); mem(vis,0); pre[st] = pre[ed] = -1; q.push(st); vis[st] = 1; dis[st] = 0; while(!q.empty()) { 
    int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u] ; i != -1 ; i = edge[i].next) { 
    int v = edge[i].t; int w = edge[i].w, c = edge[i].c; if(edge[i].w && dis[u] + c > dis[v]) { 
    dis[v] = dis[u] + c; fw[v] = min(fw[u], w); pre[v] = i; if(!vis[v]) { 
    q.push(v); vis[v] = 1; } } } } return pre[ed] != -1; } ll FYL() { 
    ll sum = 0 ; while(spfa()) { 
    maxflow ++; sum += 1ll * dis[ed] * fw[ed]; for (int i = pre[ed] ; i != -1 ; i = pre[edge[i].f]) { 
    edge[i].w -= fw[ed]; edge[i^1].w += fw[ed]; } } return sum; } void dfs1 (int u) { 
    vis[u] = 1; cout << str[u - n] << endl; for (int i = head[u] ; i != -1 ; i = edge[i].next) { 
    int t = edge[i].t, w = edge[i].w; if (t <= n && w == 0) { 
    dfs1(t + n); break; //break位置要注意 } } } void dfs2 (int u) { 
    vis[u] = 1; for (int i = head[u] ; i != -1 ; i = edge[i].next) { 
    int t = edge[i].t, w = edge[i].w; if (t <= n && w == 0 && !vis[t + n]) dfs2 (t + n); } cout << str[u - n] << endl; } int main () { 
    int check = 0; mem (head, -1); cin >> n >> m; for (int i = 1 ; i <= n ; i ++) { 
    cin >> str[i]; ma[str[i]] = i; } for (int i = 2 ; i <= n - 1 ; i ++) addedge (i , i + n , 1, 1); addedge (1 , 1 + n , 2, 1); addedge (n , n + n , 2, 1); for (int i = 1 ; i <= m ; i ++) { 
    string u , v; cin >> u >> v; int x = ma[u] , y = ma[v]; if (x > y) swap (x, y); if (x == 1 && y == n) check = 1; addedge (x + n, y, 1, 0); } st = 1 , ed = 2 * n; ll cost = FYL(); mem (vis, 0); if (maxflow == 2) { 
    cout << cost - 2 << endl; dfs1 (st + n); dfs2 (st + n); } else if (maxflow == 1 && check) { 
    cout << 2 << endl; cout << str[1] << endl; cout << str[n] << endl; cout << str[1] << endl; } else cout << "No Solution!" << endl; } 

题目链接：https://www.luogu.com.cn/problem/P2774

技巧：二分图建图，求最大权独立集合

//#define LOCAL #include <bits/stdc++.h> using namespace std; #define ll long long #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0) #define sz(a) (int)a.size() template<typename T> void read(T &x) { 
   x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){ 
   if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){ 
   x = x * 10 + ch - 48; ch = getchar();}x *= f;} template<typename T, typename... Args> void read(T &first, Args& ... args) { 
   read(first);read(args...);} template<typename T> void write(T arg) { 
   T x = arg;if(x < 0) { 
   putchar('-'); x =- x;}if(x > 9) { 
   write(x / 10);}putchar(x % 10 + '0');} template<typename T, typename ... Ts> void write(T arg, Ts ... args) { 
   write(arg);if(sizeof...(args) != 0) { 
   putchar(' ');write(args ...);}} using namespace std; ll gcd(ll a, ll b) { 
    return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { 
    return a / gcd(a, b) * b; } const int N = 1005; int n , m, sum = 0; int num[N][N]; int head[N * N] , cnt; struct node { 
    int c, t, next; }edge[N * N * 10]; void add (int f, int t, int c) { 
    edge[cnt].t = t; edge[cnt].c = c; edge[cnt].next = head[f]; head[f] = cnt ++; } void addedge (int f, int t, int c) { 
    add (f, t, c); add (t, f, 0); } int st, ed, cur[N], level[N]; bool DinicBfs(int s, int e) //利用广搜给网络图分层 { 
    mem(level,0); queue<int>q; q.push(s); level[s] = 1; while(!q.empty()) { 
    int root = q.front(); q.pop(); for(int i = head[root] ; i != -1 ; i = edge[i].next) { 
    int v = edge[i].t, c = edge[i].c; if(!level[v] && c > 0) { 
    level[v] = level[root] + 1; q.push(v); } } } return level[e] != 0; //如果当前网络能到达汇点说明存在增广路 } int DinicDfs(int root , int flow) //利用DFS在已经分好层的网络中寻找增广路 { 
    if(root == ed) return flow; int newflow , cost = 0; for(int& i = cur[root] ; i != -1 ; i = edge[i].next) //当前弧优化，&i代表i改动cur也会改动 { 
    int v = edge[i].t, c = edge[i].c; if(level[v] == level[root] + 1 && c > 0 && (newflow = DinicDfs(v,min(c,flow-cost))))//多路增广flow-cost { 
    cost += newflow; edge[i].c -= newflow; edge[i^1].c += newflow; if(cost == flow) break; } } return cost; //返回当前分层网络中能够寻找到的最大流 } int Dinic() { 
    int ans = 0; while (DinicBfs(st, ed)) { 
    for (int i = st ; i <= ed + 5 ; i ++) //如果顶点标号为0，则从0开始 cur[i] = head[i]; while (int add = DinicDfs(st, INF)) ans += add; } return ans; } int main () { 
    mem (head, -1); read (n, m); st = 0 , ed = n * m + 1; for (int i = 1 ; i <= n ; i ++) { 
    for (int j = 1 ; j <= m ; j ++) { 
    read (num[i][j]); sum += num[i][j]; int id = (i-1) * m + j; //cout << id << endl; if ((i + j) % 2) { 
    addedge(st, id, num[i][j]); //下面的建边，一定只能单向，不然的话，可能最小割直接割与ed连接的边就好了 //但是由于双向之后，可能只割与ed连的边都不够 if (i > 1) addedge (id , id - m , INF); if (i < n) addedge (id , id + m , INF); if (j > 1) addedge (id , id - 1 , INF); if (j < m) addedge (id , id + 1 , INF); } else addedge (id , ed, num[i][j]); } } cout << sum - Dinic() << endl; }