本文共 1612 字，大约阅读时间需要 5 分钟。
ISAP好长啊。。。居然打了20分钟。。。。
#include #include #include #include #include #include #include #include using namespace std;#include #include #include #include #include #include #include ;#define cler(arr, val) memset(arr, val, sizeof(arr))#define FOR(i,a,b) for(int i=a;i<=b;i++)#define IN freopen ("in.txt" , "r" , stdin);#define OUT freopen ("out.txt" , "w" , stdout);typedef long long LL;const int MAXN = 10010;const int MAXM = 44224;const int INF = 0x3f3f3f3f;const int mod = 1000000007;struct Edge{ int to,next,cap,flow;}edge[MAXM];int tol,head[MAXN];int gap[MAXN],dep[MAXN],cur[MAXN];void init(){ tol=0; cler(head,-1);}void addedge(int u,int v,int w,int rw=0){ edge[tol].to=v,edge[tol].cap=w,edge[tol].flow=0,edge[tol].next=head[u]; head[u]=tol++; edge[tol].to=u,edge[tol].cap=rw,edge[tol].flow=0,edge[tol].next=head[v]; head[v]=tol++;}int Q[MAXN];void BFS(int star,int end){ cler(dep,-1); cler(gap,0); gap[0]=-1; int front= 0, rear = 0; dep[end]=0; Q[rear++] = end; while(front!= rear) { int u=Q[front++]; for(int i = head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(dep[v]!= -1) continue; Q[rear++]= v; dep[v]=dep[u]+1; gap[dep[v]]++; } }}int S[MAXN];int sap(int star,int end,int N){ BFS(star,end); memcpy(cur,head,sizeof(head)); int top=0, u=star,ans=0; while(dep[star] edge[S[i]].cap-edge[S[i]].flow) { Min=edge[S[i]].cap-edge[S[i]].flow; inser=i; } for(int i=0;i 0) addedge(star,i,low[i]),sum+=low[i]; else addedge(i,end,-low[i]); } // cout< <<" "< <
转载于:https://www.cnblogs.com/kewowlo/p/4088338.html