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
| #include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int eN = 100005;
const int vN = 10005;
const int INF = 0x7f7f7f7f;
int n, m, s, t;
int ePtr = -1; //e的实际存储只能从偶数号顶点开始,奇数号顶点存储反向边
int to[eN << 1], nxt[eN << 1], value[eN << 1], cost[eN << 1];
int head[vN], dis[vN], minV[vN];
int preID[eN << 1], preNode[eN << 1];
bool inqueue[vN];
inline void createEdge(int u, int v, int w, int c) {
to[++ePtr] = v;
value[ePtr] = w;
cost[ePtr] = c;
nxt[ePtr] = head[u];
head[u] = ePtr;
}
bool SPFA(int s, int t) {
queue<int> q;
memset(dis, 0x7f, sizeof(dis));
memset(inqueue, false, sizeof(inqueue));
memset(preID, -1, sizeof(preID));
memset(preNode, -1, sizeof(preNode));
memset(minV, 0x7f, sizeof(minV));
dis[s] = 0;
inqueue[s] = true;
q.push(s);
while (!q.empty()) {
int x = q.front();
q.pop();
inqueue[x] = false;
for (int i = head[x]; ~i; i = nxt[i]) {
int dest = to[i];
if (dis[dest] > dis[x] + cost[i] && value[i]) {
dis[dest] = dis[x] + cost[i];
minV[dest] = min(minV[x], value[i]);
preID[dest] = i;
preNode[dest] = x;
if (!inqueue[dest]) {
inqueue[dest] = true;
q.push(dest);
}
}
}
}
return dis[t] != INF;
}
void MinCostMaxFlow(int s, int t, int& maxflow, int& mincost) {
while (SPFA(s, t)) {
for (int i = t; i != s; i = preNode[i]) {
value[preID[i]] -= minV[t];
value[preID[i] ^ 1] += minV[t];
}
maxflow += minV[t];
mincost += minV[t] * dis[t];
}
}
int main() {
memset(head, -1, sizeof(head));
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1; i <= m; i++) {
int u, v, w, f;
scanf("%d%d%d%d", &u, &v, &w, &f);
createEdge(u, v, w, f);
createEdge(v, u, 0, -f);//第0号边被占用,这条语句为反向边留下空间
}
int maxflow = 0, mincost = 0;
MinCostMaxFlow(s, t, maxflow, mincost);
printf("%d %d\n", maxflow, mincost);
} |