ISAP写法
#include <bits/stdc++.h> using namespace std; typedef long long LL; namespace FastIO { const static int MX=1e6; bool IOerror=0; char nc() { static char buf[MX],*p1=buf+MX,*pend=buf+MX; if(p1==pend) { p1=buf; pend=buf+fread(buf,1,MX,stdin); if(pend==p1) { IOerror=1; return -1; } } return *p1++; } inline bool blank(char ch) { return ch==' '||ch==' '||ch==' '||ch==' '; } inline int read(int& x) { char ch; while(blank(ch=nc())); if(IOerror) return 0; for(x=ch-'0'; (ch=nc())>='0'&&ch<='9'; x=x*10+ch-'0'); //printf("%d=== ",x); return 1; } inline int read(LL& x) { char ch; while(blank(ch=nc())); if(IOerror) return 0; for(x=ch-'0'; (ch=nc())>='0'&&ch<='9'; x=x*10+ch-'0'); //printf("%d=== ",x); return 1; } } using namespace FastIO; const int MAXN=210,MAXM=2020,MO=1024; const int INF = 0x3f3f3f3f; struct Edge { int to,next,cap,flow; Edge() {} Edge(int _to,int _next,int _cap,int _flow) { to=_to,next=_next,cap=_cap,flow=_flow; } } edge[MAXM]; //注意是MAXM int tol; int head[MAXN]; int gap[MAXN],d[MAXN],pre[MAXN],cur[MAXN]; void init() { tol = 0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w) { edge[tol]=Edge(v,head[u],w,0); head[u]=tol++; edge[tol]=Edge(u,head[v],0,0); head[v]=tol++; } int isap(int start,int end,int N) { memset(gap,0,sizeof(gap)); memset(d,0,sizeof(d)); memcpy(cur,head,sizeof(head)); int u = start; pre[u] = -1; gap[0] = N; int ans = 0; while(d[start] < N) { if(u == end) { int Min = INF; for(int i = pre[u]; i != -1; i = pre[edge[i^1].to]) if(Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow; for(int i = pre[u]; i != -1; i = pre[edge[i^1].to]) { edge[i].flow += Min; edge[i^1].flow -= Min; } u = start; ans += Min; continue; } bool flag = false; int v; for(int i = cur[u]; i != -1; i = edge[i].next) { v = edge[i].to; if(edge[i].cap - edge[i].flow && d[v]+1 == d[u]) { flag = true; cur[u] = pre[v] = i; break; } } if(flag) { u = v; continue; } int Min = N; for(int i = head[u]; i != -1; i = edge[i].next) if(edge[i].cap - edge[i].flow && d[edge[i].to] < Min) { Min = d[edge[i].to]; cur[u] = i; } gap[d[u]]--; if(!gap[d[u]])return ans; d[u] = Min+1; gap[d[u]]++; if(u != start) u = edge[pre[u]^1].to; } return ans; } int main() { int T; read(T); while (T--) { int n,m,s,t; read(n),read(m); read(s),read(t); init(); for(int i=1; i<=m; i++) { int x,y,z; read(x),read(y),read(z); addedge(x,y,z*MO+1); } int ans=isap(s,t,n); printf("%d ",ans%MO); } }
Dinic写法
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define LC(x) (x<<1) #define RC(x) ((x<<1)+1) #define MID(x,y) ((x+y)>>1) #define CLR(arr,val) memset(arr,val,sizeof(arr)) #define FAST_IO ios::sync_with_stdio(false);cin.tie(0); typedef pair<int,int> pii; //typedef long long LL; namespace FastIO { const static int MX=1e6; bool IOerror=0; char nc() { static char buf[MX],*p1=buf+MX,*pend=buf+MX; if(p1==pend) { p1=buf; pend=buf+fread(buf,1,MX,stdin); if(pend==p1) { IOerror=1; return -1; } } return *p1++; } inline bool blank(char ch) { return ch==' '||ch==' '||ch==' '||ch==' '; } inline int read(int& x) { char ch; while(blank(ch=nc())); if(IOerror) return 0; for(x=ch-'0'; (ch=nc())>='0'&&ch<='9'; x=x*10+ch-'0'); //printf("%d=== ",x); return 1; } } using namespace FastIO; const int N=210; const int M=2010; struct edge { int to,nxt; int cap; edge() {} edge(int _to,int _nxt,int _cap): to(_to),nxt(_nxt),cap(_cap) {} }; edge E[M << 1]; int head[N],tot,d[N]; void init() { CLR(head,-1); tot=0; } inline void add(int s,int t,int cap) { E[tot]=edge(t,head[s],cap); head[s]=tot++; E[tot]=edge(s,head[t],0); head[t]=tot++; } int bfs(int s,int t) { CLR(d,-1); d[s]=0; queue<int>Q; Q.push(s); while(!Q.empty()) { int u=Q.front(); Q.pop(); for(int i=head[u]; ~i; i=E[i].nxt) { int v=E[i].to; if(d[v]==-1 && E[i].cap > 0) { d[v]=d[u] + 1; if(v==t) return 1; Q.push(v); } } } return ~d[t]; } int dfs(int s,int t,int f) { if(s==t || !f) return f; int ret=0; for(int i=head[s]; ~i; i=E[i].nxt) { int v=E[i].to; if(d[v]==d[s] + 1 && E[i].cap > 0) { int df=dfs(v,t,min(f,E[i].cap)); if(df>0) { E[i].cap -=df; E[i ^ 1].cap +=df; ret +=df; f -=df; if(!f) break; } } } if(!ret) d[s]=-1; return ret; } int dinic(int s,int t) { int ret=0; while (bfs(s,t)) ret+=dfs(s,t,0x3f3f3f3f); return ret; } int main() { int T;read(T); while(T--) { init(); int n,m,s,t; read(n),read(m); read(s),read(t); while(m--) { int u,v,c; read(u),read(v),read(c); add(u,v,c*1024+1); } printf("%d ",dinic(s,t)%1024); } }
=========================================================================================
9.22更新
根据刘汝佳的板子，自己改编一下后如下（希望以后可以一直用
#include <bits/stdc++.h> using namespace std; typedef long long LL; namespace FastIO { const static int MX=1e6; bool IOerror=0; char nc() { static char buf[MX],*p1=buf+MX,*pend=buf+MX; if(p1==pend) { p1=buf; pend=buf+fread(buf,1,MX,stdin); if(pend==p1) { IOerror=1; return -1; } } return *p1++; } inline bool blank(char ch) { return ch==' '||ch==' '||ch==' '||ch==' '; } inline int read(int& x) { char ch; while(blank(ch=nc())); if(IOerror) return 0; for(x=ch-'0'; (ch=nc())>='0'&&ch<='9'; x=x*10+ch-'0'); //printf("%d=== ",x); return 1; } } using namespace FastIO; const int N=210; const int M=2010; const int INF=0x3f3f3f3f; struct Edge { int to,next; int flow,cap; //根据情况设定变量类型 Edge(){} Edge(int _to,int _next,int _cap,int _flow) { to=_to,next=_next,cap=_cap,flow=_flow; } }; Edge edge[M<<1]; int head[N],tot; int cur[N]; int d[N]; void init() { memset(head,-1,sizeof(head)); tot=0; } inline void addedge(int u,int v,int cap) { edge[tot]=Edge(v,head[u],cap,0); head[u]=tot++; edge[tot]=Edge(u,head[v],0,0); head[v]=tot++; } int bfs(int s,int t) { memset(d,-1,sizeof(d)); queue<int> Q; Q.push(s),d[s]=0; while(!Q.empty()) { int u=Q.front();Q.pop(); for(int i=head[u];~i;i=edge[i].next) { int v=edge[i].to; if(d[v]==-1&&edge[i].cap>edge[i].flow) { d[v]=d[u]+1; if(v==t) return 1; Q.push(v); } } } return ~d[t]; } int dfs(int s,int t,int a) { if(s==t||a==0) return a; int flow=0,df; // for(int& i=cur[s];~i;i=edge[i].next) for(int i=head[s];~i;i=edge[i].next) { int v=edge[i].to; // if(d[v]==d[s]+1 && // (df=dfs(v,t,min(a,edge[i].cap-edge[i].flow))>0)) //这种写法 hdu6214 TLE if(d[v]==d[s]+1&&edge[i].cap>edge[i].flow &&(df=dfs(v,t,min(a,edge[i].cap-edge[i].flow)))>0) { edge[i].flow+=df; edge[i^1].flow-=df; flow+=df; a-=df; if(a==0) break; } } if(flow==0) d[s]=-1; return flow; } int dinic(int s,int t) { int ret=0; while(bfs(s,t)) { // memcpy(cur,head,sizeof(cur)); ret+=dfs(s,t,INF); } return ret; } int main() { int T;read(T); while(T--) { init(); int n,m,s,t; read(n),read(m); read(s),read(t); while(m--) { int u,v,c; read(u),read(v),read(c); addedge(u,v,c*1024+1); } printf("%d ",dinic(s,t)%1024); } }