先贴个自己的Dinic板子。
//最大流
const int inf = 0x3f3f3f3f3f3f3f3f;
struct Edge{
int from, to, cap;
bool ori;
Edge(int u, int v, int c, bool o){
from = u, to = v, cap = c, ori = o;
}
};
vector<Edge> edges;
vector<int> id[10005];
int add_edge(int u, int v, int w){
edges.push_back(Edge(u, v, w, 1));
edges.push_back(Edge(v, u, 0, 0));
id[u].push_back(edges.size() - 2);
id[v].push_back(edges.size() - 1);
return 0;
}
int n, m, s, t, sum;
int dep[10005], inq[10005], cur[10005], vis;
int bfs(){
memset(dep, 0x3f, sizeof(dep));
memset(inq, 0, sizeof(vis));
memset(cur, 0, sizeof(cur));
dep[s] = 0;
queue<int> q;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
inq[u] = 0;
for(int i = 0, v; i < id[u].size(); i ++){
Edge e = edges[id[u][i]];
v = e.to;
if(dep[v] > dep[u] + 1 && e.cap){
dep[v] = dep[u] + 1;
if(inq[v] == 0){
q.push(v);
inq[v] = 1;
}
}
}
}
if(dep[t] != inf) return 1;
return 0;
}
int maxflow;
int dfs(int u, int flow){
int rlow = 0;
if(u == t){
vis = 1;
maxflow += flow;
return flow;
}
int used = 0;
for(int i = cur[u]; i < id[u].size(); i ++){
cur[u] = i;
Edge e = edges[id[u][i]];
int v = e.to;
if(e.cap && dep[v] == dep[u] + 1){
if(rlow = dfs(v, min(flow - used, e.cap))){
used += rlow;
edges[id[u][i]].cap -= rlow;
edges[id[u][i] ^ 1].cap += rlow;
if(used == flow) break;
}
}
}
return used;
}
int Dinic(){
while(bfs()){
vis = 1;
while(vis == 1){
vis = 0;
dfs(s, inf);
}
}
return maxflow;
}
//费用流
const int inf = 0x3f3f3f3f3f3f3f3f;
struct Edge{
int from, to, cap, cost;
bool ori;
Edge(int u, int v, int c, bool o, int cc){
from = u, to = v, cap = c, ori = o, cost = cc;
}
};
vector<Edge> edges;
vector<int> id[80005];
int add_edge(int u, int v, int w, int c){
edges.push_back(Edge(u, v, w, 1, c));
edges.push_back(Edge(v, u, 0, 0, -c));
id[u].push_back(edges.size() - 2);
id[v].push_back(edges.size() - 1);
return 0;
}
int n, m, s, t, sum;
int dep[80005], cur[80005], vis[80005];
int bfs(){
memset(dep, 0x3f, sizeof(dep));
memset(cur, 0, sizeof(cur));
memset(vis, 0, sizeof(vis));
dep[s] = 0;
vis[s] = 1;
queue<int> q;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = 0;
for(int i = 0, v; i < id[u].size(); i ++){
Edge e = edges[id[u][i]];
v = e.to;
if(dep[v] > dep[u] + e.cost && e.cap){
dep[v] = dep[u] + e.cost;
if(vis[v] == 0){
q.push(v);
vis[v] = 1;
}
}
}
}
if(dep[t] != inf) return 1;
return 0;
}
int maxflow, sumcost;
int dfs(int u, int flow){
int rlow = 0;
// cout << u << " ";
if(u == t){
vis[t] = 1;
maxflow += flow;
return flow;
}
int used = 0;
vis[u] = 1;
for(int i = cur[u]; i < id[u].size(); i ++){
// cout << 'a';
cur[u] = i;
Edge e = edges[id[u][i]];
int v = e.to;
if((vis[v] == 0 || v == t) && e.cap && dep[v] == dep[u] + e.cost){
if(rlow = dfs(v, min(flow - used, e.cap))){
used += rlow;
sumcost += rlow * e.cost;
edges[id[u][i]].cap -= rlow;
edges[id[u][i] ^ 1].cap += rlow;
if(used == flow) break;
}
}
}
return used;
}
int Dinic(){
maxflow = 0, sumcost = 0;
while(bfs()){
vis[t] = 1;
while(vis[t] == 1){
memset(vis, 0, sizeof(vis));
dfs(s, inf);
// system("pause");
}
}
return maxflow;
}
P1251 餐巾计划问题
考虑定义 1 流量。如果直接以毛巾作为流量，会导致出现一条使用过的毛巾就从汇点流走了，没法贡献给后面的日子的情况。因此考虑以“毛巾的使用次数”为流量。
那么，对于 1 使用次数，有两种情况：
- 这是最后一次使用这条毛巾。
- 这条毛巾会往后贡献。
那么我们将这两种情况拆点。第一类点显然直接连汇点，容量为 \(a_i\) 。这条毛巾可能是直接买的或者从前面拿来的。所以先连一条从源点到这个点的费用为 \(p\) 的边代表直接买毛巾，然后把能贡献到它的二类点与这个点连边，费用为洗毛巾的费用即可。因为最后一定会流满所以从源点向二类点连容量为 \(a_i\) 费用为 0 的边。跑 Dinic 即可。
cin >> N;
s = 50001, t = 50002;
for(int i = 1; i <= N; i ++)
cin >> a[i];
cin >> p >> m >> f >> n >> f1;
for(int i = 1; i <= N; i ++)
add_edge(s, i + N, inf, p);
for(int i = 1; i <= N; i ++)
add_edge(i + N, t, a[i], 0);
for(int i = 1; i <= N; i ++)
add_edge(s, i, a[i], 0);
for(int i = 1; i < N; i ++)
add_edge(i, i + 1, inf, 0);
for(int i = 1; i <= N - m; i ++)
add_edge(i, i + m + N, inf, f);
for(int i = 1; i <= N - n; i ++)
add_edge(i, i + n + N, inf, f1);
Dinic();
cout << sumcost;
P2765 魔术球问题
好玩题。
分类讨论一个数。对于每个数，它有可能单独放在一个柱子上，也有可能跟之前的某个数凑成完全平方数放到一个柱子上。直接从柱子角度考虑困难，那么正难则反。
假设我们找到了答案，设其为 \(Ans\)，考虑直接将 \(1\) 到 \(Ans\) 能连起来的数字连有向边，那么最终会形成一张 DAG 。而每根柱子对应了DAG上的一条路径，而此时这张 DAG 上的最小路径覆盖即为柱子数。DAG 上的最小路径覆盖问题为经典网络流问题，那么只用找到 \(Ans\) 满足 DAG 的最小路径覆盖为 \(n\) 且 \(Ans+1\) 的最小路径覆盖大于 \(n\) 即可。暴力的做法即为枚举 \(Ans\)，对于每个 \(Ans\) 跑一遍 Dinic 。
这个时候其实可以二分答案一下，但是没必要。根据网络流的性质，更好的方法是每次枚举新的 \(Ans\) 时在原本的残量网络上直接加边跑 Dinic 。时间复杂度不会证明，反正不大（
s = 8200, t = 8201;
for(int i = 1; i <= 55; i ++)
chk[i * i] = 1;
cin >> N;
add_edge(s, 1, 1);
add_edge(4001, t, 1);
Dinic();
while(M - maxflow <= N){
M ++;
add_edge(s, M, 1);
add_edge(M + 4000, t, 1);
for(int i = 1; i < M; i ++){
if(!chk[i + M]) continue;
add_edge(i, M + 4000, 1);
}
Dinic();
}