网络流
(_{_{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}^{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}_{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}^{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}}^{_{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}^{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}_{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}^{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}}{_{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}^{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}_{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}^{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}}_{_{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}^{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}_{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}^{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}}^{_{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}^{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}_{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}^{_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}{_{?}^{?}{?}_{?}^{?}}_{_{?}^{?}{?}_{?}^{?}}^{_{?}^{?}{?}_{?}^{?}}}})
1.最大流
/***********************************
dinic最大流思路：
不断图分层，保证dfs过程中，不会出现环等现象
在一次分层中，用dfs一次性搜寻多条增广路。
就是向下搜，搜到t为止，然后返回流量。
当前节点最大流量为的下属分支所有流量的返回最大流量。
下属分支返回的流量为min(通往该分支边的最大流量,分支的下属总流量)
当dfs一次后，一定会有某些边被榨干，改变分层图。
再次分层图，重复上述过程。
分层图用bfs实现。如果bfs不到终点，则结束算法。
************************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
typedef long long ll;
typedef long long ii;
const ll maxn = 205;
const ll maxm = 2e3+40;
const ll INF = ll(1)<<50;
struct e{
ll next,to,flow;
}edge[maxm*2];
int head[maxn],tot=0;
void add(ll u,ll v,ll flow){
edge[tot].to=v;edge[tot].next=head[u];
edge[tot].flow=flow;head[u]=tot++;
edge[tot].to=u;edge[tot].next=head[v];
edge[tot].flow=0;head[v]=tot++;
}
ll n,m,s,t;
ll dis[maxn];
queue<ll> q;
ll cur[maxn];
ll dfs(ll u,ll lim){
//cout<<"dfs"<<endl;
// /system("pause");
if(u==t)return lim;
ll flow=0;
for(ll i=cur[u];~i;i=edge[i].next){
cur[u]=i;
//最优弧优化。
//因为不是树，是网络图，所以回溯后，可能从其他分支再经过当前点。
//而当前点的之前的边流量一定已经被榨干了。
//所以不用考虑当前边的前边的边
ll v= edge[i].to;
if(dis[v]!=dis[u]+1||edge[i].flow==0){
continue;
}
ll f=dfs(v,min(edge[i].flow,lim));
flow+=f;lim-=f;
edge[i].flow-=f;edge[i^1].flow+=f;
if(lim==0)break;
}
return flow;
}
ll bfs(){
while(!q.empty())q.pop();
for(ll i=1;i<=n;i++){
dis[i]=INF;
cur[i]=head[i];
}
dis[s]=0;
q.push(s);
while(!q.empty()){
ll u=q.front();q.pop();
for(ll i=head[u];~i;i=edge[i].next){
ll v= edge[i].to;
//cout<<i<<" "<<v<<endl;
if(edge[i].flow==0||dis[v]!=INF)continue;
dis[v]=dis[u]+1;
q.push(v);
}
}
if(dis[t]==INF)return 0;
else return 1;
}
void init(){
for(ll i=0;i<=n;i++){
head[i]=-1;
}
}
int main(){
// cout<<INF+1<<endl;
ll x;
scanf("%lld%lld%lld",&n,&m,&x);
init();
s=1;t=n;
ll a,b,c;
for(int i=0;i<m;i++){
scanf("%lld%lld%lld",&a,&b,&c);
add(a,b,c);
}
/*
for(int i=0;i<tot;i++){
cout<<i<<":"<<edge[i].to<<" "<<edge[i].next<<" "<<edge[i].flow<<endl;
}*/
ll maxflow=0;
while(bfs()){
maxflow+=dfs(s,INF);
//cout<<maxflow<<endl;
}
if(maxflow==0)puts("Orz Ni Jinan Saint Cow!");
else printf("%lld %lld",maxflow,(x+maxflow-1)/maxflow);
return 0;
}
2.最小费用流
/******************************************************
整体思路：
首先在图中找到一条流不为0的最少费用路
可用dij或者spfa,dij的话要给所有的加势；
在找最短路的过程中，cost看做路径长度。
用pre[i]来存储前一条边是哪条边，因为最后
要处理所有途径边的流量，和计算cost；
cost为dis[t]*incf[t];
dis[t]为路径上累计长度，即累计单位流量花费。
然后重复调用上述过程，直到找不到一条最短路径。
*******************************************************/
#include<iostream>
#include<queue>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n,m,s,t;
int maxflow,mincost;
const int maxn=5e3+50,maxm=5e4+50;
struct e{
int next,to,flow,cost;
}edge[maxm*2];
int head[maxn],tot=0;
void add(int u,int v,int flow,int cost){
edge[tot].flow=flow;edge[tot].cost=cost;
edge[tot].next=head[u];edge[tot].to=v;
head[u]=tot++;
edge[tot].flow=0;edge[tot].cost=-cost;
edge[tot].next=head[v];edge[tot].to=u;
head[v]=tot++;
}
int dis[maxn];
int incf[maxn];
bool inq[maxn];
int pre[maxn];
bool spfa(){
queue<int> q;
for(int i=0;i<=n;i++){
dis[i]=0x7fffffff;
inq[i]=false;
}
q.push(s);
inq[s]=1;dis[s]=0;
incf[s]=0x7fffffff;
while(!q.empty()){
int u=q.front();q.pop();
inq[u]=0;
for(int i=head[u];~i;i=edge[i].next){
if(edge[i].flow==0)continue;
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].cost){
dis[v]=dis[u]+edge[i].cost;
incf[v]=min(edge[i].flow,incf[u]);
pre[v]=i;
//存前驱的边是因为最后要通过前驱来快速会找到边从而操作cost和flow
//存点的遍历所有的边。
//前驱点的寻找可以用反向边的to来寻找。
if(!inq[v]){
q.push(v);inq[v]=true;
}
}
}
}
if(dis[t]==0x7fffffff)return 0;
else return 1;
}
void MCMF(){
while(spfa()){
int x=t;
maxflow += incf[t];
mincost += dis[t]*incf[t];
int i;
while(x!=s){
i=pre[x];
edge[i].flow -= incf[t];
edge[i^1].flow += incf[t];
x = edge[i^1].to;
}
}
}
void init(){
for(int i=0;i<=n;i++){
head[i]=-1;
}
}
int main(){
maxflow=mincost=0;
scanf("%d%d%d%d",&n,&m,&s,&t);
init();
int u,v,cost,flow;
for(int i=0;i<m;i++){
scanf("%d%d%d%d",&u,&v,&flow,&cost);
add(u,v,flow,cost);
}
MCMF();
printf("%d %d
",maxflow,mincost);
return 0;
}
3.无源汇上下界可行流
/*******************
无源汇上下界可行流：
首先将图中的下界流跑满
建图的边改为上界减下界
那么会出现部分点的流不平衡
我们给这些点分别连一个起点和终点。
给缺少出流的连上起点，缺少入流的连上终点。
边的流上界为所缺少或多余的流
这样在跑满最大流后，
如果连接终点和起点的流跑满之后，
把终点和起点去掉，那么终点和起点连接的节点
会分别多出/少了连边对应边的满流。
因为前面是按照缺少/多余建图
所以缺少/多余各自补平。
做法：
建图，边为上界减下界，存下下界
建源点汇点，连统计入度出度的边
跑最大流
输出边时输出下界流+最大流的流
********************/
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 219;
const int maxm = 10250;
struct e {
int next, to, flow;
} edge[maxm * 2];
int head[maxn], tot = 0;
void add(int u, int v, int flow) {
edge[tot].next = head[u];
edge[tot].to = v;
edge[tot].flow = flow;
head[u] = tot++;
edge[tot].next = head[v];
edge[tot].to = u;
edge[tot].flow = 0;
head[v] = tot++;
}
int s, t, n, m;
int cur[maxn + 2];
int dis[maxn + 2];
int dfs(int u, int lim) {
if (u == t || lim == 0)
return lim;
int flow = 0;
for (int i = cur[u]; ~i; i = edge[i].next) {
// cout<<cur[u]<<endl;
// system("pause");
cur[u] = i;
int v = edge[i].to;
if (dis[v] != dis[u] + 1)
continue;
int f = dfs(v, min(lim, edge[i].flow));
flow += f;
lim -= f;
edge[i].flow -= f;
edge[i ^ 1].flow += f;
if (lim == flow)
break;
}
return flow;
}
bool bfs() {
for (int i = 0; i <= n + 5; i++) {
dis[i] = 0x7fffffff;
cur[i] = head[i];
}
dis[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (dis[v] != 0x7fffffff || edge[i].flow == 0)
continue;
dis[v] = dis[u] + 1;
q.push(v);
}
}
if (dis[t] == 0x7fffffff)
return 0;
else
return 1;
}
int maxflow = 0;
bool dinic() {
while (bfs()) {
maxflow += dfs(s, 0x7fffffff);
}
for (int i = head[s]; ~i; i = edge[i].next) {
if (edge[i].flow != 0)
return 0;
}
return 1;
}
int level[maxn];
int addd[maxm];
void init() {
for (int i = 0; i <= n + 2; i++) {
level[i] = 0;
head[i] = -1;
}
for (int i = 0; i < m; i++) {
addd[i] = 0;
}
}
int main() {
freopen("2.in","r",stdin);
scanf("%d%d", &n, &m);
init();
int a, b, l, u;
for (int i = 0; i < m; i++) {
scanf("%d%d%d%d", &a, &b, &l, &u);
add(a, b, u - l);
level[b] += l;
level[a] -= l;
addd[i] += l;
}
s = n + 1, t = n + 2;
int first = 0;
for (int i = 1; i <= n; i++) {
if (level[i] > 0) {
add(s, i, level[i]);
}
if (level[i] < 0) {
first += level[i];
add(i, t, -level[i]);
}
}
if (dinic()) {
puts("YES");
for (int i = 0; i < m; i++) {
cout << edge[i * 2 + 1].flow + addd[i] << endl;
}
} else
puts("NO");
return 0;
}
4.有源汇上下界最小流
/*******************
无源汇上下界可行流：
首先将图中的下界流跑满
建图的边改为上界减下界
那么会出现部分点的流不平衡
我们给这些点分别连一个起点和终点。
给缺少出流的连上起点，缺少入流的连上终点。
边的流上界为所缺少或多余的流
这样在跑满最大流后，
如果连接终点和起点的流跑满之后，
把终点和起点去掉，那么终点和起点连接的节点
会分别多出/少了连边对应边的满流。
因为前面是按照缺少/多余建图
所以缺少/多余各自补平。
做法：
建图，边为上界减下界，存下下界
建源点汇点，连统计入度出度的边
跑最大流
输出边时输出下界流+最大流的流
********************/
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 219;
const int maxm = 10250;
struct e {
int next, to, flow;
} edge[maxm * 2];
int head[maxn], tot = 0;
void add(int u, int v, int flow) {
edge[tot].next = head[u];
edge[tot].to = v;
edge[tot].flow = flow;
head[u] = tot++;
edge[tot].next = head[v];
edge[tot].to = u;
edge[tot].flow = 0;
head[v] = tot++;
}
int s, t, n, m;
int cur[maxn + 2];
int dis[maxn + 2];
int dfs(int u, int lim) {
if (u == t || lim == 0)
return lim;
int flow = 0;
for (int i = cur[u]; ~i; i = edge[i].next) {
// cout<<cur[u]<<endl;
// system("pause");
cur[u] = i;
int v = edge[i].to;
if (dis[v] != dis[u] + 1)
continue;
int f = dfs(v, min(lim, edge[i].flow));
flow += f;
lim -= f;
edge[i].flow -= f;
edge[i ^ 1].flow += f;
if (lim == flow)
break;
}
return flow;
}
bool bfs() {
for (int i = 0; i <= n + 5; i++) {
dis[i] = 0x7fffffff;
cur[i] = head[i];
}
dis[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (dis[v] != 0x7fffffff || edge[i].flow == 0)
continue;
dis[v] = dis[u] + 1;
q.push(v);
}
}
if (dis[t] == 0x7fffffff)
return 0;
else
return 1;
}
int maxflow = 0;
bool dinic() {
while (bfs()) {
maxflow += dfs(s, 0x7fffffff);
}
for (int i = head[s]; ~i; i = edge[i].next) {
if (edge[i].flow != 0)
return 0;
}
return 1;
}
int level[maxn];
int addd[maxm];
void init() {
for (int i = 0; i <= n + 2; i++) {
level[i] = 0;
head[i] = -1;
}
for (int i = 0; i < m; i++) {
addd[i] = 0;
}
}
int main() {
freopen("2.in","r",stdin);
scanf("%d%d", &n, &m);
init();
int a, b, l, u;
for (int i = 0; i < m; i++) {
scanf("%d%d%d%d", &a, &b, &l, &u);
add(a, b, u - l);
level[b] += l;
level[a] -= l;
addd[i] += l;
}
s = n + 1, t = n + 2;
int first = 0;
for (int i = 1; i <= n; i++) {
if (level[i] > 0) {
add(s, i, level[i]);
}
if (level[i] < 0) {
first += level[i];
add(i, t, -level[i]);
}
}
if (dinic()) {
puts("YES");
for (int i = 0; i < m; i++) {
cout << edge[i * 2 + 1].flow + addd[i] << endl;
}
} else
puts("NO");
return 0;
}