附上注释代码
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; /*const&int*/ const int maxline=201; const int maxnode=201; int n,m; int ans; /*lsqqx*/ struct nn { int to; int nxt; int value; }edge[maxline*2+1];//建立双向边，一个前向弧一个后向弧 int cnt;int head[maxnode]; #define forline(i,x) for(int i=head[x];i!=-1;i=edge[i].nxt) /*wll*/ int ceng[maxnode];//分层图 /*bfs*/ queue<int> team;//BFS队列 /*---cut---*/ void addEdge(int x,int y,int val) { //从0开始链式前向星,便于i^1（后向弧操作） edge[cnt].nxt=head[x]; edge[cnt].to=y; edge[cnt].value=val; head[x]=cnt; ++cnt; } bool BFS()//BFS分层图，寻找汇点，找不到为止 { for(int i=0;i<=n;++i) { ceng[i]=-1; } ceng[1]=0; team.push(1); int headx; while(!team.empty()) { headx=team.front(); team.pop(); forline(i,headx) { int will=edge[i].to; if(ceng[will]==-1&&edge[i].value>0) //（并未更新层数&&网络流性质0流量不算边） { //入队操作 ceng[will]=ceng[headx]+1; team.push(will); } } } if(ceng[n]==-1) return 0; return 1; } int zengguang(int nownode,int wave)//(现在节点，最大流量) { if(nownode==n)//探测到汇点 { return wave; } int tt; forline(i,nownode) { int will=edge[i].to; if(ceng[will]==ceng[nownode]+1)//不走回头路 { tt=zengguang(will,min(wave,edge[i].value));//前方有路 if(tt) { edge[i].value-=tt; edge[i^1].value+=tt;//后向弧 return tt; } } } return 0; } int main() { freopen("cy.in","r",stdin); freopen("cy.out","w",stdout); scanf("%d%d",&m,&n); int x,y,value; memset(head,-1,sizeof(head));//由于cnt从零开始，所以-1 for(int i=1;i<=m;++i) { scanf("%d%d%d",&x,&y,&value); addEdge(x,y,value); addEdge(y,x,0);//后向弧 } ans=0; int tmp=0; while(BFS())//BFS分层图，寻找汇点 { tmp=zengguang(1,99999);//进行增广操作 while(tmp) { ans+=tmp; tmp=zengguang(1,99999);//要不断寻找增广，直到无法增广为止 } } printf("%d\n",ans); return 0; }