ACM
网络流
666字
两个定理的证明
https://www.cnblogs.com/cniwoq/p/9245813.html
spfa的一些说明
https://blog.csdn.net/xiazdong/article/details/8193680
dinic
cpp 1const itn maxn = 1200 + 10; 2const int maxe = 120000 + 10; 3const ll inf = 1ll << 60; 4 5struct star{int to, next, w;}; 6int head[maxn], top = 0; 7star edge[maxe << 1]; 8 9void add(int u, int v, int w){ 10 edge[top].to = v; 11 edge[top].next = head[u]; 12 edge[top].w = w; 13 head[u] = top++; 14} 15 16int d[maxn], cur[maxn]; 17 18ll dfs(int s, int t, ll flow){ 19 if(flow == 0 || s == t) return flow; 20 21 ll res = 0, f; 22 for(int i = cur[s]; ~i; i = edge[i].next){ 23 cur[s] = i; 24 if(d[edge[i].to] == d[s] + 1){ 25 f = dfs(edge[i].to, t, min(flow, (ll)edge[i].w)); 26 edge[i].w -= f; edge[i ^ 1].w += f; res += f; flow -= f; 27 if(flow == 0) break; 28 } 29 } 30 return res; 31} 32 33queue<int> q, q0; 34bool bfs(int s, int t){ 35 clr(d, 0); 36 q = q0; q.push(s); 37 cur[s] = head[s]; d[s] = 1; 38 while(!q.empty()){ 39 int now = q.front(); q.pop(); 40 for(int i = head[now]; ~i; i = edge[i].next) if(!d[edge[i].to] && edge[i].w > 0){ 41 cur[edge[i].to] = head[edge[i].to]; d[edge[i].to] = d[now] + 1; 42 if(edge[i].to == t) return true; 43 q.push(edge[i].to); 44 } 45 } 46 return false; 47} 48 49ll dinic(int s, int t){ 50 ll ans = 0; 51 while(bfs(s, t)) ans += dfs(s, t, inf); 52 return ans; 53} 54 55 56 57int main(){ 58// Fastin; 59 clr(head, -1); 60 int n, m, s, t; scanf("%d %d %d %d", &n, &m, &s, &t); 61 for(int i = 0, u, v, w; i < m; i++){ 62 scanf("%d %d %d", &u, &v, &w); 63 add(u, v, w); add(v, u, 0); 64 } 65 printf("%lld\n", dinic(s, t)); 66 return 0; 67} isap
...