Contents
问题
题目描述
给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。
输入格式
第一行包含四个正整数 N,M,S,T，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来 M 行每行包含四个正整数 u_i,v_i,w_i,f_i，表示第 i 条有向边从 u_i 出发，到达 v_i，边权为 w_i，单位流量的费用为 f_i。
输出格式
一行两个整数，依次为最大流量和在最大流量情况下的最小费用。
朴素spfa
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const long long INF = 1e18;
const int N = 5e3 + 50;
const int MAXM = 6e5 + 50;
int n, m, S, T;
int head[N], tot = 1;
struct Edge
{
int nex, to, w, c;
}e[2 * MAXM];
void addedge(int a, int b, int c, int d)
{
e[++tot] = (Edge) {head[a], b, c, d};
head[a] = tot;
}
void add(int a, int b, int c, int d) {
addedge(a, b, c, d);
addedge(b, a, 0, -d);
}
struct MCMF {
queue<int> q;
int n, S, T;
long long maxflow, mincost;
int pre[N], last[N], vis[N], flow[N];
long long dis[N];
void init(int _n, int _S, int _T) {
n = _n; S = _S; T = _T;
maxflow = mincost = 0;
memset(head, 0, sizeof(head));
tot = 1;
}
int spfa() {
for (int i = 1; i <= n; i++) {
dis[i] = INF; vis[i] = 0;
}
dis[S] = 0; vis[S] = 1;
flow[S] = 1e9; pre[T] = 0;
while(!q.empty()) q.pop(); q.push(S);
while(!q.empty())
{
int now = q.front();
q.pop(); vis[now] = 0;
for(int i = head[now]; i; i = e[i].nex)
{
int to = e[i].to;
if(e[i].w && dis[to] > dis[now] + e[i].c)
{
dis[to] = dis[now] + e[i].c;
pre[to] = now;
last[to] = i;
flow[to] = min(e[i].w, flow[now]);
if(!vis[to])
{
vis[to] = 1;
q.push(to);
}
}
}
}
return pre[T] > 0;
}
void solve() {
while(spfa()) {
maxflow += flow[T];
mincost += 1LL * flow[T] * dis[T];
for(int now = T; now != S; now = pre[now])
{
e[last[now]].w -= flow[T];
e[last[now]^1].w += flow[T];
}
}
}
}mcmf;
int main()
{
scanf("%d%d%d%d", &n, &m, &S, &T);
mcmf.init(n, S, T);
for(int i = 1, a, b, c, d; i <= m; i++)
{
scanf("%d%d%d%d", &a, &b, &c, &d);
add(a, b, c, d);
}
mcmf.solve();
printf("%lld %lld\n", mcmf.maxflow, mcmf.mincost);
return 0;
}
Dijkstra优化
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, int> pii;
typedef long long ll;
#define mp make_pair
const int N = 5e3 + 50;
const int MAXM = 6e5 + 50;
const long long INF = 1e18;
int n, m, S, T;
int head[N], tot = 1;
struct Edge
{
int nex, to, w, c;
}e[2 * MAXM];
void addedge(int a, int b, int c, int d)
{
e[++tot] = (Edge) {head[a], b, c, d};
head[a] = tot;
}
void add(int a, int b, int c, int d) {
addedge(a, b, c, d);
addedge(b, a, 0, -d);
}
struct MCMF {
long long maxflow, mincost;
int n, S, T;
void init(int _n, int _S, int _T) {
n = _n; S = _S; T = _T;
maxflow = mincost = 0;
memset(head, 0, sizeof(head));
tot = 1;
}
int vis[N], tim[N];
long long d[N];
queue<int> q;
void spfa(int u) {
for (int i = 1; i <= n; i++) {
d[i] = INF; vis[i] = 0;
}
d[u] = 0; vis[u] = 1;
q.push(u);
while (!q.empty()) {
int v = q.front();
q.pop(); vis[v] = 0;
if (++tim[v] >= n) {
return ;
}
for (int i = head[v]; i; i = e[i].nex) {
int to = e[i].to;
if (e[i].w && d[to] > d[v] + e[i].c) {
d[to] = d[v] + e[i].c;
if (!vis[to]) {
vis[to] = 1;
q.push(to);
}
}
}
}
}
long long dis[N];
int pre[N], last[N], flow[N];
priority_queue<pii, vector<pii>, greater<pii> > pq;
bool Dijkstra() {
for (int i = 1; i <= n; i++) {
dis[i] = INF; vis[i] = 0;
}
while(!pq.empty()) pq.pop();
dis[S] = 0; pre[T] = 0;
flow[S] = 1e9;
pq.push(mp(0, S));
while(!pq.empty()) {
pii t = pq.top(); pq.pop();
int id = t.second;
if(vis[id]) continue;
vis[id] = 1;
for(int i = head[id]; i; i = e[i].nex) {
int to = e[i].to;
long long len = t.first + d[id] - d[to] + e[i].c;
if(e[i].w && dis[to] > len) {
dis[to] = len;
pq.push(mp(dis[to], to));
flow[to] = min(e[i].w, flow[id]);
pre[to] = id;
last[to] = i;
}
}
}
return pre[T] > 0;
}
void solve() {
spfa(S);
while (Dijkstra()) {
maxflow += flow[T];
mincost += 1LL * flow[T] * (d[T] + dis[T]);
for(int now = T; now != S; now = pre[now])
{
e[last[now]].w -= flow[T];
e[last[now]^1].w += flow[T];
}
for (int i = 1; i <= n; i++) {
d[i] = min(d[i] + dis[i], INF);
}
}
}
}mcmf;
int main(int argc, const char * argv[]) {
scanf("%d%d%d%d", &n, &m, &S, &T);
mcmf.init(n, S, T);
for(int i = 1, a, b, c, d; i <= m; i++)
{
scanf("%d%d%d%d", &a, &b, &c, &d);
add(a, b, c, d);
}
mcmf.solve();
printf("%lld %lld\n", mcmf.maxflow, mcmf.mincost);
return 0;
}
应用
题目大意：
给出一个 n\times n 的矩阵,每一格有一个非负整数 A_{ij},(A_{ij} \le 1000) 现在从 (1,1) 出发,可以往右或者往下走,最后到达 (n,n),每达到一格,把该格子的数取出来,该格子的数就变成 0,这样一共走 K 次,现在要求 K次所达到的方格的数的和最大。
分析：
- 超级源点和超级汇点分别连向（1,1）（n , n），容量为k，费用为0，仅表示一共可以走k次；
- 对于方格中的每个点，拆成两个点，分别为入点和出点。入点和出点之间连两条边，一条容量为 1，费用为点的权值，表示每个点的数只可以取一次；另一条容量为 \text{inf}，费用为 0，仅表示可以经过无数次；
- 对于在其下方或右边点的点，连一条容量为 \text{inf}，费用为 0 的边，表示且仅表示一种联通的关系。
- 把费用设为负数，最后再取相反数即可。