Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:雁过留声——最大费用流

Posted by wx5391805 at 2011-07-01 00:53:31 on Problem 3422
In Reply To:雁过留声——最大费用流 Posted by:fanhqme at 2009-11-29 19:50:08
> 像这种“传纸条”类的经典题目,基本上已经有成熟的算法了:
> 1.DP
> 2.费用流
> 
> DP解法主要是对付K<=2的(我目前只知道一个复杂度为O(N^(K+1))的DP,若有大牛
> 有好解法,欢迎讨论)
> 于是,召唤出费用流。
> 建图:为方便,每个格子掰成两个点,分别叫“出点”,“入点”,
> 入点到出点间连一个容量1,费用为格子中数的边,以及一个容量∞,费用0的边。
> 同时,一个格子的“出点”向它右、下的格子的“入点”连边,容量∞,费用0。
> 
> 源点向(0,0)的入点连一个容量K的边,(N-1,N-1)的出点向汇点连一个边。
> 当然,也可以用替代做法:限定只增广K次。
> 
> 费用流的代码:
> 
> struct edge{
> 	int e,c,f;
> 	edge *next,*opt;
> };
> int BellmanFord(int S,int T){
> 	int top,bot,x,ret;
> 	for (int i=0;i<NN;i++)dis[i]=-1,inQ[i]=0;
> 	inQ[queue[top=0]=S]=1;bot=1;
> 	dis[S]=0;pre[S]=-1;prep[S]=NULL;
> 	while (top!=bot){x=queue[top++];if (top>=((NMax*NMax)<<1)+1)top=0;
> 		inQ[x]=0;
> 		for (edge *p=E[x];p;p=p->next)
> 			if (p->f && dis[p->e]<dis[x]+p->c){
> 				dis[p->e]=dis[x]+p->c;
> 				pre[p->e]=x;prep[p->e]=p;
> 				if (!inQ[p->e]){
> 					inQ[queue[bot++]=p->e]=1;
> 					if (bot>=((NMax*NMax)<<1)+1)bot=0;
> 				}
> 			}
> 	}
> 	if (dis[T]==-1)return 0;
> 	x=T;ret=0;
> 	while (x!=S){
> 		ret+=prep[x]->c;prep[x]->f--;prep[x]->opt->f++;
> 		x=pre[x];
> 	}
> 	return ret;
> }
> int MaxKFlow(int S,int T,int k){
> 	int ret;
> 	ret=0;
> 	while (k--)ret+=BellmanFord(S,T);
> 	return ret;
> }
"以及一个容量∞,费用0的边"这是为什么??还有你不在从出点向入点做一条负该数的边吗?

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator