POJ 1273 Drainage Ditches(最大流Dinic 模板)

时间:2022-11-29 20:41:08
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m, S, T;
const int MAXN = ;//点数的最大值
const int MAXM = ;//边数的最大值
const int INF = 0x3f3f3f3f;
struct Edge
{
int to,next,cap,flow; } edge[MAXM]; //注意是MAXM
int tol;
int head[MAXN];
void init()
{
tol = ;
memset(head,-,sizeof(head));
}
void addedge(int u,int v,int w,int rw = )
{
edge[tol].to = v;
edge[tol].cap = w;
edge[tol].flow = ;
edge[tol].next = head[u];
head[u] = tol++;
edge[tol].to = u;
edge[tol].cap = rw;
edge[tol].flow = ;
edge[tol].next = head[v];
head[v] = tol++;
}
int Q[MAXN];
int dep[MAXN],cur[MAXN],sta[MAXN];
bool bfs(int s,int t,int n)
{
int front = ,tail = ;
memset(dep,-,sizeof(dep[])*(n+));
dep[s] = ;
Q[tail++] = s;
while(front < tail)
{
int u = Q[front++];
for(int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].to;
if(edge[i].cap > edge[i].flow && dep[v] == -)
{
dep[v] = dep[u] + ;
if(v == t)
return true;
Q[tail++] = v;
}
}
}
return false;
}
int dinic(int s,int t,int n)
{
int maxflow = ;
while(bfs(s,t,n))
{
for(int i = ; i < n; i++)
cur[i] = head[i];
int u = s, tail = ;
while(cur[s] != -)
{
if(u == t)
{
int tp = INF;
for(int i = tail-; i >= ; i--)
tp = min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
maxflow += tp;
for(int i = tail-; i >= ; i--)
{
edge[sta[i]].flow += tp;
edge[sta[i]^].flow -= tp;
if(edge[sta[i]].cap-edge[sta[i]].flow == )
tail = i;
} u = edge[sta[tail]^].to;
}
else if(cur[u] != - && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + == dep[edge[cur[u]].to])
{
sta[tail++] = cur[u];
u = edge[cur[u]].to;
}
else
{
while(u != s && cur[u] == -)
u = edge[sta[--tail]^].to;
cur[u] = edge[cur[u]].next;
}
}
}
return maxflow;
}
int main()
{
while(~scanf("%d %d", &m, &n))
{
init();
for(int i = ; i < m; i++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
addedge(u,v, w);
}
printf("%d\n", dinic(, n, n));
}
return ;
}