容…题意

容量设为1的原因更多是反映这条路有没有流到达汇点不需要在乎数量

while(m--)

cinuvw;add(u,v,w);add(v,u,0);add(v,u,w);add(u,v,0);

考虑将一个点

INF0x3fffffffffffffff,mod998244353;int

ceil(int

to,next,cap;way()default;way(int

to,int

{this-toto;this-nextnext;this-capcap;}

}edge[M2];

{edge[cnt]way(v,head[u],cap);head[u]cnt;

}int

dis[i]inf;queueintq;q.push(s);dis[s]0;now[s]head[s];while(!q.empty())

{int

[v,_,cap]edge[i];if(dis[v]infcap)

now[v]head[v];if(vt)

inow[u];(now[u]i);iedge[i].next)

{auto

[v,_,cap]edge[i];if(cap0||dis[v]!dis[u]1)

continue;int

nflowdfs(v,min(flow,cap));if(nflow0)

dis[v]inf;else

{edge[i].cap-nflow;edge[i^1].capnflow;retnflow;flow-nflow;}}return

ret;

stdjudgefreopen(in.txt,r,stdin);auto

TimeFlagFirstclock();#endifstd::ios::sync_with_stdio(false);std::cin.tie(nullptr);cinnmst;for(int

i1;in;i)

cap(is||it)?inf:1;add(i,in,cap);add(in,i,0);}while(m--)

{int

u,v;cinuv;add(un,v,1);add(v,un,0);add(vn,u,1);add(u,vn,0);}tn;n1;int

ans0;while(bfs())

ansdfs(s,inf);coutansendl;#ifdef

stdjudgefreopen(CON,r,stdin);std::coutstd::endl耗时:std::clock()-TimeFlagFirstmsstd::endl;std::coutstd::flush;system(pause);#endifreturn