网络流一直没学，来学一波网络流。
https://vjudge.net/problem/POJ-1273
题意：给定点数，边数，源点，汇点，每条边容量，求最大流。
解法：EK或dinic。
EK：每次增广用bfs选择一条从源到汇具有最少边数的增广路径，然后找出该路径容量最小的边，就是此次增加的流量，然后沿该路径增加反向边，同时修改每条边的容量，重复上述过程直到找不到增广路（即minFlow = 0)为止。
dinic: 每次bfs从源点到汇点分层（层数是源点到它最少要经过的边数），然后dfs从源点开始不断向下一层找增广路，碰到汇点说明找到一条，进行增广。然后回溯到点u（u是满足（u,v)容量为0的最上层节点）继续寻找增广路，如果回溯到源点且无法继续往下走dfs结束，然后对残余网络再分层，再dfs直到无法分层，算法结束。
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int G[][];
int pre[]; //前驱
bool vis[];
int n,m; //1是源，m是汇 inline int solve(){
deque<int> q;
memset(pre,,sizeof pre);
memset(vis,,sizeof vis);
pre[] = ;
vis[] = ;
q.push_back();
bool find = false;
while(!q.empty()){
int v = q.front();
q.pop_front();
for(int i=;i<=m;i++){
if(G[v][i]>&&vis[i]==){
pre[i] = v;
vis[i] = ;
if(i==m){
find = true;
q.clear();
break;
}
else q.push_back(i);
}
}
}
if(!find) return ;
int minFlow = 0x3f3f3f3f;
int v = m;
while(pre[v]){
minFlow = min(minFlow,G[pre[v]][v]);
v = pre[v];
}
v = m;
while(pre[v]){
G[pre[v]][v] -= minFlow;
G[v][pre[v]] += minFlow;
v = pre[v];
}
return minFlow;
} int main(){
while(cin>>n>>m){
memset(G,,sizeof G);
for(int i=;i<n;i++){
int s,e,c;
cin>>s>>e>>c;
G[s][e] += c;
}
int maxFlow = ;
int aug;
while(aug=solve())
maxFlow += aug;
cout<<maxFlow<<endl;
}
return ;
}
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
int G[][];
bool vis[];
int Layer[];
int n,m; //1是源点，m是汇点 inline bool countLayer(){
int layer = ;
deque<int> q;
memset(Layer,0xff,sizeof Layer);
Layer[] = ;
q.push_back();
while(!q.empty()){
int v = q.front();
q.pop_front();
for(int j=;j<=m;j++){
if(G[v][j]>&&Layer[j]==-){
Layer[j] = Layer[v]+;
if(j==m) return true;
else q.push_back(j);
}
}
}
return false;
} inline int dinic(){
int maxFlow = ;
deque<int> q;
while(countLayer()){
q.push_back();
memset(vis,,sizeof vis);
vis[] = ;
while(!q.empty()){
int nd = q.back();
if(nd==m){
int minc = inf;
int minc_vs;
for(int i=;i<q.size();i++){
int vs = q[i-];
int ve = q[i];
if(G[vs][ve]>){
if(minc>G[vs][ve]){
minc = G[vs][ve];
minc_vs = vs;
}
}
}
maxFlow += minc;
for(int i=;i<q.size();i++){
int vs = q[i-];
int ve = q[i];
G[vs][ve] -= minc;
G[ve][vs] += minc;
}
while(!q.empty()&&q.back()!=minc_vs){
vis[q.back()] = ;
q.pop_back();
}
}
else {
int i;
for(i=;i<=m;i++){
if(G[nd][i]>&&Layer[i]==Layer[nd]+&&!vis[i]){
vis[i] = ;
q.push_back(i);
break;
}
}
if(i>m) q.pop_back();
}
}
}
return maxFlow;
} int main(){
while(cin>>n>>m){
memset(G,,sizeof G);
for(int i=;i<n;i++){
int s,e,c;
cin>>s>>e>>c;
G[s][e] += c;
}
cout<<dinic()<<endl;
}
return ;
}