初学网络流。存一下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 = 55; const int maxn = N*N+2+100; const int maxm = maxn*4*2; const int INF=0x3f3f3f3f; int g[N][N]; int n,m,dig,fil,bui; int S, T; int ans = 0; 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,-1,sizeof(head)); this->sz=-1; } void add_edge(int a,int b,int c){ ++sz; to[sz]=b; cap[sz]=c;flow[sz]=0; 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,0,sizeof(vis)); queue<int>Q; vis[s]=1; d[s]=0; Q.push(s); while(!Q.empty()){ int u=Q.front();Q.pop(); for(int i=head[u];i!=-1;i=Next[i]){ int v=to[i]; if(!vis[v]&&cap[i]>flow[i]){ vis[v]=1; d[v]=d[u]+1; Q.push(v); } } } return vis[t]; } int DFS(int x,int a){ if(x==t||a==0)return a; int Flow=0,f; for(int& i=cur[x];i!=-1;i=Next[i]){ int v=to[i]; if(d[v]==d[x]+1&&(f=DFS(v,min(a,cap[i]-flow[i])))>0){ Flow+=f; flow[i]+=f; flow[i^1]-=f; a-=f; if(a==0)break; } } return Flow; } int Maxflow(int s,int t){ this->s=s,this->t=t; int Flow=0; while(BFS()){ for(int i=0;i<=n;i++) cur[i]=head[i]; Flow+=DFS(s,INF); } return Flow; } }dinic; inline int id(int x, int y) { return (x-1)*m + y; } int main() { int t; scanf("%d", &t); for (int ca = 1; ca <= t; ca ++) { scanf("%d%d",&m,&n); scanf("%d%d%d", &dig, &fil, &bui); ans = 0; dinic.init(n*m+3); S = n*m+1, T = n*m+2; for (int i = 1; i <= n; i++) { char x; for (int j = 1; j <= m; j++) scanf(" %c", &x), g[i][j] = x=='#' ? 1:0; } int dx[] = {1, 0, 0, -1}, dy[] = {0, 1, -1, 0}; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (i == 1 || j == 1 || i == n || j == m) { if (!g[i][j]) ans += fil, g[i][j] = 1; 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 = 0; k < 4; k++) { int Fx = i+dx[k], Fy = j+dy[k]; if (Fx < 1 || Fx > n || Fy < 1 || Fy > m) continue; dinic.add_edge(id(i, j), id(Fx, Fy), bui); } } ans += dinic.Maxflow(S, T); printf("%d ", ans); } return 0; }
模板题：CodeVS 1993 草地排水
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int maxn=100000+10; const int INF=2147000000; 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,-1,sizeof(head)); sz=-1; //注意 方便亦或找反向边 } 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]=0; ++sz; to[sz]=a, Next[sz]=head[b];head[b]=sz; cap[sz]=c, flow[sz]=c; //正向的增加，反向的减少 }//加双向边 bool BFS() { memset(vis,0,sizeof(vis)); queue<int>Q; vis[s]=1; d[s]=0; Q.push(s); while(!Q.empty()){ int u=Q.front();Q.pop(); for(int i=head[u];i!=-1;i=Next[i]){ int v=to[i]; if(!vis[v]&&cap[i]>flow[i]){ vis[v]=1; d[v]=d[u]+1; Q.push(v); } } } return vis[t]; }//求深度 int DFS(int x,int a){ if(x==t||a==0)return a;//当前增广路上的最小残量 int Flow=0,f; for(int& i=cur[x];i!=-1;i=Next[i]){ int v=to[i]; if(d[v]==d[x]+1&&(f=DFS(v,min(a,cap[i]-flow[i])))>0){ Flow+=f; flow[i]+=f; flow[i^1]-=f;// a-=f; if(a==0)break; } } return Flow; }//增广路 int Maxflow(int ss,int tt) { s=ss, t=tt; int Flow=0; while(BFS()) { for(int i=0;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 = 1; i <= m; i++){ scanf("%d%d%d", &a, &b, &c); dinic.add_edge(a, b, c); } int ans = dinic.Maxflow(1, n); cout<<ans<<endl; return 0; }
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 = 10000+10; const int maxm = 2*100000+10; 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, -1); sz=-1; //注意 方便亦或找反向边 } 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]=0; ++sz; to[sz]=a, Next[sz]=head[b];head[b]=sz; cap[sz]=c, flow[sz]=c; //正向的增加，反向的减少 }//加双向边 bool BFS() { memset(vis,0,sizeof(vis)); queue<int>Q; vis[s]=1; d[s]=0; Q.push(s); while(!Q.empty()) { int u=Q.front(); Q.pop(); for(int i = head[u]; i != -1; i = Next[i]) { int v = to[i]; if(!vis[v] && cap[i] > flow[i]) { vis[v]=1; d[v]=d[u]+1; Q.push(v); } } } return vis[t]; }//求深度 int DFS(int x,int a){ if(x==t||a==0)return a;//当前增广路上的最小残量 int Flow=0,f; for(int& i=cur[x];i!=-1;i=Next[i]){ int v=to[i]; if(d[v]==d[x]+1&&(f=DFS(v,min(a,cap[i]-flow[i])))>0){ Flow+=f; flow[i]+=f; flow[i^1]-=f;// a-=f; if(a==0)break; } } return Flow; }//增广路 int Maxflow(int ss,int tt) { s=ss, t=tt; int Flow=0; while(BFS()) { for(int i=0;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 = 0; 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 = 0, mms(last, 0); } int relax(int x, int y, int tmp) { if (dis[x]+1 < dis[y]) { dis[y] = dis[x] + 1; return 1; } return 0; } void SPFA(int k) { queue<int> q; mms(dis, INF), mms(vis, 0); q.push(k), dis[k] = 0, vis[k] = 1; 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] = 1; } vis[x] = 0; } } int n,m; int main() { int t; scanf("%d", &t); for (int ca = 1; ca <= t; ca++) { init(); scanf("%d%d",&m,&n); dinic.init(n, m); int a, b, c; for(int i = 1; i <= m; i++) { scanf("%d%d%d", &a, &b, &c); build(a, b, c); build(b, a, c); } SPFA(1); for (int i = 1; i <= tot; i+=2) { int x = u[i], y = v[i], c = l[i]; if (dis[y]-dis[x] == 1) dinic.add_edge(x, y, c); else if (dis[x]-dis[y] == 1) dinic.add_edge(y, x, c); } int ans = dinic.Maxflow(1, n); printf("%d ", ans); } return 0; }