刚学了最大流的 EK 算法和 Dinic 算法，在此做一点总结。
由于这次专题学习是偏向图论建模的，因此目前暂且不涉及算法本身。
Dinic 板子：
namespace Net{
int S,T;
int head[510],work[510],etot = 1;
struct node{ int nxt,v,cap; }edge[160010];
inline void add(int x,int y,int w){
edge[++etot] = {head[x],y,w};
head[x] = etot;
}
inline void addedge(int u,int v,int w){ add(u,v,w),add(v,u,0); }
int dis[510];
bool vis[510];
bool bfs(){
queue<int> q;
for(int i = S;i<=T;++i)dis[i] = -1;
dis[S] = 0;
q.push(S);
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = head[x];i;i = edge[i].nxt){
int v = edge[i].v;
if(edge[i].cap > 0 && dis[v] == -1){
dis[v] = dis[x] + 1;
q.push(v);
}
}
}
return (dis[T] >= 0);
}
int dfs(int u,int flow){
if(u == T)return flow;
for(int &i = work[u];i;i = edge[i].nxt){
int v = edge[i].v;
if(edge[i].cap > 0 && dis[v] == dis[u] + 1){
int tmp = dfs(v,min(flow,edge[i].cap));
if(tmp > 0){
edge[i].cap -= tmp;
edge[i^1].cap += tmp;
return tmp;
}
}
}
return 0;
}
int Dinic(){
int ans = 0;
while(bfs()){
for(int i = S;i<=T;++i)work[i] = head[i];
while(1){
int flow = dfs(S,inf);
if(flow == 0)break;
ans += flow;
}
}
return ans;
}
}
Dinic 邻接矩阵（没有当前弧优化）
namespace Net{
int S,T;
ll cap[N][N];
inline void addedge(int x,int y,ll w){
cap[x][y] = w;
cap[y][x] = 0;
}
int dist[N];
bool vis[N];
ll dfs(int u,ll flow){
if(u == T)return flow;
for(int i = S;i<=T;++i)if(cap[u][i] != -1){
if(cap[u][i] > 0 && dist[i] == dist[u] + 1){
int tmp = dfs(i,min(cap[u][i],flow));
if(tmp > 0){
cap[u][i] -= tmp;
cap[i][u] += tmp;
return tmp;
}
}
}
return 0;
}
bool bfs(){
queue<int> q;
for(int i = S;i<=T;++i)dist[i] = -1;
q.push(S); dist[S] = 0;
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = S;i<=T;++i)if(cap[x][i] > 0 && dist[i] == -1){
dist[i] = dist[x] + 1;
q.push(i);
}
}
return (dist[T] >= 0);
}
ll Dinic(ll lim){
S = 0, T = F * 2 + 1;
for(int i = S;i<=T;++i)
for(int j = S;j<=T;++j)cap[i][j] = -1;
for(int i = 1;i<=F;++i){
addedge(S,i,cow[i]);
addedge(i+F,T,pen[i]);
for(int j = 1;j<=F;++j)
if(dis[i][j] <= lim)addedge(i,j+F,inf);
}
ll ans = 0;
while(bfs()){
while(1){
ll flow = dfs(S,inf);
if(flow == 0)break;
ans += flow;
}
}
return ans;
}
}
using namespace Net;
图论建模
P3254圆桌问题
basic
套路地，将人看作“流水”，那么我们可以通过人数的流向具象化桌子与单位之间的关系。具体做法：
每一个单位作为一个点，每一个桌子看作一个点，源点 \(S\) 向每一个单位 \(i\) 连一条权值为 \(r[i]\) 的边，每一个桌子 \(i\) 向汇点连一条权值为 \(c[i]\) 的边。这样我们看所有人是否可以都入座就是看最大流是不是等于总人数。
对于中间的，由于题目条件“同一个单位来的代表不在同一个餐桌就餐”，因此，每一个单位向每一个餐桌连一条权值为 \(1\) 的有向边。
方案就是去看看对于一条 单位->桌子 的边，跑完后这条边的剩余容量是否为 \(0\)，若是，则表明这一条边有人选择。
scanf("%d%d",&m,&n);
S = 0, T = m + n + 1;
for(int i = 1;i<=m;++i){
scanf("%d",&r[i]);
addedge(S,i,r[i]);
cnt += r[i];
}
for(int i = 1;i<=n;++i){
scanf("%d",&c[i]);
addedge(i+m,T,c[i]);
}
for(int i = 1;i<=m;++i)
for(int j = m+1;j<=m+n;++j)
addedge(i,j,1);
int res = Dinic();
if(res != cnt)return puts("0"),0;
puts("1");
for(int i = 1;i<=m;++i){
for(int j = head[i];j;j = edge[j].nxt){
int v = edge[j].v - m;
if(edge[j].cap == 0)printf("%d ",v);
}
puts("");
}
P6768 [USACO05MAR] Ombrophobic Bovines 发抖的牛
二分
要求最小时间，明显符合单调性，故二分答案。
与上题类似，将牛作为“水流”。
建图：
- S->每一个田地（代表这个田地的牛），边权为该位置牛的数量
- 每一个田地（代表这个田地的牛棚）->T，边权为牛棚容量
- 对于在二分的 \(mid\) 时间内可以到达的位置，连出一条权值为 \(inf\) 的边，因为“路很宽，无限量的牛可以通过”。
观察到数据范围很小，最短路可以用 Floyed 处理。
ll Dinic(ll lim){
S = 0, T = F * 2 + 1;
for(int i = S;i<=T;++i)
for(int j = S;j<=T;++j)cap[i][j] = -1;
for(int i = 1;i<=F;++i){
addedge(S,i,cow[i]);
addedge(i+F,T,pen[i]);
for(int j = 1;j<=F;++j)
if(dis[i][j] <= lim)addedge(i,j+F,inf);
}
ll ans = 0;
while(bfs()){
while(1){
ll flow = dfs(S,inf);
if(flow == 0)break;
ans += flow;
}
}
return ans;
}
拆点
由于“每头牛只享用一种食物和一种饮料”，我们直接 S->食物->牛->饮料->T 的思路是错误的。
那么我们应当利用网络流中边的限定功能。
考虑拆点，一只牛被拆成了两个点，两点间连了一条权值为 \(1\) 的边，这样就可以保证一只牛只吃一对了。
拆点是个好东西！
S = 0, T = 2 * n + F + D + 1;
for(int i = 1;i<=F;++i)addedge(S,i,1);
for(int i = 2*n+F+1;i<=2*n+F+D;++i)addedge(i,T,1);
for(int i = 1;i<=n;++i)addedge(F+i,F+i+n,1);
for(int i = 1,a,b;i<=n;++i){
scanf("%d%d",&a,&b);
// cow_i F+i->F+i+n
for(int j = 1,x;j<=a;++j){
scanf("%d",&x);
addedge(x,F+i,1);
}
for(int j = 1,x;j<=b;++j){
scanf("%d",&x);
addedge(F+i+n,2*n+F+x,1);
}
}
printf("%d",Dinic());