Dinic模板：
HDU 4280
C++ 加了栈还是TLE ，然后手写对了快了三秒
1 //#pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include <stdio.h> 3 #include <algorithm> 4 #include <string.h> 5 #include <iostream> 6 #include <string> 7 #include <queue> 8 #include<string.h> 9 10 using namespace std; 11 12 #define N 100010 13 #define inf 0x3f3f3f3f 14 15 struct edge 16 { 17 int next,v,c; 18 }e[N<<1]; 19 int n,m; 20 int tot,head[N],d[N]; 21 int q[N]; 22 23 int min(int a,int b) 24 { 25 return a<b?a:b; 26 } 27 28 void add(int u,int v,int c) 29 { 30 e[tot].v=v;e[tot].c=c; 31 e[tot].next=head[u];head[u]=tot++; 32 33 e[tot].v=u;e[tot].c=c; 34 e[tot].next=head[v];head[v]=tot++; 35 } 36 37 int bfs(int s,int t) 38 { 39 memset(d,-1,sizeof(d)); 40 int f=0,r=0; 41 q[r++]=s; 42 d[s]=0; 43 44 while (f<r) 45 { 46 int u=q[f++]; 47 if (u==t) return 1; 48 for (int i=head[u];i!=-1;i=e[i].next) 49 { 50 int v=e[i].v; 51 if (d[v]==-1&&e[i].c>0) 52 { 53 d[v]=d[u]+1; 54 q[r++]=v; 55 } 56 } 57 } 58 return 0; 59 } 60 61 int dfs(int s,int t,int b) 62 { 63 int r=0; 64 if (s==t) return b; 65 for (int i=head[s];i!=-1&&r<b;i=e[i].next) 66 { 67 int v=e[i].v; 68 if (e[i].c>0&&d[v]==d[s]+1) 69 { 70 int x=min(e[i].c,b-r); 71 x=dfs(v,t,x); 72 r+=x; 73 e[i].c-=x; 74 e[i^1].c+=x; 75 } 76 } 77 if (!r) d[s]-=2; 78 return r; 79 } 80 81 int dinic(int s,int t) 82 { 83 int ans=0,tmp; 84 while (bfs(s,t)) 85 { 86 while (tmp=dfs(s,t,inf)) ans+=tmp; 87 } 88 return ans; 89 } 90 91 int main() 92 { 93 int T; 94 scanf("%d",&T); 95 while (T--) 96 { 97 memset(head,-1,sizeof(head)); 98 tot=0; 99 int s,t; 100 scanf("%d%d",&n,&m); 101 int xx=-inf,yy=inf; 102 for (int i=1;i<=n;i++) 103 { 104 int x,y; 105 scanf("%d%d",&x,&y); 106 if (xx<x) xx=x,t=i; 107 if (yy>x) yy=x,s=i; 108 } 109 110 while (m--) 111 { 112 int x,y,c; 113 scanf("%d%d%d",&x,&y,&c); 114 add(x,y,c); 115 } 116 117 printf("%d ",dinic(s,t)); 118 } 119 return 0; 120 }
于是乎找来Sap 模板：
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 7 const int MAXN=100010;//点数的最大值 8 const int MAXM=400010;//边数的最大值 9 const int INF=0x3f3f3f3f; 10 11 struct Node 12 { 13 int from,to,next; 14 int cap; 15 }edge[MAXM]; 16 int tol; 17 int head[MAXN]; 18 int dep[MAXN]; 19 int gap[MAXN];//gap[x]=y :说明残留网络中dep[i]==x的个数为y 20 21 int n;//n是总的点的个数，包括源点和汇点 22 23 void init() 24 { 25 tol=0; 26 memset(head,-1,sizeof(head)); 27 } 28 29 void add_edge(int u,int v,int w) 30 { 31 edge[tol].from=u; 32 edge[tol].to=v; 33 edge[tol].cap=w; 34 edge[tol].next=head[u]; 35 head[u]=tol++; 36 edge[tol].from=v; 37 edge[tol].to=u; 38 edge[tol].cap=w; 39 edge[tol].next=head[v]; 40 head[v]=tol++; 41 } 42 void BFS(int start,int end) 43 { 44 memset(dep,-1,sizeof(dep)); 45 memset(gap,0,sizeof(gap)); 46 gap[0]=1; 47 int que[MAXN]; 48 int front,rear; 49 front=rear=0; 50 dep[end]=0; 51 que[rear++]=end; 52 while(front!=rear) 53 { 54 int u=que[front++]; 55 if(front==MAXN)front=0; 56 for(int i=head[u];i!=-1;i=edge[i].next) 57 { 58 int v=edge[i].to; 59 if(dep[v]!=-1)continue; 60 que[rear++]=v; 61 if(rear==MAXN)rear=0; 62 dep[v]=dep[u]+1; 63 ++gap[dep[v]]; 64 } 65 } 66 } 67 int SAP(int start,int end) 68 { 69 int res=0; 70 BFS(start,end); 71 int cur[MAXN]; 72 int S[MAXN]; 73 int top=0; 74 memcpy(cur,head,sizeof(head)); 75 int u=start; 76 int i; 77 while(dep[start]<n) 78 { 79 if(u==end) 80 { 81 int temp=INF; 82 int inser; 83 for(i=0;i<top;i++) 84 if(temp>edge[S[i]].cap) 85 { 86 temp=edge[S[i]].cap; 87 inser=i; 88 } 89 for(i=0;i<top;i++) 90 { 91 edge[S[i]].cap-=temp; 92 edge[S[i]^1].cap+=temp; 93 } 94 res+=temp; 95 top=inser; 96 u=edge[S[top]].from; 97 } 98 if(u!=end&&gap[dep[u]-1]==0)//出现断层，无增广路 99 break; 100 for(i=cur[u];i!=-1;i=edge[i].next) 101 if(edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1) 102 break; 103 if(i!=-1) 104 { 105 cur[u]=i; 106 S[top++]=i; 107 u=edge[i].to; 108 } 109 else 110 { 111 int min=n; 112 for(i=head[u];i!=-1;i=edge[i].next) 113 { 114 if(edge[i].cap==0)continue; 115 if(min>dep[edge[i].to]) 116 { 117 min=dep[edge[i].to]; 118 cur[u]=i; 119 } 120 } 121 --gap[dep[u]]; 122 dep[u]=min+1; 123 ++gap[dep[u]]; 124 if(u!=start)u=edge[S[--top]].from; 125 } 126 } 127 return res; 128 } 129 int main() 130 { 131 int cn; 132 int m; 133 cin>>cn; 134 int t1,t2,t3; 135 while(cn--) 136 { 137 int maxn = -INF; 138 int minn = INF; 139 int maxi; 140 int mini; 141 cin>>n>>m; 142 init(); 143 for(int i=1; i<=n; i++) 144 { 145 scanf("%d %d", &t1, &t2); 146 if(maxn < t1) 147 { 148 maxn = t1; 149 maxi = i; 150 } 151 if(minn > t1) 152 { 153 minn = t1; 154 mini = i; 155 } 156 } 157 while(m--) 158 { 159 scanf("%d %d %d", &t1, &t2, &t3); 160 add_edge(t1, t2, t3); 161 } 162 printf("%d ", SAP(mini, maxi)); 163 } 164 return 0; 165 }