Island Transport HDU - 4280
题意： 给一张图，求最大流
思路： isap算法模板 详解见此
code：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<queue> using namespace std; const int maxn = 1e5 + 5; struct edges{ int u, v, w, next; } g[maxn]; int head[maxn], cnt; int dep[maxn], cur[maxn], last[maxn], gap[maxn]; void init(int n){ cnt = 0; for(int i = 0; i <= n; i++){ head[i] = -1; } } void add(int u, int v, int w){ g[cnt].u = u; g[cnt].v = v; g[cnt].w = w; g[cnt].next = head[u]; head[u] = cnt++; } void bfs(int n, int s, int t){ for(int i = 1; i <= n; i++){ dep[i] = -1; } queue<int> qu; while(qu.size()) qu.pop(); qu.push(t); dep[t] = 0; while(qu.size()){ int u = qu.front(); qu.pop(); for(int i = head[u]; i != -1; i = g[i].next){ int v = g[i].v; if(dep[v] == -1 && g[i ^ 1].w > 0) dep[v] = dep[u] + 1, qu.push(v); } } for(int i = 0; i<= n; i++) gap[i] = 0; for(int i = 1; i <= n; i++) gap[dep[i]]++; } long long add_flow(int s, int t){ int u = t; int min_flow = g[last[u]].w; while(u != s){ min_flow = min(min_flow, g[last[u]].w); u = g[last[u] ^ 1].v; } u = t; while(u != s){ int k = last[u]; g[k].w -= min_flow; g[k ^ 1].w += min_flow; u = g[k ^ 1].v; } return 1LL * min_flow; } long long isap(int n, int s, int t){ long long flow = 0; for(int i = 1; i <= n; i++){ cur[i] = head[i]; } bfs(n, s, t); int u = s; while(dep[s] < n) { if(u == t){ flow += add_flow(s, t); u = s; } bool flag = false; for(int i = cur[u]; i != -1; i = g[i].next){ cur[u] = i; int v = g[i].v; if(g[i].w > 0 && dep[u] == dep[v] + 1) { u = v; flag = true; last[v] = i; break; } } if(!flag){ int min_dep = n - 1; for(int i = head[u]; i != -1; i = g[i].next) if(g[i].w > 0) min_dep = min(min_dep, dep[g[i].v]); if(--gap[dep[u]] <= 0) break; gap[dep[u] = min_dep + 1]++; cur[u] = head[u]; if(u != s) u = g[last[u] ^ 1].v; } } return flow; } int main(){ int T, n, m; int x, y, u, v, w; int s, t, x1, x2; scanf("%d", &T); while(T--){ scanf("%d%d", &n, &m); init(n); for(int i = 1; i <= n; i++){ scanf("%d%d", &x, &y); if(i == 1) x1 = x, s = 1, x2 = x, t = 1; else{ if(x1 > x) x1 = x, s = i; if(x2 < x) x2 = x, t = i; } } for(int i = 1; i <= m; i++){ scanf("%d%d%d", &u, &v, &w); add(u, v, w); add(v, u, w); } printf("%lld\n", isap(n, s, t)); } }大佬的精简code：
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #include<bits/stdc++.h> #define endl "\n" using namespace std; typedef long long ll; const int maxn=100050; const int maxe=200050; const int inf=0x3f3f3f3f; struct Edge{ int v; int w; int next; }edge[maxe]; int head[maxn],cnt; int gap[maxn],last[maxn],dis[maxn]; int n,m; void add(int u,int v,int w){ edge[cnt].next=head[u]; edge[cnt].v=v; edge[cnt].w=w; head[u]=cnt++; } void init(){ cnt=0; memset(head,-1,sizeof(head)); } void init_mf(int s,int t){ memset(gap,0,sizeof(gap)); memset(dis,0,sizeof(dis)); ++gap[dis[t]=1]; for(int i=1;i<=n;i++) last[i]=head[i]; queue<int>q; q.push(t); while(q.size()){ int x=q.front();q.pop(); for (int i=head[x];i!=-1;i=edge[i].next){ int v=edge[i].v; if (!dis[v]) { ++gap[dis[v]=dis[x]+1]; q.push(v); } } } } ll aug(int x,int s,int t,int mi){ if (x==t) return mi; ll flow=0; for (int &i=last[x];i!=-1;i=edge[i].next){ int v=edge[i].v; if (dis[x]==dis[v]+1){ ll tmp=aug(v,s,t,min(mi,edge[i].w)); flow+=tmp,mi-=tmp,edge[i].w-=tmp,edge[i^1].w+=tmp; if (!mi) return flow; } } if (!(--gap[dis[x]])) dis[s]=n+1; ++gap[++dis[x]],last[x]=head[x]; return flow; } ll maxflow(int s,int t){ init_mf(s,t); ll ret=aug(s,s,t,inf); while (dis[s]<=n) ret+=aug(s,s,t,inf); return ret; } int main() { int tn; scanf("%d",&tn); while(tn--){ int s,t; scanf("%d%d",&n,&m); init(); int mi=inf,ma=-inf; for(int i=1;i<=n;i++){ int x,y; scanf("%d%d",&x,&y); if(x<mi){ mi=x; s=i; } if(x>ma){ ma=x; t=i; } } while(m--){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } printf("%lld\n",maxflow(s,t)); } return 0; }