各种姿势鲁了一遍，这种姿势绝对是最适合写网络流的
邻接表的写法支持重边，支持稀疏图，易于查找反向边，添加一个标记即可删边，又没有vector的繁琐
这里傻呼呼的用容量和流量两个东西，而不是用残量，本人觉得前者更容易理解且调试得多，也并没有多开什么内存*_*
#include#include #include #include #include using namespace std;const int maxn=208;const int INF=0x7f7f7f7f;struct fuck{ int u,v,flow,cap,next;}edge[maxn<<1];int n,m;int dis[maxn],pre[maxn];bool vis[maxn];int head[maxn<<1];int tol=0;void init(){ tol=0; memset(head,-1,sizeof(head));}void addedge(int u,int v,int w){ edge[tol].u=u; edge[tol].v=v; edge[tol].cap=w; edge[tol].flow=0; edge[tol].next=head[u]; head[u]=tol++; edge[tol].u=v; edge[tol].v=u; edge[tol].cap=0; edge[tol].flow=0; edge[tol].next=head[v]; head[v]=tol++;}int bfs(){ queue q; memset(vis,false,sizeof(vis)); int u,v,i; q.push(1);dis[1]=INF;pre[1]=-1;vis[1]=true; while(!q.empty()) { u=q.front();q.pop(); if(u==n) break; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(!vis[v]&&edge[i].cap>edge[i].flow) { dis[v]=min(dis[u],edge[i].cap-edge[i].flow); vis[v]=true; q.push(v); pre[v]=i; } } } if(!vis[n]) return -1; return dis[n];}int ek(){ memset(dis,INF,sizeof(dis)); int max_flow=0,u,v,fl; while(1) { fl=bfs(); if(fl==-1) break; u=n; while(u!=1) { edge[pre[u]].flow+=fl; edge[pre[u]^1].flow-=fl; u=edge[pre[u]].u; } max_flow+=fl; } return max_flow;}int main(){ int i,j,u,v,w; while(scanf("%d%d",&m,&n)==2) { init(); for(i=0;i