以前最大流我都是写sap啊。dinic啊之类的复杂算法。。感觉很不爽。。但是暴力dfs又经常超时，而EK算法反而更难写。。于是我很纠结。。
今天我看到了一种很帅的算法。。就是每次只增广容量在K以上的增广路，找不到了将k除2。。
代码很简单，时间我测了一下在稀疏图上是sap的3倍左右。。
哎。。花了4000买了台HTC HD2。。再是山寨的我只能撞死了晕。。
我无聊又进行了一些测试，发现在边权比较参差不齐的时候效果还是很好的，但在单位边图上就退化成暴力dfs了囧。。但可以加个高度函数优化，速度就几乎跟SAP一样了。。不过没意义。。
Code：
#include<iostream>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
int n,m;
const int V=5000;
struct Edge
{
int t,c;
Edge*next,*op;
Edge(int _t,int _c,Edge*_n):t(_t),c(_c),next(_n){}
}*E[V]={0};
int vs,vt,v;
void AddEdge(int s,int t,int c)
{
E[s]=new Edge(t,c,E[s]);
E[t]=new Edge(s,c,E[t]);
E[s]->op=E[t];E[t]->op=E[s];
}
int k=0;
bool vis[V]={0};
bool dfs(int no)
{
if(no==vt)return true;
vis[no]=true;
for(Edge*e=E[no];e;e=e->next)if(!vis[e->t]&&e->c>=k&&dfs(e->t))
{
e->c-=k;e->op->c+=k;return true;
}
return false;
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m;v=n;int s,t,c;
vs=0;vt=n-1;
while(m–)
{
cin>>s>>t>>c;–s;–t;
AddEdge(s,t,c);
k=c>k?c:k;
}
long long ans=0;
while(k)
{
while(memset(vis,0,sizeof(vis)),dfs(vs))ans+=k;
k>>=1;
}
cout<<ans<<endl;
}