最近总是不知不觉地就做到了网络流的题，感觉知识树要点偏。算了，先随便写点东西再说。
[AHOI2009]最小割
显然一条边至少要满流才有可能是被割边。
先考虑存在性问题，若一条边为某个最小割割边集中的边，那么这条边一定是该最小割中无法取代的。对于一条流量为 \(0\) 的边 \((u,v)\)，如果在残量网络上存在从 \(u\) 到 \(v\) 的路径，即在残量网络上 \(u,v\) 属于同一连通块（因为 \((v,u)\) 这条边必然在残量网络中），那么可以从这条路径中分点流量到另一条路径，就不存在一个最小代价路径切断方案，其中该道路被切断。
再考虑必要性问题，先给出结论，当且仅当 \(u\) 和 \(S\) 在同一强连通分量中，同时 \(v\) 和 \(T\) 在同一强连通分量中。因为一条边如果没满流，那么残量网络上必然同时存在原边和反边，两端点同属一强连通分量。考虑缩点后的 DAG，从 \(S\) 到 \(T\) 的路径上如果有不止一条边，那么没有一条边是必然被切断的。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e4+10,M=1e5+10,inf=INT_MAX;
int n,m,S,T,tot=1,head[N];
struct edge{
int u,v,nxt,w;
}e[M<<2];
void add(int u,int v,int w){
e[++tot].v=v;
e[tot].u=u;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
int dep[N],cur[N];
bool bfs(int S,int T){
for(int i=1;i<=n;i++){
dep[i]=0;
}
dep[S]=1;
queue<int>q;
q.push(S);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(!dep[v]&&w){
dep[v]=dep[u]+1;
if(v==T){
return 1;
}
q.push(v);
}
}
}
return 0;
}
int dfs(int u,int flow,int T){
if(u==T){
return flow;
}
int s=0;
for(int i=cur[u];i;i=e[i].nxt){
cur[u]=i;
int v=e[i].v,w=e[i].w;
if(dep[v]==dep[u]+1&&w){
int res=dfs(v,min(flow,w),T);
s+=res;
flow-=res;
e[i].w-=res;
e[i^1].w+=res;
}
if(!flow){
break;
}
}
if(!s){
dep[u]=0;
}
return s;
}
int dfn[N],low[N],col[N],idx,col_num,stk[N],top,in_stack[N];
void tarjan(int u){
low[u]=dfn[u]=++idx;
stk[++top]=u;
in_stack[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(!w){
continue;
}
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(in_stack[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
col[u]=++col_num;
in_stack[u]=0;
while(stk[top]!=u){
col[stk[top]]=col_num;
in_stack[stk[top]]=0;
top--;
}
top--;
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m),read(S),read(T);
for(int i=1;i<=m;i++){
int u,v,w;
read(u),read(v),read(w);
add(u,v,w);
add(v,u,0);
}
while(bfs(S,T)){
for(int i=1;i<=n;i++){
cur[i]=head[i];
}
dfs(S,inf,T);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i);
}
}
for(int i=1;i<=m;i++){
if(!e[i<<1].w){
int u=e[i<<1].u,v=e[i<<1].v;
if(col[u]!=col[v]){
write_space(1);
}
else{
write_space(0);
}
if(col[u]==col[S]&&col[v]==col[T]){
write_endl(1);
}
else{
write_endl(0);
}
}
else{
puts("0 0");
}
}
return 0;
}
[NOI2009] 植物大战僵尸
我们将一个植物前面的植物视作也保护它的植物。因为要击溃一个植物，必须击溃保护它的植物。所以，从保护的植物连边到被保护的植物。但是可能有环，环上的植物是不可能被击溃，所以做一遍拓扑排序，只有被遍历过的植物才有可能是被击溃的植物。我们只保留遍历过的植物，和边上的两个植物都遍历过的边。那么最后题目就变成了求这个图的最大权闭合子图。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=610,M=1e6+10,inf=1e9 ;
int n,m,val[N];
int id(int x,int y){
return (x-1)*m+y;
}
vector<int>G[N],out[N];
int deg[N],vis[N],S,T,tot=1,head[N],ans;
void topo(){
queue<int>q;
for(int i=1;i<=n*m;i++){
if(!deg[i]){
q.push(i);
}
}
while(!q.empty()){
int u=q.front();
vis[u]=1;
q.pop();
for(auto v:G[u]){
deg[v]--;
if(!deg[v]){
q.push(v);
}
}
}
}
struct node{
int v,w,nxt;
}e[M<<1];
void add(int u,int v,int w){
e[++tot].v=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
int dep[N],cur[N];
bool bfs(int S,int T){
for(int i=1;i<=T;i++){
dep[i]=0;
}
queue<int>q;
q.push(S);
dep[S]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w&&!dep[v]){
dep[v]=dep[u]+1;
if(v==T){
return 1;
}
q.push(v);
}
}
}
return 0;
}
int dfs(int u,int flow,int T){
if(u==T){
return flow;
}
int s=0;
for(int i=cur[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w&&dep[v]==dep[u]+1){
int res=dfs(v,min(flow,w),T);
e[i].w-=res;
e[i^1].w+=res;
s+=res;
flow-=res;
}
if(!flow){
break;
}
}
if(!s){
dep[u]=0;
}
return s;
}
int dinic(int S,int T){
int sum=0;
while(bfs(S,T)){
for(int i=1;i<=T;i++){
cur[i]=head[i];
}
sum+=dfs(S,inf,T);
}
return sum;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m);
S=n*m+1,T=n*m+2;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
read(val[id(i,j)]);
int sum;
read(sum);
for(int k=1,x,y;k<=sum;k++){
read(x),read(y);
x++,y++;
out[id(i,j)].pb(id(x,y));
G[id(i,j)].pb(id(x,y));
deg[id(x,y)]++;
}
if(j<m){
out[id(i,j+1)].pb(id(i,j));
G[id(i,j+1)].pb(id(i,j));
deg[id(i,j)]++;
}
}
}
topo();
for(int i=1;i<=n*m;i++){
if(!vis[i]){
continue;
}
if(val[i]>0){
add(S,i,val[i]);
add(i,S,0);
ans+=val[i];
}
else{
add(i,T,-val[i]);
add(T,i,0);
}
for(auto x:out[i]){
if(!vis[x]){
continue;
}
add(x,i,inf);
add(i,x,0);
}
}
write_endl(ans-dinic(S,T));
return 0;
}
[SDOI2013]费用流
别看到题目叫作费用流，就一股脑写费用流了。注意到题目中有句话，Bob在分配单位花费之前，已经知道Alice所给出的最大流方案。那么Bob的赋权方法就是确定的，将所有权值赋给这个最大流方案中流量最大的边，那么题目要求的东西就变成了求最大流并求一个最大流方案，使得流量最大的边流量最小。
求最大值最小，二分最大边流量 \(x\)，所有边的流量对 \(x\) 取 \(\min\)。看这样的图上的最大流是否是原图上的最大流，是则说明这个最大流量是合法，反之亦然。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=110,M=1e3+10,inf=1e9;
int head[N],tot=1,n,m,S,T,val;
double max_flow;
struct edge{
int v,nxt;
double W,w;
}e[M<<1];
int dep[N],cur[N];
bool bfs(int S,int T){
for(int i=1;i<=n;i++){
dep[i]=0;
}
dep[S]=1;
queue<int>q;
q.push(S);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
double w=e[i].w;
if(!dep[v]&&w>eps){
dep[v]=dep[u]+1;
if(v==T){
return 1;
}
q.push(v);
}
}
}
return 0;
}
double dfs(int u,double flow,int T){
if(u==T){
return flow;
}
double s=0;
for(int i=cur[u];i;i=e[i].nxt){
cur[u]=i;
int v=e[i].v;
double w=e[i].w;
if(dep[v]==dep[u]+1&&w>eps){
double res=dfs(v,min(flow,w),T);
e[i].w-=res;
e[i^1].w+=res;
flow-=res;
s+=res;
}
if(flow<eps){
break;
}
}
if(!s){
dep[u]=0;
}
return s;
}
double dinic(int S,int T){
double flow=0;
while(bfs(S,T)){
for(int i=1;i<=n;i++){
cur[i]=head[i];
}
flow+=dfs(S,inf,T);
}
return flow;
}
void add(int u,int v,int w){
e[++tot].v=v;
e[tot].W=e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
void add_e(int u,int v,int w){
add(u,v,w);
add(v,u,0);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m),read(val);
for(int i=1,u,v,w;i<=m;i++){
read(u),read(v),read(w);
add_e(u,v,w);
}
S=1,T=n;
max_flow=dinic(S,T);
write_endl((int)max_flow);
ll l=0,r=5e9,ans=0;
while(l<=r){
ll mid=(l+r)>>1;
for(int i=1;i<=tot;i++){
e[i].w=min(e[i].W,1.0*mid/100000.0);
}
double flow=dinic(S,T);
if(fabs(flow-max_flow)<eps){
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
printf("%.6lf\n",ans/100000.0*val);
return 0;
}