（待更新）
有一种类似于Dinic的写法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; const int MAXN = 1000; const int MAXM = 30010; const int INF = 2147483647; namespace Dinic { struct Edge { int from,to,cap,cost,flow; Edge() {} Edge(int from,int to,int cap,int cost,int flow): from(from), to(to), cap(cap), cost(cost), flow(flow) {} }; int n,m,s,t; int head[MAXN],nxt[MAXM]; Edge edge[MAXM]; int dist[MAXN],cur[MAXN]; void clear(int _n) { n = _n; m = 0; memset(head,255,sizeof head); } void addedge(int from,int to,int cap,int cost) { edge[m] = Edge(from,to,cap,cost,0); nxt[m] = head[from]; head[from] = m++; edge[m] = Edge(to,from,0,-cost,0); nxt[m] = head[to]; head[to] = m++; } queue<int> q; bool inq[MAXN]; bool spfa() { for(int i = 0; i < n; ++i) dist[i] = INF; memset(inq,0,sizeof inq); dist[s] = 0; q.push(s); inq[s] = 1; while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = 0; for(int i = head[u]; ~i; i = nxt[i]) { Edge &e = edge[i]; if(e.cap > e.flow && dist[e.to] > dist[u] + e.cost) { dist[e.to] = dist[u] + e.cost; if(!inq[e.to]) { inq[e.to] = 1; q.push(e.to); } } } } return dist[t] != INF; } int cost; bool vis[MAXN]; int dfs(int u,int res) { vis[u] = 1; if(u == t || !res) {return cost += dist[t] * res, res;} int flow = 0, f; for(int &i = cur[u]; ~i; i = nxt[i]) { Edge &e = edge[i]; if(e.cap > e.flow && dist[e.to] == dist[u] + e.cost && (!vis[e.to])) { f = dfs(e.to,min(e.cap - e.flow,res)); e.flow += f; edge[i^1].flow -= f; flow += f; res -= f; if(!res) break; } } return flow; } int maxflow(int _s,int _t) { s = _s; t = _t; int flow = 0, f; while(spfa()) { vis[t] = 1; while(vis[t]) { memset(vis,0,sizeof vis); for(int i = 0; i < n; ++i) cur[i] = head[i]; while(f = dfs(s,INF)) flow += f; } } return flow; } } int read() { char ch = getchar(); int x = 0, f = 1; while(ch < '0' || ch > '9') {if(ch == '-') f = -f; ch = getchar();} while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} return x * f; } int main() { int n,m; n = read(), m = read(); Dinic::clear(n + 1); int s,t,c,w; for(int i = 1; i <= m; ++i) { s = read(), t = read(), c = read(), w = read(); Dinic::addedge(s,t,c,w); } printf("%d ",Dinic::maxflow(1,n)); printf("%d\n",Dinic::cost); return 0; } |