一.最小费用流
最小费用流实际上就是最短路寻找增广路
下面给出一个应用题：
思路：货物搬运，显然的是， 多的会分给少的，其中相邻的点的费用为1，所以首先连边。一个点连接相邻的点，容量为INF，费用为1；考虑多的点会将不需要的货物分出去，将源点与其连接一条边，大小为x[i]-avg；考虑小的点需要多的货物，所以这个需要连接汇点。
代码如下：
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110, M = 610, INF = 1e8;int n, S, T;
int s[N];
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];void add(int a, int b, int c, int d)
{e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++ ;
}bool spfa()
{int hh = 0, tt = 1;memset(d, 0x3f, sizeof d);memset(incf, 0, sizeof incf);q[0] = S, d[S] = 0, incf[S] = INF;while (hh != tt){int t = q[hh ++ ];if (hh == N) hh = 0;st[t] = false;for (int i = h[t]; ~i; i = ne[i]){int ver = e[i];if (f[i] && d[ver] > d[t] + w[i]){d[ver] = d[t] + w[i];pre[ver] = i;incf[ver] = min(f[i], incf[t]);if (!st[ver]){q[tt ++ ] = ver;if (tt == N) tt = 0;st[ver] = true;}}}}return incf[T] > 0;
}int EK()
{int cost = 0;while (spfa()){int t = incf[T];cost += t * d[T];for (int i = T; i != S; i = e[pre[i] ^ 1]){f[pre[i]] -= t;f[pre[i] ^ 1] += t;}}return cost;
}int main()
{scanf("%d", &n);S = 0, T = n + 1;memset(h, -1, sizeof h);int tot = 0;for (int i = 1; i <= n; i ++ ){scanf("%d", &s[i]);tot += s[i];add(i, i < n ? i + 1 : 1, INF, 1);add(i, i > 1 ? i - 1 : n, INF, 1);}tot /= n;for (int i = 1; i <= n; i ++ )if (tot < s[i])add(S, i, s[i] - tot, 0);else if (tot > s[i])add(i, T, tot - s[i], 0);printf("%d\n", EK());return 0;
}
推荐一个网络流的题单：
比较适合学习过的同学的题单（刷完大概1个月）：https://vjudge.net/article/4765
快速入门（刷完1周左右）：https://vjudge.net/article/4125
二.线性DP
题目1
题目链接：https://vjudge.net/problem/CodeForces-191A
思路：定义f[26][26]表示状态i字母开头，j字母结尾的最大长度，最后统计f[i][i],注意为0的情况，显然是不成立的
代码如下：
#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using namespace std;
const int inf=1e9;
void solve() {int n;cin>>n;vector<string>a(n+1);for(int i=1; i<=n; i++){string s;cin>>s;a[i]=s;}vector<vector<int>>f(26,vector<int>(26,0));for(int i=1; i<=n; i++){int len=a[i].size();for(int j=0; j<26; j++){if(f[j][a[i][0]-'a']!=0)f[j][a[i][len-1]-'a']=max(f[j][a[i][len-1]-'a'],f[j][a[i][0]-'a']+len);}f[a[i][0]-'a'][a[i][len-1]-'a']=max(f[a[i][0]-'a'][a[i][len-1]-'a'],len);}int res=0;for(int i=0; i<26; i++){res=max(res,f[i][i]);}cout<<res<<endl;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);solve();return 0;
}题目2
题目链接：Boredom - CodeForces 455A - Virtual Judge
思路：这个实际上就是选不选的问题，只不过是具有"时效性"
代码如下：
#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using namespace std;
const int inf=1e9;
void solve() {int n;cin>>n;vector<int>a(n+1);vector<vector<i64>>f(1e5+10,vector<i64>(2,0));vector<i64>cnt(1e5+10,0);for(int i=0; i<n; i++){i64 w;cin>>w;cnt[w]+=w;}for(int i=1; i<=1e5; i++){if(i-2>=0){f[i][1]=max(f[i-2][0],f[i-2][1]);}f[i][1]+=cnt[i];f[i][0]=max(f[i-1][0],f[i-1][1]);}n=1e5;cout<<max(f[n][0],f[n][1])<<endl;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);// int t;// std::cin >> t;// while (t--) {solve();// }return 0;
}题目3
题目链接：https://vjudge.net/problem/CodeForces-1061C
思路：将每个数的可能都尝试一下，实际上这个是具有累加性的
代码如下：
#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using namespace std;
const int inf=1e9,mod=1e9+7;
void solve() {int n;cin>>n;vector<int>a(n+1);a[0]=1;for(int i=1; i<=n; i++){int w;cin>>w;vector<int>temp;for(int j=1; j*j<=w && j<=n; j++){if(w%j==0){temp.push_back(j);if(j*j!=w && w/j<=n){temp.push_back(w/j);}}}sort(temp.rbegin(),temp.rend());for(auto v:temp){a[v]+=a[v-1];a[v]%=mod;}}i64 sum=0;for(int i=1; i<=n; i++){sum+=a[i];sum%=mod;}cout<<sum<<endl;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);// int t;// std::cin >> t;// while (t--) {solve();// }return 0;
}题目4
题目链接：https://vjudge.net/problem/CodeForces-1110D
思路：定义dp[x][y]表示三元组[i-1,i,i+1]的个数,以及三元组[i,i+1,i+2]的个数.为什么不选择i-2,i-1,i呢，实际上这个会被i-1为中心而被包围。那么为什么需要选择[i,i+1,i+2]呢，实际上我们需要考虑i包含是所有三元组，同时这个可以表示关系。
代码如下：
#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using namespace std;
const int inf=1e9,mod=1e9+7;
void solve() {int n,m;cin>>n>>m;vector<int>cnt(m+1,0);vector<vector<int>>dp(3,vector<int>(3,0));for(int i=0; i<n; i++){int x;cin>>x;cnt[x]++;}for(int i=1; i<=m; i++){vector<vector<int>>temp(3,vector<int>(3,0));for(int x=0; x<3; x++){for(int y=0; y<3; y++){for(int z=0; z<3; z++){if(cnt[i]<x+y+z)continue;temp[y][z]=max(temp[y][z],dp[x][y]+(cnt[i]-x-y-z)/3+z);}}}dp=temp;}cout<<dp[0][0]<<endl;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);// int t;// std::cin >> t;// while (t--) {solve();// }return 0;
}题目5
题目链接：https://vjudge.net/problem/CodeForces-245H
思路:哈希线性判断回文串，使用dp[j][i]+=dp[j][i-1]+当前以i结尾的贡献
代码如下：
#include <bits/stdc++.h>using i64 = long long;
using namespace std;const int mod = 1e9 + 7;
const int MAXN = 100005;
void solve() {char ss[MAXN]; cin >> ss; int len = strlen(ss) + 1;vector<i64> s(len + 2, 0);for (int i = 1; i < len; i++) { s[i] = ss[i - 1]; //cout<<s[i]<<endl;}vector<vector<i64>> dp(len + 1, vector<i64>(len + 1, 0));vector<i64> Lhasp(len + 2, 0), Rhasp(len + 2, 0);vector<i64> p(len + 1, 0);p[1] = 131;for (int i = 2; i <= len; i++) {p[i] = p[i - 1] * 131 ;}for (int i = 1; i < len; i++) {Lhasp[i] = Lhasp[i - 1]*131+s[i] ;//cout<<Lhasp[i]<<endl;}p[len-1] = 131;for (int i = len - 2; i >= 1; i--) {p[i] = p[i + 1] * 131 ;}for (int i = len - 1; i >= 1; i--) {Rhasp[i] = Rhasp[i + 1] * 131 +s[i];//cout<<Rhasp[i]<<endl;}p[1] = 131;for (int i = 2; i <= len; i++) {p[i] = p[i - 1] * 131 ;}auto get = [&](int a, int b) -> bool {i64 res1 = Lhasp[b] - Lhasp[a - 1]*p[b-a+1] ;i64 res2 = Rhasp[a] - Rhasp[b + 1]*p[(len-a)-(len-b)+1] ; int p1 = a - 1, p2 = len-1 - b;//cout<<a<<' '<<b<<' '<<p1<<' '<<p2<<endl;return res1==res2;};for (int i = 1; i < len; i++) {int cnt = 1;for (int j = i; j >= 1; j--) {if (i == j) dp[j][i] = 1;else {cnt += get(j, i);//cout<<j<<' ' <<i<<' '<<cnt<<' '<<"ans:";dp[j][i] += dp[j][i - 1] + cnt;//cout<<dp[j][i]<<endl;}//cout<<dp[j][i]<<endl;}}int q;cin >> q;while (q--) {int l, r;cin >> l >> r;cout << dp[l][r] << endl; }
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);solve();return 0;
}
