[网络流]最大流

网络流最大流最小割

题目链接

就是一道点割。

先说边割

边割比较常见。

最大流

最大流等于最小割&＃xff0c;我懒得证。

求最大流的思路就是每次尝试找一条从源点到汇点的通路&＃xff0c;然后找到这条路上残余流量最小的流量&＃xff0c;答案加上这个流量&＃xff0c;这条通路上每条边的残余流量减去这个值&＃xff0c;反向边加上这个值。

关于反向边&＃xff0c;实际上是一个反悔机制。反向流多少&＃xff0c;表示正向已经流了多少。也就是说&＃xff0c;如果我们从反向边流了一些流量&＃xff0c;就相当于从这条边退回了一部分流量。

点割

所谓点割&＃xff0c;就是被割掉的不再是边&＃xff0c;而是点。思路是将点转化成边。

如上题&＃xff1a;将每个点拆成\(i\)和\(i&＃43;n\)两个点&＃xff0c;中间连一条流量为\(1\)的边&＃xff0c;将这条边割掉&＃xff0c;就相当于割掉这个点。

详见代码。

#include
#include
#include
#include
using namespace std;
long long read(){long long x &＃61; 0; int f &＃61; 0; char c &＃61; getchar();while(c <&＃39;0&＃39; || c > &＃39;9&＃39;) f |&＃61; c &＃61;&＃61; &＃39;-&＃39;, c &＃61; getchar();while(c >&＃61; &＃39;0&＃39; && c <&＃61; &＃39;9&＃39;) x &＃61; (x <<1) &＃43; (x <<3) &＃43; (c ^ 48), c &＃61; getchar();return f ? -x:x;
}const int INF &＃61; 2147483647;
int n, m, s, t;
struct szh{int nxt, to, w;
}a[4004];
int head[203],cnt&＃61;1;
void add(int x, int y, int w){a[&＃43;&＃43;cnt].nxt &＃61; head[x], a[cnt].to &＃61; y, head[x] &＃61; cnt, a[cnt].w &＃61; w;
}int dis[203];
bool bfs(){memset(dis, 0, sizeof dis);queue q;q.push(s), dis[s] &＃61; 1;while(!q.empty()){int u &＃61; q.front();q.pop();for (int i &＃61; head[u], v; v &＃61; a[i].to, i; i &＃61; a[i].nxt)if(a[i].w && !dis[v]) q.push(v), dis[v] &＃61; dis[u] &＃43; 1;}return dis[t];
}int fir[103];
int dfs(int u, int flow){if(u &＃61;&＃61; t || !flow) return flow;int ans &＃61; 0;for (int &i &＃61; fir[u], v; v &＃61; a[i].to, i; i &＃61; a[i].nxt)//弧优化if(a[i].w && dis[v] &＃61;&＃61; dis[u] &＃43; 1){int x &＃61; dfs(v, min(flow, a[i].w));a[i].w -&＃61; x, a[i^1].w &＃43;&＃61; x, ans &＃43;&＃61; x; //更新残余流量if(!(flow-&＃61;x)) break;}return ans;
}void dinic(){int ans &＃61; 0;while(bfs()){for (int i &＃61; 1; i <&＃61; (n <<1); &＃43;&＃43;i) fir[i] &＃61; head[i];//为dfs中取址操作做铺垫ans &＃43;&＃61; dfs(s,INF);}printf("%d", ans);
}int main(){n &＃61; read(), m &＃61; read(), s &＃61; read(), t &＃61; read();s &＃43;&＃61; n; //源点不能删掉for (int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) add(i, i &＃43; n, 1), add(i &＃43; n, i, 0);//拆点for (int i &＃61; 1; i <&＃61; m; &＃43;&＃43;i){int x &＃61; read(), y &＃61; read();add(x &＃43; n, y, INF), add(y, x &＃43; n, 0); //电脑之间不会断&＃xff0c;所以连INFadd(y &＃43; n, x, INF), add(x, y &＃43; n, 0);}dinic(); //模板return 0;
}