关于权值为double的网络流(dinic
  • 板块学术版
  • 楼主Leap_Frog
  • 当前回复27
  • 已保存回复27
  • 发布时间2020/9/23 21:38
  • 上次更新2023/11/5 12:43:21
查看原帖
关于权值为double的网络流(dinic
44805
Leap_Frog楼主2020/9/23 21:38
  1. 有什么好一点的模板题吗,想试试看我的模板是不是对的。
  2. 下面这份板子有什么问题吗?好像T了,而出题人说数据是随机的。
inline void ADDE(int x,int y,double w) {e[++et]=(edge){y,w,head[x]},head[x]=et;}
inline void adde(int x,int y,double w) {ADDE(x,y,w),ADDE(y,x,0);}
inline char bfs(int s,int t)
{
	queue<int>q;memset(d,-1,sizeof(d)),d[s]=1,q.push(s);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=head[x];i;i=e[i].nxt) if(e[i].w>0&&d[e[i].to]==-1) q.push(e[i].to),d[e[i].to]=d[x]+1;
	}
	return d[t]!=-1;
}
#define rev(x) ((((x)&1)?1:-1)+(x))
inline double dfs(int x,int t,double lim=INF)
{
	double g=lim;if(x==t) return lim;
	for(int i=cur[x];i;cur[x]=i=e[i].nxt) if(e[i].w>0&&d[e[i].to]==d[x]+1)
	{
		double f=dfs(e[i].to,t,min(e[i].w,g));
		e[i].w-=f,e[rev(i)].w+=f,g-=f;if(g<dx) break;
	}
	return lim-g;
}
#undef rev
inline double dinic(int s,int t)
{
	double r=0;
	while(bfs(s,t)) {memcpy(cur,head,sizeof(cur)),r+=dfs(s,t);if(r>=INF) return r;}
	return r;
}
2020/9/23 21:38
加载中...