ISAP求最大流模板
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> using namespace std; const int maxn=100010; const int inf=1e9; struct node { int from,to,next; int cap; }edge[maxn*4]; int tol; int head[maxn]; int dep[maxn]; int gap[maxn];//gep[x]=y说明残量网络中dep[i]==x的个数为y int n;//点的个数 void init() { tol=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w) { edge[tol].from=u; edge[tol].to=v; edge[tol].cap=w; edge[tol].next=head[u]; head[u]=tol++; } void bfs (int st,int ed) { memset (dep,-1,sizeof(dep)); memset (gap,0,sizeof(gap)); gap[0]=1; queue<int> q; dep[ed]=0; q.push(ed); while (!q.empty()) { int u=q.front(); q.pop(); for (int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if (dep[v]!=-1) continue; q.push(v); dep[v]=dep[u]+1; gap[dep[v]]++; } } } int sap (int st,int ed) { int res=0; bfs (st,ed); int cur[maxn]; int s[maxn]; int top=0; memcpy (cur,head,sizeof(head)); int u=st; int i; while (dep[st]<n) { if (u==ed) { int tmp=inf; int inser; for (i=0;i<top;i++) if (tmp>edge[s[i]].cap) { tmp=edge[s[i]].cap; inser=i; } for (i=0;i<top;i++) { edge[s[i]].cap-=tmp; edge[s[i]^1].cap+=tmp; } res+=tmp; top=inser; u=edge[s[top]].from; } if (u!=ed&&gap[dep[u]-1]==0) break; for (i=cur[u];i!=-1;i=edge[i].next) if (edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1) break; if (i!=-1) { cur[u]=i; s[top++]=i; u=edge[i].to; } else { int min=n; for (i=head[u];i!=-1;i=edge[i].next) { if (edge[i].cap==0) continue; if (min>dep[edge[i].to]) { min=dep[edge[i].to]; cur[u]=i; } } gap[dep[u]]--; dep[u]=min+1; gap[dep[u]]++; if (u!=st) u=edge[s[--top]].from; } } return res; } int main() { int start,end; int m; int u,v,z; int T; scanf("%d",&T); while(T--) { init(); scanf("%d%d",&n,&m); int Min=inf; int Max=-inf; int x,y; for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); if(Min>x) { Min=x; start=i; } if(Max<x) { Max=x; end=i; } } while(m--) { scanf("%d%d%d",&u,&v,&z); addedge(u,v,z); addedge(v,u,z); } //n一定是点的总数，这是使用SAP模板需要注意的 int ans=sap(start,end); printf("%d ",ans); } return 0; }