- 有什么好一点的模板题吗,想试试看我的模板是不是对的。
- 下面这份板子有什么问题吗?好像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;
}