## 【Codeforces 802C】Heidi and Library (hard)

### 解题报告

1. 上下界最小费用流：
直接按照上下界网络流一样建图，然后正常跑费用流
2. 带负环的费用流
应用消圈定理，强行将负环满流

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000000;
const int M = 200;
const int INF = 1e9;

int n,k,S,T,tot,SS,TT,ans,a[M],np[M],cc[M];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int AddEdge(int u, int v, int c, int f) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
}

class Minimum_Cost_Flow{
int dis[N],sur[N],inq[N],vis[N];
queue<int> que;
public:
inline void MaxFlow() {
while (clearCircle());
for (int ff; ff = INF, SPFA();) {
for (int w = TT; w != SS; w = to[sur[w]^1]) {
ff = min(ff, flow[sur[w]]);
}
for (int w = TT; w != SS; w = to[sur[w]^1]) {
flow[sur[w]] -= ff;
flow[sur[w]^1] += ff;
}
ans += dis[TT] * ff;
}
}
private:
bool SPFA() {
memset(dis,60,sizeof(dis));
que.push(SS); dis[SS] = 0;

while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = i;
if (!inq[to[i]]) {
inq[to[i]] = 1;
que.push(to[i]);
}
}
}
}
return dis[TT] < INF;
}
bool clearCircle() {
memset(dis, 0, sizeof(dis));
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= tot; ++i) {
if (!vis[i] && DFS(i)) {
return 1;
}
}
return 0;
}
bool DFS(int w) {
vis[w] = 1;
if (inq[w]) {
int cur = w;
do {
flow[sur[cur]]--;
flow[sur[cur]^1]++;
ans += cost[sur[cur]];
cur = to[sur[cur]];
} while (cur != w);
return 1;
} else {
inq[w] = 1;
for (int i = head[w]; i; i = nxt[i]) {
if (flow[i] && dis[to[i]] > dis[w] + cost[i]) {
dis[to[i]] = dis[w] + cost[i];
sur[w] = i;
if (DFS(to[i])) {
inq[w] = 0;
return 1;
}
}
}
inq[w] = 0;
return 0;
}

}
}MCMF;

int main() {
#ifdef DBG
freopen("11input.in", "r", stdin);
#endif
S = tot = n + 4; T = n + 1;
SS = n + 2; TT = n + 3;
for (int i = 1; i <= n; i++) {
np[i] = ++tot;
AddEdge(np[i], i + 1, 0, INF);
}
for (int i = 1; i <= n; i++) {
}
for (int i = 1; i <= n; i++) {
ans += cc[a[i]];
for (int j = i + 1; j <= n; j++) {
if (a[i] == a[j]) {
break;
}
}
}
MCMF.MaxFlow();
cout<<ans<<endl;
return 0;
}


## 【LA 5928】[2016-2017 ACM-ICPC CHINA-Final] Mr.Panda and TubeMaster

### 中文题面

Mr. Panda很喜欢玩游戏。最近，他沉迷在一款叫Tube Master的游戏中。

1. 每个格子要么没有管道，要么这个格子的管道是环形管道的一部分。
2. 每个关键格子必须放置管道。

Mr. Panda想要打赢这局游戏并且拿到尽可能多的分数。你能帮他计算他最多能拿多少分吗？

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000;
const int M = 100000;
const int INF = 1e9;

int pos[30][30],cx[30][30],cy[30][30],vis[30][30];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline int AddEdge(int u, int v, int c, int f) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
return E - 1;
}

class Minimum_Cost_Flow{
int dis[N],sur[N],inq[N];
queue<int> que;
public:
inline int MaxFlow() {
int ret_cost = 0, ret_flow = 0;
for (int f=INF,w;SPFA();f=INF) {
for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
ret_cost += dis[T] * f;
ret_flow += f;
}
return ret_flow == n * m? ret_cost: -INF;
}
private:
bool SPFA() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = i;
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
return dis[T] < INF;
}
}MCMF;

inline int id(int x, int y, int t) {
return ((y - 1) * n + x - 1) * 2 + t;
}

int main() {
S = 0; T = N - 1; E = 1; memset(head,0,sizeof(head));
for (int j=1,v;j<=m;j++) for (int i=1;i<n;i++) cx[i][j] = -read();
for (int j=1,v;j<m;j++) for (int i=1;i<=n;i++) cy[i][j] = -read();
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (vis[i][j] != t) AddEdge(id(i,j,1), id(i,j,2), 0, 1);
}
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if ((i + j) & 1) {
if (i < n) AddEdge(id(i+1,j,1), id(i,j,2), cx[i][j], 1);
if (i > 1) AddEdge(id(i-1,j,1), id(i,j,2), cx[i-1][j], 1);
if (j < m) AddEdge(id(i,j,1), id(i,j+1,2), cy[i][j], 1);
if (j > 1) AddEdge(id(i,j,1), id(i,j-1,2), cy[i][j-1], 1);
}
}
}
int tmp = MCMF.MaxFlow();
if (tmp == -INF) puts("Impossible");
else printf("%d\n",-tmp);
}
return 0;
}


—————————— UPD 2017.3.22 ——————————
Claris给我讲了一点新的姿势，不需要原来的无源汇带上下界费用流了

Claris真是太强了 _(:з」∠)_

## 【BZOJ 3876】[AHOI2014] 支线剧情

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300 + 9;
const int M = 20000 + 100 << 1;
const int INF = 1e9;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int f, int c) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
}

class Minimum_Cost_Flow{
int dis[N],sur[N],inq[N];
queue<int> que;
public:
inline void MaxFlow(bool SPJ=0) {
for (int f=INF,w;SPFA();f=INF) {
if (SPJ && dis[T] >= 0) return;
for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
vout += dis[T] * f;
}
}
private:
bool SPFA() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = i;
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
return dis[T] < INF;
}
}MCMF;

int main() {
S = 0; T = N - 1; V = N - 2;
for  (int i=1,k;i<=n;i++) {
for (int j=1,p,c;j<=k;j++) {
cnt[i]--; cnt[p]++;
vout += c;
}
}
for (int i=1;i<=n;i++) {
if (cnt[i] > 0) Add_Edge(S, i, cnt[i], 0);
}
MCMF.MaxFlow();
if (flow[i]) return 1;
S = V; T = 1;
MCMF.MaxFlow(1);
printf("%d\n",vout);
return 0;
}


## 【算法笔记】上下界网络流问题

### 无源汇可行流

1. 问题分析：
因为只比传统网络流多了下界，所以考虑单独考虑下界的流量

2. 解决方案：
于是原来的边拆为上界为min的边并强行满流，和上界为max - min的边。
但这样可能会出现流量不平衡的状况，及一个点流入的流量不等于流出量。
于是单独增加源汇点，构造一个完全等价的网络流问题

至此我们已经将问题转化为传统网络流问题，直接求解即可。
如何判断是否有可行流的根据也显而易见了：$$Max\_Flow = = \sum {Min\_Flo{w_i}}$$

### 有源汇可行流

1. 问题分析：
有源汇意味着有一对点的流量不守恒，就是这一对点使其于无源汇可行流问题有了差别
于是我们考虑去掉这个不同点，将其转化为无源汇可行流

2. 解决方案
我们注意到，将源汇点连上一条容量INF的边之后，所有的点流量都守恒了
换一句话来说我们将其转化为了无源汇可行流问题，使用上文所述方法求解即可

### 有源汇最大流/最小流

1. 通解通法：
观察可行流的解决方案，不难发现我们控制我们人为增加的那条边的容量即可控制最大流的容量
所以我们可以二分最大流/最小流，之后进行可行流判断，再之后根据结果进行调整即可

2. 最小流的高效算法：
先不连t-s的那条容量为INF的边，先跑一次附加源汇的最大流
连t-s的那条边，在残量网络上继续跑附加源汇最大流
此时t-s那条边的流量是最小的，使用上文所述方法判断其是否为可行流即可

3. 最大流的高效算法
连t-s的那条容量为INF的边，跑一次附加源汇最大流
连t-s的那条边，在残量网络上继续跑s-t的最大流
此时t-s那条边的流量是最小的，使用上文所述方法判断其是否为可行流即可