赛前赛后算是第三次接触Dinic算法了，每一次接触都能有种很好的感觉，直男的我没法描述~~
已经比较懂得DInic的基本算法思想了
首先是bfs进行进行分层处理，然后dfs寻找分层后的最大流，在这其中做好正向边流量和反向边流量的优化处理
bfs依旧是比较的简单，维护flor的数组
dfs依旧是Dinic的精华
int dfs(int s,int t,int value)
{
int ret = value;
if(s == t || value == )return value; int a; for(int &i = cur[s];~i;i = e[i].pre)
{
int to = e[i].to;
int cost = e[i].cost;
if(flor[to] == flor[s] + && (a = dfs(to,t,min(ret,e[i].cost))))
{
e[i].cost -= a;
e[i ^ ].cost += a;
ret -= a;
if(ret == )break;
}
} if(ret == value)flor[s] = ;
return value - ret;
}
从s到t，value为其路径上的最大流量值
然后访问分层后的边（仅仅访问一次）往下继续留，递归回来的时候进行正向边和反向边的流量优化
最最后面删点，删去此次分层后被截流的点然后根据优化后的网络流继续分层，直到分层结束。、、
/*
Dinic算法求取最小费用最大流问题
必要的概念：
前向弧：方向与链正方向一致的弧——p+
后向弧：方向与链反方向一致的弧——p-
增广路：也称为可改进路径，对于一条可行流，存在p
满足p的所有前向弧都是非饱和的，
p的所有后向弧都是非零流弧
割：去除摸一个点后使基图不在连通，
也就是将原来的两个点集划分为两个子集S和T
s-t割：分割后的两个子集，远点s属于S，汇点t属于T
s-t割后的弧u-v，u属于sv属于t的为前向弧，反之为后向弧
割的容量：前向弧的容量和
最小割：使容量最小的割
*/
/*
最大流
也就是寻找增广路
1.现在是零流
2.（当前情况下）寻找一条路，从s到t，并且每一段的流量都小于容量（并不是小于等于！！流量代表的是当前的流量，如果想等就不再可行）
3.那么找到这条路上的min（容量 – 流量），然后每一段的流量都加上delta（这就叫增广路）
4.重复步骤二，知道找不到增广路
以上为基础算法思想
*/
/*
逐步的优化
反向边：为了求出最大流
反向边的出现给了流浪一个反向的几回，虽然有重复的部分但是能确保反向增广后，可以得到两条独一无二的链！
在说的明白一点反向的可行性是建立在可以退流的基础上，像二分图匹配似的
*/
/*
Dinic算法
1》初始化容量网络和网络流
2》构造残留网络和层次网络，若汇点不在层次网络之中结束
3》对层次网络进行DFS，进行增广
4》重复步骤二
*/
#include <iostream>
#include <cstdio>
#include <string.h>
#include <queue>
#define inf 0xffffff
using namespace std;
const int maxn = 220;
const int maxm = 4e4 + 4e2;
int n,m;
struct node{
int pre;
int to,cost;
}e[maxm];
int id[maxn],cnt;
int flor[maxn];
void init()
{
memset(id,-1,sizeof(id));
cnt = 0;
}
int cur[maxn];//DFS的优化遍历
void add(int from,int to,int cost)
{
e[cnt].to = to;
e[cnt].cost = cost;
e[cnt].pre = id[from];
id[from] = cnt++;
swap(from,to);
e[cnt].to = to;
e[cnt].cost = 0;
e[cnt].pre = id[from];
id[from] = cnt++;
//可以用异或去取他的反向边
//偶数为正向，奇数为反向
}
int bfs(int s,int t)
{
memset(flor,0,sizeof(flor));
queue<int>q;
while(q.size())q.pop();
flor[s] = 1;//flor还充当vis数组，所以从1层开始分层
q.push(s);
while(q.size())
{
int now = q.front();q.pop();
for(int i = id[now];~i;i = e[i].pre)
{
int to = e[i].to;
int cost = e[i].cost;
if(flor[to] == 0 && cost > 0)
{
flor[to] = flor[now] + 1;
q.push(to);
if(to == t)return 1;
}
}
}
return 0;
}
int dfs(int s,int t,int value)
{
int ret = value;
if(s == t || value == 0)return value;
int a;
for(int &i = cur[s];~i;i = e[i].pre)
{
int to = e[i].to;
int cost = e[i].cost;
if(flor[to] == flor[s] + 1 && (a = dfs(to,t,min(ret,e[i].cost))))
{
e[i].cost -= a;
e[i ^ 1].cost += a;
ret -= a;
if(ret == 0)break;
}
}
if(ret == value)flor[s] = 0;
return value – ret;
}
int Dinic(int s,int t)
{
int ret = 0;
while(bfs(s,t))
{
memcpy(cur,id,sizeof(id));
// for(int i = 0;i < n;i++)
// {
// cur[i] = id[i];
// }
ret += dfs(s,t,inf);
//cout<<“cs”<<endl;
}
return ret;
}
int main()
{
/*
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
*/
while(~scanf(“%d%d”,&m,&n))
{
init();
int a,b,x;
for(int i = 1;i <= m;i++)
{
scanf(“%d%d%d”,&a,&b,&x);
add(a,b,x);
}
int ret = Dinic(1,n);
printf(“%d\n”,ret);
}
return 0;
}
/*不知道什么时候的事了，博客园的代码插入位置咋不能在光标之后了，一开始就是因为CSDN的不好编辑才用的博客园哎~~*/
