算法：最小割
每个点当做一个任务，从源连一个在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<bot;top++){x=queue[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 && w<alpha;p=p->next)
            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

• Re:雁过留声——Dinic的细节 (69) chenyuanqin 2010-08-20 21:25:13
  • Re:雁过留声——Dinic的细节 (19) bbbbbbbbba 2011-02-15 22:16:10
• 谢谢你的优化~~~~ (0) DE_SEAN 2011-05-13 10:19:51
• Re:雁过留声——Dinic的细节 (54) mjzshd 2011-09-08 16:25:41
• Re:雁过留声——Dinic的细节 (8) ofenTLE 2011-12-28 22:01:12
• Re:雁过留声——Dinic的细节 (17) yc5_yc 2012-05-02 20:54:22
• Re:雁过留声——Dinic的细节 (5) 331895686 2012-08-03 15:38:31
• "多路增广"和"当前弧优化"本质上在做同样的事吧？ (131) NtNlyCoder 2015-10-27 16:37:31