## 【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;
}


## 【CodeChef DINING】[January Cook-off 2014] Dining

### 解题报告

http://oi.cyo.ng/?p=2702

## 【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真是太强了 _(:з」∠)_

## 【日常小测】摩尔庄园

### Code

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

const int N = 100009;
const int INF = 1e9;

int  n,m,vout,cnt[N],pos[N];
int sur[N],val[N],cost[N];

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 LCA(int u, int v) {
for (;u!=v;u>>=1)
if (u < v) swap(u, v);
return u;
}

inline void update(int w) {
static int ls, rs, cl, cr;
if (cnt[w]) sur[w] = w, val[w] = 0;
else sur[w] = 0, val[w] = INF;
if ((ls=w<<1) <= n) {
cl = cost[ls] > 0? -1: 1;
if(val[ls] + cl < val[w]) {
val[w] = val[ls] + cl;
sur[w] = sur[ls];
}
}
if ((rs=ls|1) <= n) {
int cr = cost[rs] > 0? -1: 1;
if(val[rs] + cr < val[w]) {
val[w] = val[rs] + cr;
sur[w] = sur[rs];
}
}
}

inline void modify(int w, int p, int delta) {
while (w != p) {
cost[w] += delta;
update(w); w >>= 1;
}
}

inline int query(int w, int &ans) {
static int ret, delta; delta = 0;
for (;w;w>>=1) {
if (val[w] + delta < ans) {
ans = val[w] + delta;
ret = sur[w];
}
delta += cost[w] >= 0? 1: -1;
} return ret;
}

int main() {
for (int i=1;i<=n;i++) cnt[i] = read();
for (int i=1;i<=m;i++) pos[i] = read();
for (int i=n;i;i--) update(i);
for (int i=1,u,v,ans=INF;i<=m;++i,ans=INF) {
cnt[v=query(u=pos[i], ans)]--;
printf("%d\n",vout+=ans);
int lca = LCA(u, v);
modify(u, lca, 1); modify(v, lca, -1);
for (;lca;lca>>=1) update(lca);
}
return 0;
}


## 【Yandex Contest 3529D】[NEERC 2016] Delight for a Cat

### Code

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

const int N = 1009;
const int M = 5000;
const LL INF = 1e18;

int n,k,me,ms,S,T,s[N],e[N],edge[N];
LL vout,dis[N];

inline int 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;
return E - 1;
}

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;
}

class Minimum_Cost_Flow{
int sur[N],inq[N];
queue<int> que;
public:
inline LL MaxFlow() {
LL ret_cost = 0;
for (int f=1e9,w;SPFA();f=1e9) {
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;
}
return ret_cost;
}
private:
bool SPFA() {
fill(dis, dis+N, INF);
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;
for (int i=1;i<=n;i++) vout += (s[i] = read());
for (int i=1;i<=n;i++) e[i] = read();
for (int i=2;i<=n-k+2;i++) Add_Edge(i, i-1, k-ms-me, 0);
for (int i=1;i<=n;i++) edge[i] = Add_Edge(min(i+1, n-k+2), max(1, i-k+1), 1, s[i] - e[i]);
printf("%lld\n",vout-MCMF.MaxFlow());
for (int i=1;i<=n;i++) putchar(flow[edge[i]]? 'S': 'E');
return 0;
}


## 【TopCoder SRM570】Curvy on Rails

### 解题报告

1. 回路中的每一个点的度一定是 $2$
2. 如果每一个点的度都是 $2$ ，那么这一定是由一些回路构成的图

1. 横向的度
2. 纵向的度

### Code

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

const int L = 30;
const int N = 2000;
const int M = 50000;
const int INF = 1000000000;

int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};

class Minimum_Cost_Flow{
int dis[N],sur[N],inq[N];
queue<int> que;
public:
inline pair<int,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 make_pair(ret_cost, ret_flow);
}
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;

class CurvyonRails {
int n,m,cnt,E;
char pat[L][L];
public:
int getmin(vector<string> field) {
init();
m = field.size();
n = field[0].size();
for (int j=0;j<m;j++) {
for (int i=0;i<n;i++) {
pat[i+1][j+1] = field[j][i];
}
}
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) {
if (pat[i][j] == 'w') continue;
else {
if (++cnt, i + j & 1) {
} else {
for (int k=1,x,y;k<=4;k++) {
x = i + dx[k];
y = j + dy[k];
if (1 <= x && x <= n && 1 <= y && y <= m) {
if (x == i) Add_Edge(id(i,j,1), id(x,y,1), 1);
if (y == j) Add_Edge(id(i,j,0), id(x,y,0), 1);
}
}
}
if (pat[i][j] == '.') {
}
if (pat[i][j] == 'C') {
}
}
}
}
pair<int,int> vout = MCMF.MaxFlow();
if (vout.second < cnt) return -1;
else return vout.first;
}
private:
inline int id(int x, int y, int t) {
return ((y-1)*n + (x-1)) * 2 + 1 + t;
}
inline void init() {
E = 1; S = cnt = 0; T = N - 1;
}
inline void Add_Edge(int u, int v, int f, int c = 0) {
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;
}
};


## 【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;
}


## 【BZOJ 4514】[Sdoi2016] 数字配对

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

const int M = 200+9;
const int N = 100000+9;
const int MX = 100000;
const int INF = 0x7fffffff;

int pri[N],tot,vis[N],n,A[M],B[M],C[M];
int lft[M],rit[M],tl,tr,sur[M],S,T,inq[M];
LL cost[N],dis[M];
queue<int> que;

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 void Get_Prime_Number(){
for (int i=2;i<=MX;i++) {
if (!vis[i]) pri[++tot] = i;
for (int j=1;j<=tot&&i*pri[j]<=MX;j++)
if (i%pri[j]) vis[i*pri[j]] = 1;
else {vis[i*pri[j]] = 1; break;}
}
}

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

inline bool divide(int w) {int ret = 0; for (int i=1;i<=tot;i++) while (w%pri[i] == 0) w /= pri[i], ret++; return ret&1;}
inline bool is_prime(int w) {for (int i=1;i<=tot;i++) if (pri[i] >= w) break; else if (w%pri[i] == 0) return false; return true;}

inline bool SPFA(){
memset(dis,127,sizeof(dis));
que.push(S); inq[S] = 1; dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
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[to[i]] = i;
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
} return dis[T] < dis[M-2];
}

inline LL MCMF(){
LL ret = 0, tot_cost = 0; bool tag=1;
for (int w=T,f;SPFA()&&tag;w=T) {
for (f=INF;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
if (dis[T]*f+tot_cost > 0) ret += -tot_cost / dis[T], tag = 0;
else {
for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
ret += f; tot_cost += f*dis[T];
}
} return ret;
}

int main(){
n = read(); Get_Prime_Number(); S = 0; T = M - 1;
for (int i=1;i<=n;i++) A[i] = read();
for (int i=1;i<=n;i++) B[i] = read();
for (int i=1;i<=n;i++) C[i] = read();
for (int i=1;i<=n;i++)
if (divide(A[i])) lft[++tl] = i, Add_Edge(S,i,B[i],0);
for (int i=1;i<=tl;i++) for (int j=1;j<=tr;j++) {
int w1 = A[lft[i]], w2 = A[rit[j]]; if (w1 > w2) swap(w1, w2);
if (w2 % w1 == 0 && is_prime(w2 / w1))
} printf("%lld\n",MCMF());
return 0;
}


## 【算法笔记】网络流相关·第二波冲刺

1）最小路径覆盖（路径问题）：出度入度拆点后跑二分图匹配
2）最大独立集：二分图建图后跑最小割
3）供求关系可以考虑二分图
4）棋盘类问题可以考虑染色
5）最大权闭合子图
6）列出数学等式，按等式的正负配合流量平衡进行建图

## 【BZOJ 1061】[Noi2008] 志愿者招募

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

const int N = 1000+9;
const int M = 100000;
const int INF = 1e9;

int n,m,S,T,ned[N],inq[N],sur[N],FLOW[N];
queue<int> que;

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 void Add_Edge(int u, int v, int f, int c) {
static int TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}

inline int SPFA() {
memset(dis,127,sizeof(dis));
memset(FLOW,0,sizeof(FLOW));
que.push(S); dis[S] = 0; inq[S] = 1; FLOW[S] = INF;

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

inline int MCMF() {
int ret = 0;
for (int w=T,f;f=SPFA();w=T) for (int t=sur[w];w!=S;t=sur[w])
flow[t] -= f, flow[t^1] += f, ret += cost[t]*f, w = to[t^1];
return ret;
}

int main(){
n = read(); m = read(); S = 0; T = N-1;
for (int i=1;i<=n;i++) ned[i] = read();
for (int i=n+1;i;i--) ned[i] = ned[i-1] - ned[i];
printf("%d\n",MCMF());
return 0;
}


## 【BZOJ 2879】[Noi2012] 美食节

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

const int L = 100+9;
const int N = 1000+9;
const int M = N*100;
const int INF = 100000000;

int inq[N],cnt,cur[N],mat[L][L],id[N],vout,S,T,sur[N];
queue<int> que;

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 void Add_Edge(int u, int v, int f, int c) {
static int TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}

inline bool SPFA() {
memset(dis,127,sizeof(dis));
que.push(S); inq[S] = 1; dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
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[to[i]] = i;
if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
}
} return dis[T] < 1000000000;
}

inline void MCMF(){
for (int nw;SPFA();) {
for (int w=T;w!=S;w=to[sur[w]^1]) nw = id[w]?id[w]:nw, flow[sur[w]]--, flow[sur[w]^1]++;
id[++cnt] = nw; cur[nw]++; Add_Edge(S,cnt,1,0); vout += dis[T];
}
}

int main(){
n = read(); m = read(); S = 0; T = N - 1; cnt = n+m;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) mat[i][j] = read();
for (int i=1;i<=m;i++) {
id[i+n] = i; cur[i] = 1; Add_Edge(S,i+n,1,0);
} MCMF(); printf("%d\n",vout);
return 0;
}


## 【BZOJ 1070】[SCOI2007] 修车

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

int m,n,s,t,vout;// m means the worker     n means the car
int str[70][20];
struct edge{
int from,to,cap,cost,flow;
edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),cost(cost),flow(flow){}
edge(){}
};
vector<edge> edges;
vector<int> node[700];//1-60 is the car  71-INF is the worker

void addedge(int from,int to,int cap,int flow,int cost){
edges.push_back( edge(from,to,cap,0,cost) );
edges.push_back( edge(to,from,0,0,-cost) );
int asd=edges.size();
node[from].push_back(asd-2);
node[to].push_back(asd-1);
}

void init(){
cin>>m>>n;
for (int i=1,hc;i<=n;i++){//car
for (int j=1;j<=m;j++){//worker
scanf("%d",&hc);//hc=-hc;
for (int k=1,hj;k<=n;k++){
hj=n+(j-1)*n+k;
}
}
}
s=0;t=n+n*m+1;
}

int d[1000],a[1000],p[1000],inq[1000];
bool bellman_ford(){
queue<int> Q;Q.push(s);
memset(inq,0,sizeof (inq));
for (int i=1;i<=t;i++) d[i]=0x7ffffeee;
a[s]=0x7ffffeee;d[s]=0;p[s]=0;inq[s]=1;

while(!Q.empty()) {
int now=Q.front();Q.pop();inq[now]=0;
int len=node[now].size();
for (int i=0;i<len;i++){
edge& e=edges[node[now][i]];
if (e.cap>e.flow && d[e.to]>d[now]+e.cost){
d[e.to]=d[now]+e.cost;
p[e.to]=node[now][i];
a[e.to]=min(a[now],e.cap-e.flow);
if (!inq[e.to]) inq[e.to]=1,Q.push(e.to);
}
}
}
if (d[t]==0x7ffffeee) return false;
vout+=d[t]*a[t];
for (int i=t;i!=s;i=edges[p[i]].from){
edges[p[i]].flow+=a[t];
edges[p[i]^1].flow-=a[t];
}
return true;
}

int main(){
init();
while (bellman_ford()) {}
printf("%.2f",(double)vout/(double)n);
return 0;
}


## 【BZOJ 3171】[Tjoi2013] 循环格

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

const int N = 15*15*2+9;
const int M = N*10;
const int INF = 100000000;

int ord[20],dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1},S,T,inq[N],sur[N];
char pat[20]; queue<int> que;

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 id(int x, int y, int ty) {
static int SUM = n*m;
if (!x) x = n; else if (x == n+1) x = 1;
if (!y) y = m; else if (y == m+1) y = 1;
return x+(y-1)*n+ty*SUM;
}

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

inline int SPFA() {
memset(dis,127,sizeof(dis));
memset(FLOW,0,sizeof(FLOW));
que.push(S); dis[S] = 0; inq[S] = 1; FLOW[S] = INF;

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

inline int MCMF() {
int ret = 0;
for (int w=T,f;f=SPFA();w=T)
for (int t=sur[w];w!=S;t=sur[w])
flow[t] -= f, flow[t^1] += f,
ret += cost[t]*f, w = to[t^1];
return ret;
}

int main(){
m = read(); n = read(); S = 0; T = N-1;
for (int j=1;j<=m;j++) {
scanf("%s",pat+1);
for (int i=1;i<=n;i++)
if (pat[i] == 'R') ord[i] = 1; else if (pat[i] == 'D') ord[i] = 2;
else if (pat[i] == 'L') ord[i] = 3; else ord[i] = 4;
for (int i=1;i<=n;i++) {