dinic(链表)

算法：最小割
每个点当做一个任务，从源连一个在A上代价为容量的边，从汇再连一个B上代价为容量的边
如果x,y分开会产生代价，则他们间连一个双向的边，容量为代价
最大流就可以了

有些人，包括曾经的我，都是用Dinic加无数恶心优化过的（我7xxxMs)
曾经考虑找增广路时是否必须多路增广，但是由于听信了某神牛
“多头增广和单头的效果是一样的，我试验过”的指点，所以放弃了。

今天，我试了一下多路增广，发现...3xxxMsAC！

贡献一个29行的Dinic，供大家交流！

int level[Nmax],queue[Nmax];
int MakeLevel(){
    int bot,x;
    memset(level,0xff,sizeof(level));
    level[queue[0]]=0;bot=1;
    for (int top=0;top        for (edge *p=es[x];p;p=p->next)if (p->c && level[p->e]==-1)
			level[queue[bot++]=p->e]=level[x]+1;
    }
    return level[N-1]!=-1;
}
int FindPath(int u,int alpha){
    if (u==N-1)return alpha;
    int t,w;
	w=0;
	for (edge *p=es[u];p && wnext)
            if (p->c>0 && level[p->e]==level[u]+1)if (t=FindPath(p->e,Min(p->c,alpha-w))){
            p->c-=t;
            if (p->opt)p->opt->c+=t;
			w+=t;//多路增广优势巨大
        }
	if (!w)level[u]=-1;//关键的一句话
	return w;
}
void Dinic(){
    int t;
    while (MakeLevel())while (t=FindPath(0,1100000000))res+=t;
}

其中，用到的边用链表存储
struct edge{
int e,//指向的节点
c;//剩余可增广的流量
edge *next,//下一个节点
*opt;//反向边
};
答案保存在全局变量res中，源点使用S，汇点使用N-1