题目：
最小割裸题。
那个限制就是在 i、j 之间连双向边。
根据本题能引出网络流中二元关系的种种。
别忘了写 if ( x==n+1 ) return flow ; ！
#include#include #include #include using namespace std;const int N=2e4+5,M=2e5+5,INF=0x3f3f3f3f;int n,m,hd[N],cr[N],xnt=1,mxflow,dfn[N];int num;struct Ed{ int nxt,to,cap; Ed(int n=0,int t=0,int c=0):nxt(n),to(t),cap(c) {}}ed[(N+M)<<2];void add(int x,int y,int z){ ed[++xnt]=Ed(hd[x],y,z);hd[x]=xnt; ed[++xnt]=Ed(hd[y],x,0);hd[y]=xnt;}bool bfs(){ memset(dfn,0,sizeof dfn); dfn[0]=1;queue q;q.push(0); while(q.size()) { int k=q.front();q.pop(); for(int i=hd[k],v;i;i=ed[i].nxt) if(!dfn[v=ed[i].to]&&ed[i].cap) { dfn[v]=dfn[k]+1;q.push(v); if(v==n+1)return true; } } return false;}int dinic(int x,int flow){ if(x==n+1)return flow;//!!! int use=0; for(int &i=cr[x],v;i;i=ed[i].nxt) if(dfn[v=ed[i].to]==dfn[x]+1&&ed[i].cap) { int tmp=dinic(v,min(ed[i].cap,flow-use)); if(!tmp)dfn[v]=0; ed[i].cap-=tmp;ed[i^1].cap+=tmp;use+=tmp; if(use==flow)return flow; } return use;}int main(){ scanf("%d%d",&n,&m);int x,y,z; for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); add(0,i,x);add(i,n+1,y); } for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } while(bfs()) { memcpy(cr,hd,sizeof hd); int k=dinic(0,INF); mxflow+=k; } printf("%d",mxflow); return 0;}