初学网络流。存一下Dinic板子。
复杂度O(n^2*m)
UVA - 1515 Pool construction
把每个草地与 S 相连，花费为dig，每个洞与 T 相连，花费为
然后对于每个两个相邻的点连一条权值为 build 的边。
求最小割，就是把草和洞分开的花费。
因为只有三种割的情况：
割S与草之间的边，那么这个草就与T相连了。所以花费需要dig。
割T与洞之间的边。同理。
割两个相邻的点之间的边。很显然，如果他们连着同一个点（源点或者汇点），那么他们是不会被割开的。
所以只有他们连着不同的点的时候，才会需要花费build割开。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue> using namespace std;
const int N = ;
const int maxn = N*N++;
const int maxm = maxn**;
const int INF=0x3f3f3f3f;
int g[N][N];
int n,m,dig,fil,bui;
int S, T;
int ans = ; struct Dinic{
int head[maxn],Next[maxm],to[maxm],cap[maxm],flow[maxm];
int sz,n,m,s,t;
bool vis[maxn];
int cur[maxn],d[maxn];
void init(int n){
this->n=n;
memset(head,-,sizeof(head));
this->sz=-;
}
void add_edge(int a,int b,int c){
++sz;
to[sz]=b;
cap[sz]=c;flow[sz]=;
Next[sz]=head[a];head[a]=sz;
++sz;
to[sz]=a;
cap[sz]=c;flow[sz]=c;
Next[sz]=head[b];head[b]=sz;
}
bool BFS(){
memset(vis,,sizeof(vis));
queue<int>Q;
vis[s]=;
d[s]=;
Q.push(s);
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=head[u];i!=-;i=Next[i]){
int v=to[i];
if(!vis[v]&&cap[i]>flow[i]){
vis[v]=;
d[v]=d[u]+;
Q.push(v);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x==t||a==)return a;
int Flow=,f;
for(int& i=cur[x];i!=-;i=Next[i]){
int v=to[i];
if(d[v]==d[x]+&&(f=DFS(v,min(a,cap[i]-flow[i])))>){
Flow+=f;
flow[i]+=f;
flow[i^]-=f;
a-=f;
if(a==)break;
}
}
return Flow;
}
int Maxflow(int s,int t){
this->s=s,this->t=t;
int Flow=;
while(BFS()){
for(int i=;i<=n;i++)
cur[i]=head[i]; Flow+=DFS(s,INF);
}
return Flow;
}
}dinic; inline int id(int x, int y)
{
return (x-)*m + y;
} int main()
{
int t;
scanf("%d", &t);
for (int ca = ; ca <= t; ca ++)
{
scanf("%d%d",&m,&n);
scanf("%d%d%d", &dig, &fil, &bui);
ans = ;
dinic.init(n*m+);
S = n*m+, T = n*m+; for (int i = ; i <= n; i++)
{
char x;
for (int j = ; j <= m; j++)
scanf(" %c", &x), g[i][j] = x=='#' ? :;
} int dx[] = {, , , -}, dy[] = {, , -, }; for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++)
{
if (i == || j == || i == n || j == m)
{
if (!g[i][j]) ans += fil, g[i][j] = ;
dinic.add_edge(S, id(i, j), INF);
}
else if (g[i][j]) dinic.add_edge(S, id(i, j), dig);
else dinic.add_edge(id(i, j), T, fil); for (int k = ; k < ; k++)
{
int Fx = i+dx[k], Fy = j+dy[k];
if (Fx < || Fx > n || Fy < || Fy > m) continue;
dinic.add_edge(id(i, j), id(Fx, Fy), bui);
}
} ans += dinic.Maxflow(S, T);
printf("%d\n", ans);
} return ;
}
模板题：CodeVS 1993 草地排水
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue> using namespace std;
const int maxn=+;
const int INF=; struct Dinic
{
int head[maxn],Next[maxn],to[maxn],cap[maxn],flow[maxn];
//cap:容量, flow:流量
int sz,n,m,s,t;
bool vis[maxn];
int cur[maxn],d[maxn]; //d:depth cur当前弧优化
void init(int nn,int mm)
{
n=nn, m=mm;
memset(head,-,sizeof(head));
sz=-; //注意 方便亦或找反向边
} void add_edge(int a,int b,int c)
{
++sz;
to[sz]=b, Next[sz]=head[a], head[a]=sz;
cap[sz]=c, flow[sz]=; ++sz;
to[sz]=a, Next[sz]=head[b];head[b]=sz;
cap[sz]=c, flow[sz]=c; //正向的增加，反向的减少
}//加双向边 bool BFS()
{
memset(vis,,sizeof(vis));
queue<int>Q;
vis[s]=;
d[s]=;
Q.push(s);
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=head[u];i!=-;i=Next[i]){
int v=to[i];
if(!vis[v]&&cap[i]>flow[i]){
vis[v]=;
d[v]=d[u]+;
Q.push(v);
}
}
}
return vis[t];
}//求深度 int DFS(int x,int a){
if(x==t||a==)return a;//当前增广路上的最小残量
int Flow=,f;
for(int& i=cur[x];i!=-;i=Next[i]){
int v=to[i];
if(d[v]==d[x]+&&(f=DFS(v,min(a,cap[i]-flow[i])))>){
Flow+=f;
flow[i]+=f;
flow[i^]-=f;//
a-=f;
if(a==)break;
}
}
return Flow;
}//增广路 int Maxflow(int ss,int tt)
{
s=ss, t=tt;
int Flow=;
while(BFS())
{
for(int i=;i<=n;i++) cur[i]=head[i];
Flow+=DFS(s,INF);
}
return Flow;
} }dinic; int n,m;
int main()
{
scanf("%d%d",&m,&n);
dinic.init(n, m);
int a, b, c;
for(int i = ; i <= m; i++){
scanf("%d%d%d", &a, &b, &c);
dinic.add_edge(a, b, c);
}
int ans = dinic.Maxflow(, n);
cout<<ans<<endl; return ;
}
HDU - 5889 Barricade
先跑一遍最短路，然后从最短路上的边中跑最小割。
TLE代码。。。我也不知道为什么会TLE。以后再改。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue> #define mms(k, x) memset(k, (x), sizeof(k)) using namespace std;
const int maxn = +;
const int maxm = *+;
const int INF = 0x3f3f3f3f; struct Dinic
{
int head[maxm],Next[maxm],to[maxm],cap[maxm],flow[maxm];
//cap:容量, flow:流量
int sz,n,m,s,t;
bool vis[maxn];
int cur[maxn],d[maxn]; //d:depth cur当前弧优化
void init(int nn,int mm)
{
n=nn, m=mm;
mms(head, -);
sz=-; //注意 方便亦或找反向边
} void add_edge(int a,int b,int c)
{
++sz;
to[sz]=b, Next[sz]=head[a], head[a]=sz;
cap[sz]=c, flow[sz]=; ++sz;
to[sz]=a, Next[sz]=head[b];head[b]=sz;
cap[sz]=c, flow[sz]=c; //正向的增加，反向的减少
}//加双向边 bool BFS()
{
memset(vis,,sizeof(vis));
queue<int>Q;
vis[s]=;
d[s]=;
Q.push(s);
while(!Q.empty())
{
int u=Q.front(); Q.pop();
for(int i = head[u]; i != -; i = Next[i])
{
int v = to[i];
if(!vis[v] && cap[i] > flow[i])
{
vis[v]=;
d[v]=d[u]+;
Q.push(v);
}
}
}
return vis[t];
}//求深度 int DFS(int x,int a){
if(x==t||a==)return a;//当前增广路上的最小残量
int Flow=,f;
for(int& i=cur[x];i!=-;i=Next[i]){
int v=to[i];
if(d[v]==d[x]+&&(f=DFS(v,min(a,cap[i]-flow[i])))>){
Flow+=f;
flow[i]+=f;
flow[i^]-=f;//
a-=f;
if(a==)break;
}
}
return Flow;
}//增广路 int Maxflow(int ss,int tt)
{
s=ss, t=tt;
int Flow=;
while(BFS())
{
for(int i=;i<=n;i++) cur[i]=head[i];
Flow+=DFS(s,INF);
}
return Flow;
} }dinic; int v[maxm], nxt[maxm], last[maxm], l[maxm], u[maxm];
int dis[maxn], vis[maxn];
int tot = ; void build(int x, int y, int z)
{
tot++, v[tot] = y;
nxt[tot] = last[x], last[x] = tot, l[tot] = z;
u[tot] = x;
} void init()
{
tot = , mms(last, );
} int relax(int x, int y, int tmp)
{
if (dis[x]+ < dis[y])
{
dis[y] = dis[x] + ;
return ;
}
return ;
} void SPFA(int k)
{
queue<int> q;
mms(dis, INF), mms(vis, );
q.push(k), dis[k] = , vis[k] = ; while(!q.empty())
{
int x = q.front(), y;
q.pop();
for (int i = last[x]; i; i = nxt[i])
{
int y = v[i];
if (relax(x, y, i) && !vis[y]) q.push(y), vis[y] = ;
}
vis[x] = ;
}
} int n,m;
int main()
{
int t;
scanf("%d", &t);
for (int ca = ; ca <= t; ca++)
{
init();
scanf("%d%d",&m,&n);
dinic.init(n, m);
int a, b, c;
for(int i = ; i <= m; i++)
{
scanf("%d%d%d", &a, &b, &c);
build(a, b, c);
build(b, a, c);
} SPFA();
for (int i = ; i <= tot; i+=)
{
int x = u[i], y = v[i], c = l[i];
if (dis[y]-dis[x] == )
dinic.add_edge(x, y, c);
else if (dis[x]-dis[y] == )
dinic.add_edge(y, x, c);
} int ans = dinic.Maxflow(, n);
printf("%d\n", ans);
}
return ;
}