【算法】网络流-最大流(dinic)

【题解】http://www.cnblogs.com/onioncyc/p/6496532.html

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=210,inf=0x3f3f3f3f;struct edge{
    int from,v,flow;}e[maxn*3];int n,m,tot=2,S,T,d[maxn],q[510],first[maxn],cur[maxn];void insert(int u,int v,int flow){tot++;e[tot].v=v;e[tot].flow=flow;e[tot].from=first[u];first[u]=tot;}bool bfs(){    memset(d,-1,sizeof(d));    int head=0,tail=1;q[head]=S;    d[S]=0;    while(head!=tail)     {         int x=q[head++];if(head>=501)head=0;         for(int i=first[x];i;i=e[i].from)         if(d[e[i].v]==-1&&e[i].flow>0)          {              q[tail++]=e[i].v;d[e[i].v]=d[x]+1;              if(tail>=501)tail=0;          }     }    if(d[T]==-1)return 0;else return 1;}int dfs(int x,int a){    if(x==T||a==0)return a;    int flow=0,f;    for(int& i=cur[x];i;i=e[i].from)//当前弧优化      if(d[e[i].v]==d[x]+1&&(f=dfs(e[i].v,min(a,e[i].flow)))>0)      {          e[i].flow-=f;          e[i^1].flow+=f;          flow+=f;          a-=f;          if(a==0)break;      }    return flow;}int main(){    scanf("%d%d",&m,&n);    S=1;T=n;    for(int i=1;i<=m;i++)     {         int u,v,w;         scanf("%d%d%d",&u,&v,&w);         insert(u,v,w);         insert(v,u,0);     }    int ans=0;    while(bfs())     {         for(int i=1;i<=n;i++)cur[i]=first[i];         ans+=dfs(S,inf);     }    printf("%d",ans);    return 0;}