二分图最大匹配问题。
【建模方法】
在二分图的基础上增加源S和汇T
1、S向X集合中每个顶点连一条容量为1的有向边。
2、Y集合中每个顶点向T连一条容量为1的有向边。
3、XY集合之间的边都设为从A集合中的点到B集合之中的点，容量为1的有向边。
求网络最大流，流量就是匹配数，所有满流边是一组可行解。
【建模分析】
基本的二分图最大匹配，可以直接用匈牙利算法或Hopcroft_Karp算法解决，更一般的方法是网络最大流。
例题:
【问题描述】
飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。
如图，假设有10个驾驶员，如图中的V1，V2，…，V10就代表达10个驾驶员,其中V1，V2，V3，V4，V5是正驾驶员,V6，V7，V8，V9，V10是副驾驶员。如果一个正驾驶员和一个副驾驶员可以同机飞行，就在代表他们两个之间连一条线,两个人不能同机飞行，就不连。例如V1和V7可以同机飞行，而V1和V8就不行。请搭配飞行员，使出航的飞机最多。注意:因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行.
【输入格式】
输入文件有若干行
第一行，两个整数n与n1，表示共有n个飞行员(2<=n<=100),其中有n1名飞行员是正驾驶员.
下面有若干行,每行有2个数字a,b。表示正驾驶员a和副驾驶员b可以同机飞行。
注:正驾驶员的编号在前,即正驾驶员的编号小于副驾驶员的编号.
【输出格式】
输出文件有一行
第一行，1个整数，表示最大起飞的飞机数。
【输入输出样例】
输入文件名： flyer.in
10 5
1 7
2 6
2 10
3 7
4 8
5 9
输出文件名：flyer.out
4
【问题分析】
二分图最大匹配问题。
【建模方法】
在二分图的基础上增加源S和汇T。
1、S向X集合中每个顶点连一条容量为1的有向边。
2、Y集合中每个顶点向T连一条容量为1的有向边。
3、XY集合之间的边都设为从A集合中的点到B集合之中的点，容量为1的有向边。
求网络最大流，流量就是匹配数，所有满流边是一组可行解。
【建模分析】
基本的二分图最大匹配，可以直接用匈牙利算法或Hopcroft_Karp算法解决，更一般的方法是网络最大流。
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<iomanip>
//#define mem(dp,a) memset(dp,a,sizeof(dp))
//#define fo(i,n) for(int i=0;i<(n);i++)
//#define INF 0x3f3f3f3f
#define fread() freopen("data.txt","r",stdin)
#define fwrite() freopen("out.out","w",stdout)
using namespace std;
typedef long long ll;
//最小费用最大流,求最大费用只需要取相反数,结果取相反数即可。
//点的总数为 N,点的编号 0~N-1
const int MAXN = 505;
const int MAXM = 100005;//要比题目给的大
const int INF = 0x3f3f3f3f;
struct Edge
{
int to, next, cap, flow, cost;
int x, y;
} edge[MAXM],HH[MAXN],MM[MAXN];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N, M;
void init(int n)
{
N = n;
tol = 0;
memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int cap, int cost)//左端点，右端点，容量，花费
{
edge[tol]. to = v;
edge[tol]. cap = cap;
edge[tol]. cost = cost;
edge[tol]. flow = 0;
edge[tol]. next = head[u];
head[u] = tol++;
edge[tol]. to = u;
edge[tol]. cap = 0;
edge[tol]. cost = -cost;
edge[tol]. flow = 0;
edge[tol]. next = head[v];
head[v] = tol++;
}
bool spfa(int s, int t)
{
queue<int>q;
for(int i = 0; i < N; i++)
{
dis[i] = INF;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u]; i != -1; i = edge[i]. next)
{
int v = edge[i]. to;
if(edge[i]. cap > edge[i]. flow &&
dis[v] > dis[u] + edge[i]. cost )
{
dis[v] = dis[u] + edge[i]. cost;
pre[v] = i;
if(!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
if(pre[t] == -1) return false;
else return true;
}
/*
* 直接调用获取最小费用和最大流
* 输入: start-源点，end-汇点（编号从0开始）
* 返回值: pair<int,int> 第一个是最小费用，第二个是最大流
*/
pair<int, int> minCostMaxflow(int s, int t)
{
int flow = 0;
int cost = 0;
while(spfa(s,t))
{
int Min = INF;
for(int i = pre[t]; i != -1; i = pre[edge[i^1]. to])
{
if(Min > edge[i]. cap - edge[i]. flow)
Min = edge[i]. cap - edge[i]. flow;
}
// int percost=0;
for(int i = pre[t]; i != -1; i = pre[edge[i^1]. to])
{
edge[i]. flow += Min;
edge[i^1]. flow -= Min;
cost += edge[i]. cost * Min;
// percost+=edge[i].cost;
}
// if(percost>0){
// return make_pair(cost, flow);
// }
// cost+=percost*Min;
flow += Min;
}
return make_pair(cost, flow);
}
int a,b,c,d;
int u,v,k;
int m,n;
int main()
{
ios_base::sync_with_stdio(false);
// fread();
freopen("flyer.in","r",stdin);
freopen("flyer.out","w",stdout);
while(cin >> n>>m)
{
init(n+2);
while(cin >>u>>v)
{
addedge(u,v,1,0);
// addedge(v,u,1,0);
}
for(int i=1;i<=m;i++)
{
addedge(0,i,1,0);
}
for(int i=m+1;i<=n;i++)
{
addedge(i,n+1,1,0);
}
cout << minCostMaxflow(0,n+1).second <<endl;
}
return 0;
}
最大权闭合图
【问题分析】
最大权闭合图问题，可以转化成最小割问题，进而用最大流解决。
【建模方法】
把每个实验看作二分图X集合中的顶点，每个设备看作二分图Y集合中的顶点，增加源S和汇T。
1、从S向每个Xi连接一条容量为该点收入的有向边。
2、从Yi向T连接一条容量为该点支出的有向边。
3、如果一个实验i需要设备j，连接一条从Xi到Yj容量为无穷大的有向边。
统计出所有实验的收入只和Total，求网络最大流Maxflow，最大收益就是Total-Maxflow。对应的解就是最小割划分出的S集合中的点，也就是最后一次增广找到阻塞流时能从S访问到的顶点。
【建模分析】
定义一个割划分出的S集合为一个解，那么割集的容量之和就是(未被选的A集合中的顶点的权值 + 被选的B集合中的顶点的权值)，记为Cut。A集合中所有顶点的权值之和记为Total，那么Total - Cut就是(被选的A集合中的顶点的权值 - 被选的B集合中的顶点的权值)，即为我们的目标函数，记为A。要想最大化目标函数A，就要尽可能使Cut小，Total是固定值，所以目标函数A取得最大值的时候，Cut最小，即为最小割。
该问题的一般模型为最大权闭合图，相关讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。
例题:
【问题描述】
W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1,E2,…,Em}，和进行这些实验需要使用的全部仪器的集合I={ I1, I2,…,In }。实验Ej 需要用到的仪器是I的子集Rj∈I。配置仪器Ik 的费用为ck 美元。实验Ej 的赞助商已同意为该实验结果支付pj 美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
【编程任务】
对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。
【数据输入】
第1行有2个正整数m和n(m,n <= 100)。m是实验数，n是仪器数。接下来的m行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。
【结果输出】
第1行是实验编号；第2行是仪器编号；最后一行是净收益。
【输入文件示例】shuttle.in
2 3
10 1 2
25 2 3
5 6 7
【输出文件示例】shuttle.out
1 2
1 2 3
17
【问题分析】
最大权闭合图问题，可以转化成最小割问题，进而用最大流解决。
【建模方法】
把每个实验看作二分图X集合中的顶点，每个设备看作二分图Y集合中的顶点，增加源S和汇T。
1、从S向每个Xi连接一条容量为该点收入的有向边。
2、从Yi向T连接一条容量为该点支出的有向边。
3、如果一个实验i需要设备j，连接一条从Xi到Yj容量为无穷大的有向边。
统计出所有实验的收入只和Total，求网络最大流Maxflow，最大收益就是Total-Maxflow。对应的解就是最小割划分出的S集合中的点，也就是最后一次增广找到阻塞流时能从S访问到的顶点。
【建模分析】
定义一个割划分出的S集合为一个解，那么割集的容量之和就是(未被选的A集合中的顶点的权值 + 被选的B集合中的顶点的权值)，记为Cut。A集合中所有顶点的权值之和记为Total，那么Total - Cut就是(被选的A集合中的顶点的权值 - 被选的B集合中的顶点的权值)，即为我们的目标函数，记为A。要想最大化目标函数A，就要尽可能使Cut小，Total是固定值，所以目标函数A取得最大值的时候，Cut最小，即为最小割。
该问题的一般模型为最大权闭合图，相关讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<iomanip>
//#define mem(dp,a) memset(dp,a,sizeof(dp))
//#define fo(i,n) for(int i=0;i<(n);i++)
//#define INF 0x3f3f3f3f
#define fread() freopen("data.txt","r",stdin)
#define fwrite() freopen("out.out","w",stdout)
using namespace std;
typedef long long ll;
vector<int> re;
int s,t;
int m,n,t1,t2;
int ans;
const int MAXN=100000,MAXM=100000,inf=1e9;
struct Edge
{
int v,c,f,nx;
Edge() {}
Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}
} E[MAXM];
int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],N,sz;
void init(int _n) //初始化
{
N=_n,sz=0; memset(G,-1,sizeof(G[0])*N);
}
void link(int u,int v,int c)//连接两个点
{
E[sz]=Edge(v,c,0,G[u]); G[u]=sz++;
E[sz]=Edge(u,0,0,G[v]); G[v]=sz++;
}
int ISAP(int S,int T)
{//S -> T
int maxflow=0,aug=inf,flag=false,u,v;
for (int i=0;i<N;++i)cur[i]=G[i],gap[i]=dis[i]=0;
for (gap[S]=N,u=pre[S]=S;dis[S]<N;flag=false)
{
for (int &it=cur[u];~it;it=E[it].nx)
{
if (E[it].c>E[it].f&&dis[u]==dis[v=E[it].v]+1)
{
if (aug>E[it].c-E[it].f) aug=E[it].c-E[it].f;
pre[v]=u,u=v; flag=true;
if (u==T)
{
for (maxflow+=aug;u!=S;)
{
E[cur[u=pre[u]]].f+=aug;
E[cur[u]^1].f-=aug;
}
aug=inf;
}
break;
}
}
if (flag) continue;
int mx=N;
for (int it=G[u];~it;it=E[it].nx)
{
if (E[it].c>E[it].f&&dis[E[it].v]<mx)
{
mx=dis[E[it].v]; cur[u]=it;
}
}
if ((--gap[dis[u]])==0) break;
++gap[dis[u]=mx+1]; u=pre[u];
}
return maxflow;
}
bool bfs(int S,int T)
{
static int Q[MAXN];
memset(dis,-1,sizeof(dis[0])*N);
dis[S]=0;
Q[0]=S;
for (int h=0,t=1,u,v,it ; h<t ; ++h)
{
for ( u=Q[h],it=G[u] ; ~it ; it=E[it].nx)
{
if (dis[v=E[it].v]==-1 && E[it].c > E[it].f)
{
dis[v]=dis[u]+1;
Q[t++]=v;
}
}
}
return dis[T]!=-1;
}
int dfs(int u,int T,int low)
{
if (u==T) return low;
int ret=0,tmp,v;
for (int &it=cur[u];~it&&ret<low;it=E[it].nx)
{
if (dis[v=E[it].v]==dis[u]+1&&E[it].c>E[it].f)
{
if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f)))
{
ret+=tmp;
E[it].f+=tmp;
E[it^1].f-=tmp;
// low -= tmp;
// if(low==0)break;
}
}
}
if (!ret) dis[u]=-1;
return ret;
}
int dinic(int S,int T)
{
int maxflow=0,tmp;
while (bfs(S,T))
{
memcpy(cur,G,sizeof(G[0])*N);
while (tmp=dfs(S,T,inf)) maxflow+=tmp;
}
return maxflow;
}
int main()
{
ios_base::sync_with_stdio(false);
// fread();
freopen("shuttle.in","r",stdin);
freopen("shuttle.out","w",stdout);
scanf("%d%d",&m,&n);
s=0; t=n+m+1;
init(t+1);
for (int i=1;i<=m;i++)
{
scanf("%d",&t1);
link(s,i,t1);
ans += t1;
for (;;)
{
do t1=getchar(); while (t1==' '); ungetc(t1,stdin);
if (t1==10 || t1==13) break;
scanf("%d",&t2);
link(i,t2+m,inf);
}
}
for (int i=1;i<=n;i++)
{
scanf("%d",&t1);
link(i+m,t,t1);
}
int tmp_ans = dinic(s,t);;
// for(int i = 0;i <=m+n;i++)
// {
// cout << dis[i]<<" ";
// }
// cout <<endl;
for(int i = 1;i <= m;++i)
if(dis[i]!=-1)
cout<<i<<" ";
cout<<endl;
for(int i = m+1;i <= m+n;++i)
if(dis[i]!=-1)
cout << i-m<<" ";
cout <<endl;
cout << ans - tmp_ans <<endl;
return 0;
}
有向无环图最小路径覆盖
【问题分析】
有向无环图最小路径覆盖，可以转化成二分图最大匹配问题，从而用最大流解决。
【建模方法】
构造二分图，把原图每个顶点i拆分成二分图X，Y集合中的两个顶点Xi和Yi。对于原图中存在的每条边(i,j)，在二分图中连接边(Xi,Yj)。然后把二分图最大匹配模型转化为网络流模型，求网络最大流。
最小路径覆盖的条数，就是原图顶点数，减去二分图最大匹配数。沿着匹配边查找，就是一个路径上的点，输出所有路径即可。
【建模分析】
对于一个路径覆盖，有如下性质：
1、每个顶点属于且只属于一个路径。
2、路径上除终点外，从每个顶点出发只有一条边指向路径上的另一顶点。
所以我们可以把每个顶点理解成两个顶点，一个是出发，一个是目标，建立二分图模型。该二分图的任何一个匹配方案，都对应了一个路径覆盖方案。如果匹配数为0，那么显然路径数=顶点数。每增加一条匹配边，那么路径覆盖数就减少一个，所以路径数=顶点数 - 匹配数。要想使路径数最少，则应最大化匹配数，所以要求二分图的最大匹配。
注意，此建模方法求最小路径覆盖仅适用于有向无环图，如果有环或是无向图，那么有可能求出的一些环覆盖，而不是路径覆盖。
例题:
- [网络流24题] 最小路径覆盖问题
★★☆ 输入文件：path3.in 输出文件：path3.out 评测插件
时间限制：1 s 内存限制：128 MB
算法实现题8-3 最小路径覆盖问题（习题8-13）
´问题描述：
给定有向图G=(V,E)。设P是G的一个简单路（顶点不相交）的集合。如果V中每个
顶点恰好在P的一条路上，则称P是G的一个路径覆盖。P中路径可以从V的任何一个顶
点开始，长度也是任意的，特别地，可以为0。G的最小路径覆盖是G的所含路径条数最少
的路径覆盖。
设计一个有效算法求一个有向无环图G的最小路径覆盖。
提示：
设V={1，2，… ，n}，构造网络G1=(V1,E1)如下：
每条边的容量均为1。求网络G1的(x0,y0)最大流。
´编程任务：
对于给定的给定有向无环图G，编程找出G的一个最小路径覆盖。
´数据输入：
由文件input.txt提供输入数据。文件第1行有2个正整数n和m。n是给定有向无环图
G的顶点数，m是G的边数。接下来的m行，每行有2个正整数i 和j，表示一条有向边(i,j)。
´结果输出:
程序运行结束时，将最小路径覆盖输出到文件output.txt中。从第1行开始，每行输出
一条路径。文件的最后一行是最少路径数。
【问题分析】
有向无环图最小路径覆盖，可以转化成二分图最大匹配问题，从而用最大流解决。
【建模方法】
构造二分图，把原图每个顶点i拆分成二分图X，Y集合中的两个顶点Xi和Yi。对于原图中存在的每条边(i,j)，在二分图中连接边(Xi,Yj)。然后把二分图最大匹配模型转化为网络流模型，求网络最大流。
最小路径覆盖的条数，就是原图顶点数，减去二分图最大匹配数。沿着匹配边查找，就是一个路径上的点，输出所有路径即可。
【建模分析】
对于一个路径覆盖，有如下性质：
1、每个顶点属于且只属于一个路径。
2、路径上除终点外，从每个顶点出发只有一条边指向路径上的另一顶点。
所以我们可以把每个顶点理解成两个顶点，一个是出发，一个是目标，建立二分图模型。该二分图的任何一个匹配方案，都对应了一个路径覆盖方案。如果匹配数为0，那么显然路径数=顶点数。每增加一条匹配边，那么路径覆盖数就减少一个，所以路径数=顶点数 - 匹配数。要想使路径数最少，则应最大化匹配数，所以要求二分图的最大匹配。
注意，此建模方法求最小路径覆盖仅适用于有向无环图，如果有环或是无向图，那么有可能求出的一些环覆盖，而不是路径覆盖。
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<iomanip>
//#define mem(dp,a) memset(dp,a,sizeof(dp))
//#define fo(i,n) for(int i=0;i<(n);i++)
//#define INF 0x3f3f3f3f
#define fread() freopen("data.txt","r",stdin)
#define fwrite() freopen("out.out","w",stdout)
using namespace std;
typedef long long ll;
vector<int> re;
int s,t;
int m,n,t1,t2;
int ans;
const int MAXN=100000,MAXM=100000,inf=1e9;
struct Edge
{
int v,c,f,nx;
Edge() {}
Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}
} E[MAXM];
int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],N,sz;
int tonex[MAXN];//记录下一个节点
bool vis[MAXN];//
//dis[]层次
void init(int _n) //初始化
{
N=_n,sz=0; memset(G,-1,sizeof(G[0])*N);
}
void link(int u,int v,int c)//连接两个点
{
E[sz]=Edge(v,c,0,G[u]); G[u]=sz++;
E[sz]=Edge(u,0,0,G[v]); G[v]=sz++;
}
int ISAP(int S,int T)
{//S -> T
int maxflow=0,aug=inf,flag=false,u,v;
for (int i=0;i<N;++i)cur[i]=G[i],gap[i]=dis[i]=0;
for (gap[S]=N,u=pre[S]=S;dis[S]<N;flag=false)
{
for (int &it=cur[u];~it;it=E[it].nx)
{
if (E[it].c>E[it].f&&dis[u]==dis[v=E[it].v]+1)
{
if (aug>E[it].c-E[it].f) aug=E[it].c-E[it].f;
pre[v]=u,u=v; flag=true;
if (u==T)
{
for (maxflow+=aug;u!=S;)
{
E[cur[u=pre[u]]].f+=aug;
E[cur[u]^1].f-=aug;
}
aug=inf;
}
break;
}
}
if (flag) continue;
int mx=N;
for (int it=G[u];~it;it=E[it].nx)
{
if (E[it].c>E[it].f&&dis[E[it].v]<mx)
{
mx=dis[E[it].v]; cur[u]=it;
}
}
if ((--gap[dis[u]])==0) break;
++gap[dis[u]=mx+1]; u=pre[u];
}
return maxflow;
}
bool bfs(int S,int T)
{
static int Q[MAXN];
memset(dis,-1,sizeof(dis[0])*N);
dis[S]=0;
Q[0]=S;
//dis[i]为-1表示没有
for (int h=0,t=1,u,v,it ; h<t ; ++h)
{
for ( u=Q[h],it=G[u] ; ~it ; it=E[it].nx)
{
if (dis[v=E[it].v]==-1 && E[it].c > E[it].f)
{
dis[v]=dis[u]+1;
Q[t++]=v;
}
}
}
return dis[T]!=-1;
}
int dfs(int u,int T,int low)
{
if (u==T) return low;
int ret=0,tmp,v;
for (int &it=cur[u];~it&&ret<low;it=E[it].nx)
{
if (dis[v=E[it].v]==dis[u]+1&&E[it].c>E[it].f)
{
if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f)))
{
if(v-n>0) vis[v-n]=1;
tonex[u] = v;
ret+=tmp;
E[it].f+=tmp;
E[it^1].f-=tmp;
// low -= tmp;
// if(low==0)break;
}
}
}
if (!ret) dis[u]=-1;
return ret;
}
int dinic(int S,int T)
{
int maxflow=0,tmp;
while (bfs(S,T))
{
memcpy(cur,G,sizeof(G[0])*N);
while (tmp=dfs(S,T,inf)) maxflow+=tmp;
}
return maxflow;
}
int main()
{
ios_base::sync_with_stdio(false);
// fread();
freopen("path3.in","r",stdin);
freopen("path3.out","w",stdout);
cin >> n>> m;
s=0; t=n+n+1;
init(t+1);
for(int i=1;i<=n;i++)
{
link(s,i,1);
}
for(int i=n+1;i<=2*n;i++)
{
link(i,t,1);
}
for(int i = 0 ;i < m;i++)
{
cin >> t1 >> t2;
link(t1,t2+n,inf);
}
int tmp_ans = dinic(s,t);
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
cout<<i;
int k=i;
while(tonex[k])
{
cout<<" "<<tonex[k]-n;
k=tonex[k]-n;
}
cout<<endl;
}
cout << n - tmp_ans <<endl;
return 0;
}
二分图多重匹配
【问题分析】
二分图多重匹配问题，可以用最大流解决。
【建模方法】
建立二分图，每个单位为X集合中的顶点，每个餐桌为Y集合中的顶点，增设附加源S和汇T。
1、从S向每个Xi顶点连接一条容量为该单位人数的有向边。
2、从每个Yi顶点向T连接一条容量为该餐桌容量的有向边。
3、X集合中每个顶点向Y集合中每个顶点连接一条容量为1的有向边。
求网络最大流，如果最大流量等于所有单位人数之和，则存在解，否则无解。对于每个单位，从X集合对应点出发的所有满流边指向的Y集合的顶点就是该单位人员的安排情况（一个可行解）。
【建模分析】
对于一个二分图，每个顶点可以有多个匹配顶点，称这类问题为二分图多重匹配问题。X，Y集合之间的边容量全部是1，保证两个点只能匹配一次（一个餐桌上只能有一个单位的一个人），源汇的连边限制了每个点匹配的个数。求出网络最大流，如果流量等于X集合所有点与S边容量之和，那么则说明X集合每个点都有完备的多重匹配。
【问题另解】
贪心，更好的方法其实是贪心。首先把所有单位和餐桌按人数从大到小排序，一种适当的贪心策略就是对于每个单位，所有人每次尽量去剩余容量较大的餐桌就坐。按照这种贪心策略，如果某时发现有人已经无法就坐，则无解。具体方法为用线段树维护餐桌的剩余容量，按人数从多到少安排每个单位的人员，每次安排就是把容量餐桌前k大的餐桌人数减1（k为该单位人数）。为保证线段树前k位时刻为前k大，要维护第k与第k+1,k+2,…人数与第k相等的位置，减少第k大时要减少尽量靠后的，这样才能保证单调。
例题:
[网络流24题] 圆桌聚餐
★★☆ 输入文件：roundtable.in 输出文件：roundtable.out 评测插件
时间限制：1 s 内存限制：128 MB
«问题描述：
假设有来自m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为
ri(i=1,2,3…m), 。会议餐厅共有n张餐桌，每张餐桌可容纳c i(i=1,2…n) 个代表就餐。
为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，
给出满足要求的代表就餐方案。
«编程任务：
对于给定的代表数和餐桌数以及餐桌容量，编程计算满足要求的代表就餐方案。
«数据输入：
由文件roundtable.in提供输入数据。文件第1行有2 个正整数m和n，m表示单位数，n表
示餐桌数，1<=m<=150, 1<=n<=270。文件第2 行有m个正整数，分别表示每个单位的代表
数。文件第3 行有n个正整数，分别表示每个餐桌的容量。
«结果输出:
程序运行结束时，将代表就餐方案输出到文件roundtable.out中。如果问题有解，在文件第
1 行输出1，否则输出0。接下来的m行给出每个单位代表的就餐桌号。如果有多个满足要
求的方案，只要输出1 个方案。
输入文件示例 输出文件示例
roundtable.in
4 5
4 5 3 5
3 5 2 6 4 roundtable.out
1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5
【问题分析】
二分图多重匹配问题，可以用最大流解决。
【建模方法】
建立二分图，每个单位为X集合中的顶点，每个餐桌为Y集合中的顶点，增设附加源S和汇T。
1、从S向每个Xi顶点连接一条容量为该单位人数的有向边。
2、从每个Yi顶点向T连接一条容量为该餐桌容量的有向边。
3、X集合中每个顶点向Y集合中每个顶点连接一条容量为1的有向边。
求网络最大流，如果最大流量等于所有单位人数之和，则存在解，否则无解。对于每个单位，从X集合对应点出发的所有满流边指向的Y集合的顶点就是该单位人员的安排情况（一个可行解）。
【建模分析】
对于一个二分图，每个顶点可以有多个匹配顶点，称这类问题为二分图多重匹配问题。X，Y集合之间的边容量全部是1，保证两个点只能匹配一次（一个餐桌上只能有一个单位的一个人），源汇的连边限制了每个点匹配的个数。求出网络最大流，如果流量等于X集合所有点与S边容量之和，那么则说明X集合每个点都有完备的多重匹配。
【问题另解】
贪心，更好的方法其实是贪心。首先把所有单位和餐桌按人数从大到小排序，一种适当的贪心策略就是对于每个单位，所有人每次尽量去剩余容量较大的餐桌就坐。按照这种贪心策略，如果某时发现有人已经无法就坐，则无解。具体方法为用线段树维护餐桌的剩余容量，按人数从多到少安排每个单位的人员，每次安排就是把容量餐桌前k大的餐桌人数减1（k为该单位人数）。为保证线段树前k位时刻为前k大，要维护第k与第k+1,k+2,…人数与第k相等的位置，减少第k大时要减少尽量靠后的，这样才能保证单调。
#include<bits/stdc++.h>
#define MAXN 510
#define MAXM 100000
#define INF 0x3f3f3f3f
using namespace std;
struct Edge
{
int from, to, cap, flow, next;
};
Edge edge[MAXM];
int head[MAXN], cur[MAXN], edgenum;
int dist[MAXN];
bool vis[MAXN];
int N, M,ss,tt;
void init()
{
edgenum = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int w)
{
Edge E1 = {u, v, w, 0, head[u]};
edge[edgenum] = E1;
head[u] = edgenum++;
Edge E2 = {v, u, 0, 0, head[v]};
edge[edgenum] = E2;
head[v] = edgenum++;
}
bool BFS(int s, int t)
{
queue<int> Q;
memset(dist, -1, sizeof(dist));
memset(vis, false, sizeof(vis));
dist[s] = 0;
vis[s] = true;
Q.push(s);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
for(int i = head[u]; i != -1; i = edge[i].next)
{
Edge E = edge[i];
if(!vis[E.to] && E.cap > E.flow)
{
dist[E.to] = dist[u] + 1;
if(E.to == t) return true;
vis[E.to] = true;
Q.push(E.to);
}
}
}
return false;
}
int DFS(int x, int a, int t)
{
if(x == t || a == 0) return a;
int flow = 0, f;
for(int &i = cur[x]; i != -1; i = edge[i].next)
{
Edge &E = edge[i];
if(dist[E.to] == dist[x] + 1 && (f = DFS(E.to, min(a, E.cap - E.flow), t)) > 0)
{
edge[i].flow += f;
edge[i^1].flow -= f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
int Maxflow(int s, int t)
{
int flow = 0;
while(BFS(s, t))
{
memcpy(cur, head, sizeof(head));
flow += DFS(s, INF, t);
}
return flow;
}
int T;
int n,m,t;
int main()
{
freopen("roundtable.in","r",stdin);
freopen("roundtable.out","w",stdout);
// scanf("%d", &T);
// while(T--)
// {
//
// }
int sum = 0;
int ss,tt;
scanf("%d%d", &m, &n);
ss=0,tt=m+n+1;
init();
for(int i=1;i<=m;i++)
{
scanf("%d",&t);
sum+=t;
addEdge(0,i,t);
for(int j=m+1;j<=n+m;j++)
{
addEdge(i,j,1);
}
}
for(int j=m+1;j<=n+m;j++)
{
scanf("%d",&t);
addEdge(j,tt,t);
}
if(Maxflow(ss, tt)<sum)
{
printf("%d\n",0);
}
else
{
printf("%d\n",1);
for(int i=1;i<=m;i++)
{
for(int j = head[i]; j != -1; j = edge[j].next)
{
if(edge[j].flow==1)
{
printf("%d ",edge[j].to-m);
}
}
printf("\n");
}
}
return 0;
}
最多不相交路径
【问题分析】
第一问时LIS，动态规划求解，第二问和第三问用网络最大流解决。
【建模方法】
首先动态规划求出F[i]，表示以第i位为开头的最长上升序列的长度，求出最长上升序列长度K。
1、把序列每位i拆成两个点
例题:
给定正整数序列x1,….. , xn 。
（1）计算其最长递增子序列的长度s。
（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。
（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长
度为s的递增子序列。
【问题分析】
第一问时LIS，动态规划求解，第二问和第三问用网络最大流解决。
【建模方法】
首先动态规划求出F[i]，表示以第i位为开头的最长上升序列的长度，求出最长上升序列长度K。
1、把序列每位i拆成两个点
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 100010
#define MAXM 10000000+10
#define INF 0x3f3f3f3f
struct Edge
{
int from, to, cap, flow, next;
};
Edge edge[MAXM];
int head[MAXN], cur[MAXN], edgenum;
int dist[MAXN];
bool vis[MAXN];
int N, M,ss,tt;
void init()
{
edgenum = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int w)
{
Edge E1 = {u, v, w, 0, head[u]};
edge[edgenum] = E1;
head[u] = edgenum++;
Edge E2 = {v, u, 0, 0, head[v]};
edge[edgenum] = E2;
head[v] = edgenum++;
}
bool BFS(int s, int t)
{
queue<int> Q;
memset(dist, -1, sizeof(dist));
memset(vis, false, sizeof(vis));
dist[s] = 0;
vis[s] = true;
Q.push(s);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
for(int i = head[u]; i != -1; i = edge[i].next)
{
Edge E = edge[i];
if(!vis[E.to] && E.cap > E.flow)
{
dist[E.to] = dist[u] + 1;
if(E.to == t) return true;
vis[E.to] = true;
Q.push(E.to);
}
}
}
return false;
}
int DFS(int x, int a, int t)
{
if(x == t || a == 0) return a;
int flow = 0, f;
for(int &i = cur[x]; i != -1; i = edge[i].next)
{
Edge &E = edge[i];
if(dist[E.to] == dist[x] + 1 && (f = DFS(E.to, min(a, E.cap - E.flow), t)) > 0)
{
edge[i].flow += f;
edge[i^1].flow -= f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
int Maxflow(int s, int t)
{
int flow = 0;
while(BFS(s, t))
{
memcpy(cur, head, sizeof(head));
flow += DFS(s, INF, t);
}
return flow;
}
int n;
int a[100005];
int dp[100005];
int main()
{
freopen("data.txt","r",stdin);
ios_base::sync_with_stdio(false);
cin >> n;
int s = 0;
int t = n+n+1;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
dp[1]=1;
for(int i=2;i<=n;i++)
{
dp[i]=1;
for(int j=1;j<i;j++)
{
if(a[i]>=a[j])
{
dp[i] = max(dp[i],dp[j]+1);
}
}
}
int ans = *max_element(dp+1,dp+1+n);
cout << ans<<endl;
init();
for(int i=1;i<=n;i++)
{
addEdge(i,i+n,1);
}
for(int i=1;i<=n;i++)
{
if(dp[i]==ans)
{
addEdge(s,i,1);
}
if(dp[i]==1)
{
addEdge(i+n,t,1);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[i]>=a[j]&& dp[i] == dp[j]+1)
{
addEdge(i+n,j,1);
}
}
}
cout << Maxflow(s,t)<<endl;
init();
for(int i=1;i<=n;i++)
{
int fl=1;
if(i==1||i==n) fl=INF;
addEdge(i,i+n,fl);
}
for(int i=1;i<=n;i++)
{
if(dp[i]==ans)
{
if(i==n)
addEdge(s,i,INF);
else
addEdge(s,i,1);
}
if(dp[i]==1)
{
if(i==1)
addEdge(i+n,t,INF);
else
addEdge(i+n,t,1);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[i]>=a[j]&& dp[i] == dp[j]+1)
{
addEdge(i+n,j,1);
}
}
}
cout << Maxflow(s,t)<<endl;
return 0;
}
二分图点权最大独立集
【问题分析】
二分图点权最大独立集，转化为最小割模型，从而用最大流解决。
【建模方法】
首先把棋盘黑白染色，使相邻格子颜色不同，所有黑色格子看做二分图X集合中顶点，白色格子看做Y集合顶点，建立附加源S汇T。
1、从S向X集合中每个顶点连接一条容量为格子中数值的有向边。
2、从Y集合中每个顶点向T连接一条容量为格子中数值的有向边。
3、相邻黑白格子Xi,Yj之间从Xi向Yj连接一条容量为无穷大的有向边。
求出网络最大流，要求的结果就是所有格子中数值之和减去最大流量。
【建模分析】
这是一个二分图最大点权独立集问题，就是找出图中一些点，使得这些点之间没有边相连，这些点的权值之和最大。独立集与覆盖集是互补的，求最大点权独立集可以转化为求最小点权覆盖集（最小点权支配集）。最小点权覆盖集问题可以转化为最小割问题解决。结论:最大点权独立集 = 所有点权 - 最小点权覆盖集 = 所有点权 - 最小割集 = 所有点权 - 网络最大流。
对于一个网络，除去冗余点（不存在一条ST路径经过的点），每个顶点都在一个从S到T的路径上。割的性质就是不存在从S到T的路径，简单割可以认为割边关联的非ST节点为割点，而在二分图网络流模型中每个点必关联到一个割点（否则一定还有增广路，当前割不成立），所以一个割集对应了一个覆盖集（支配集）。最小点权覆盖集就是最小简单割，求最小简单割的建模方法就是把XY集合之间的变容量设为无穷大，此时的最小割就是最小简单割了。
有关二分图最大点权独立集问题，更多讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。
例题:
«问题描述：
在一个有m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任
意2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。
«编程任务：
对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
【问题分析】
二分图点权最大独立集，转化为最小割模型，从而用最大流解决。
【建模方法】
首先把棋盘黑白染色，使相邻格子颜色不同，所有黑色格子看做二分图X集合中顶点，白色格子看做Y集合顶点，建立附加源S汇T。
1、从S向X集合中每个顶点连接一条容量为格子中数值的有向边。
2、从Y集合中每个顶点向T连接一条容量为格子中数值的有向边。
3、相邻黑白格子Xi,Yj之间从Xi向Yj连接一条容量为无穷大的有向边。
求出网络最大流，要求的结果就是所有格子中数值之和减去最大流量。
【建模分析】
这是一个二分图最大点权独立集问题，就是找出图中一些点，使得这些点之间没有边相连，这些点的权值之和最大。独立集与覆盖集是互补的，求最大点权独立集可以转化为求最小点权覆盖集（最小点权支配集）。最小点权覆盖集问题可以转化为最小割问题解决。结论:最大点权独立集 = 所有点权 - 最小点权覆盖集 = 所有点权 - 最小割集 = 所有点权 - 网络最大流。
对于一个网络，除去冗余点（不存在一条ST路径经过的点），每个顶点都在一个从S到T的路径上。割的性质就是不存在从S到T的路径，简单割可以认为割边关联的非ST节点为割点，而在二分图网络流模型中每个点必关联到一个割点（否则一定还有增广路，当前割不成立），所以一个割集对应了一个覆盖集（支配集）。最小点权覆盖集就是最小简单割，求最小简单割的建模方法就是把XY集合之间的变容量设为无穷大，此时的最小割就是最小简单割了。
有关二分图最大点权独立集问题，更多讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。
#include<bits/stdc++.h>
#define MAXN 1010
#define MAXM 10000100
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 100005;
int mm[1005][1005];
int n,m;
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int col[1005][1005];
struct Edge
{
int from, to, cap, flow, next;
};
Edge edge[MAXM];
int head[MAXN], cur[MAXN], edgenum;
int dist[MAXN];
bool vis[MAXN];
int N, M,ss,tt;
void init()
{
edgenum = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int w)
{
Edge E1 = {u, v, w, 0, head[u]};
edge[edgenum] = E1;
head[u] = edgenum++;
Edge E2 = {v, u, 0, 0, head[v]};
edge[edgenum] = E2;
head[v] = edgenum++;
}
bool BFS(int s, int t)
{
queue<int> Q;
memset(dist, -1, sizeof(dist));
memset(vis, false, sizeof(vis));
dist[s] = 0;
vis[s] = true;
Q.push(s);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
for(int i = head[u]; i != -1; i = edge[i].next)
{
Edge E = edge[i];
if(!vis[E.to] && E.cap > E.flow)
{
dist[E.to] = dist[u] + 1;
if(E.to == t) return true;
vis[E.to] = true;
Q.push(E.to);
}
}
}
return false;
}
int DFS(int x, int a, int t)
{
if(x == t || a == 0) return a;
int flow = 0, f;
for(int &i = cur[x]; i != -1; i = edge[i].next)
{
Edge &E = edge[i];
if(dist[E.to] == dist[x] + 1 && (f = DFS(E.to, min(a, E.cap - E.flow), t)) > 0)
{
edge[i].flow += f;
edge[i^1].flow -= f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
int Maxflow(int s, int t)
{
int flow = 0;
while(BFS(s, t))
{
memcpy(cur, head, sizeof(head));
flow += DFS(s, INF, t);
}
return flow;
}
void dfs(int x,int y,int cl)
{
col[x][y]=cl;
for(int i=0;i<4;i++)
{
int xx = x+dir[i][0];
int yy = y+dir[i][1];
if(xx<1 || xx>n||yy<1||yy>m||col[xx][yy]) continue;
if(cl==1)
dfs(xx,yy,2);
else
dfs(xx,yy,1);
}
}
int getnum(int x,int y)
{
return (x-1)*m+y;
}
int main()
{
// freopen("data.txt","r",stdin);
// ios_base::sync_with_stdio(false);
// int T;
// scanf("%d",&T);
while(scanf("%d%d",&n,&m)==2)
{
int ans = 0;
memset(col,0,sizeof(col));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&mm[i][j]);
ans+=mm[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!col[i][j])
{
dfs(i,j,1);
}
}
}
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=m;j++)
// {
// cout << col[i][j]<<" ";
// }
// cout <<endl;
// }
init();
ss = 0;
tt = n*m+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(col[i][j]==1)
{
addEdge(ss,getnum(i,j),mm[i][j]);
for(int d=0;d<4;d++)
{
int xx = i+dir[d][0];
int yy = j+dir[d][1];
if(xx<1 || xx>n || yy<1 || yy>m ||col[xx][yy]==1) continue;
addEdge(getnum(i,j),getnum(xx,yy),INF);
}
}
else
{
addEdge(getnum(i,j),tt,mm[i][j]);
}
}
}
printf("%d\n",ans-Maxflow(ss,tt));
}
return 0;
}
线性规划网络优化
【问题分析】
网络优化问题，用最小费用最大流解决。
【建模方法】
把每天分为二分图两个集合中的顶点Xi,Yi，建立附加源S汇T。
1、从S向每个Xi连一条容量为ri，费用为0的有向边。
2、从每个Yi向T连一条容量为ri，费用为0的有向边。
3、从S向每个Yi连一条容量为无穷大，费用为p的有向边。
4、从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大，费用为0的有向边。
5、从每个Xi向Yi+m(i+m<=N)连一条容量为无穷大，费用为f的有向边。
6、从每个Xi向Yi+n(i+n<=N)连一条容量为无穷大，费用为s的有向边。
求网络最小费用最大流，费用流值就是要求的最小总花费。
【建模分析】
这个问题的主要约束条件是每天的餐巾够用，而餐巾的来源可能是最新购买，也可能是前几天送洗，今天刚刚洗好的餐巾。每天用完的餐巾可以选择送到快洗部或慢洗部，或者留到下一天再处理。
经过分析可以把每天要用的和用完的分离开处理，建模后就是二分图。二分图X集合中顶点Xi表示第i天用完的餐巾，其数量为ri，所以从S向Xi连接容量为ri的边作为限制。Y集合中每个点Yi则是第i天需要的餐巾，数量为ri，与T连接的边容量作为限制。每天用完的餐巾可以选择留到下一天（Xi->Xi+1），不需要花费，送到快洗部(Xi->Yi+m)，费用为f，送到慢洗部(Xi->Yi+n)，费用为s。每天需要的餐巾除了刚刚洗好的餐巾，还可能是新购买的(S->Yi)，费用为p。
在网络上求出的最小费用最大流，满足了问题的约束条件（因为在这个图上最大流一定可以使与T连接的边全部满流，其他边只要有可行流就满足条件），而且还可以保证总费用最小，就是我们的优化目标。
例题:
题目描述 Description
一个餐厅在相继的 N 天里，每天需用的餐巾数不尽相同。假设第 i 天需要 ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为 p 分；或者把旧餐巾送到快洗部，洗一块需 m 天，其费用为 f 分；或者送到慢洗部，洗一块需 n 天(n>m)，其费用为 s
#include<iostream>
#include<cstdio>
#define inf 0x7fffffff
#define T 2001
using namespace std;
int cnt=1,day,p,m,f,n,s,ans;
int from[2005],q[2005],dis[2005],head[2005];
bool inq[2005];
struct data{int from,to,next,v,c;}e[1000001];
void ins(int u,int v,int w,int c)
{
cnt++;
e[cnt].from=u;e[cnt].to=v;
e[cnt].v=w;e[cnt].c=c;
e[cnt].next=head[u];head[u]=cnt;
}
void insert(int u,int v,int w,int c)
{ins(u,v,w,c);ins(v,u,0,-c);}
bool spfa()
{
for(int i=0;i<=T;i++)dis[i]=inf;
int t=0,w=1,i,now;
dis[0]=q[0]=0;inq[0]=1;
while(t!=w)
{
now=q[t];t++;if(t==2001)t=0;
for(int i=head[now];i;i=e[i].next)
{
if(e[i].v&&dis[e[i].to]>dis[now]+e[i].c)
{
from[e[i].to]=i;
dis[e[i].to]=dis[now]+e[i].c;
if(!inq[e[i].to])
{
inq[e[i].to]=1;
q[w++]=e[i].to;
if(w==2001)w=0;
}
}
}
inq[now]=0;
}
if(dis[T]==inf)return 0;return 1;
}
void mcf()
{
int i,x=inf;
i=from[T];
while(i)
{
x=min(e[i].v,x);
i=from[e[i].from];
}
i=from[T];
while(i)
{
e[i].v-=x;
e[i^1].v+=x;
ans+=x*e[i].c;
i=from[e[i].from];
}
}
int main()
{
scanf("%d%d%d%d%d%d",&day,&p,&m,&f,&n,&s);
for(int i=1;i<=day;i++)
{
if(i+1<=day)insert(i,i+1,inf,0);
if(i+m<=day)insert(i,day+i+m,inf,f);
if(i+n<=day)insert(i,day+i+n,inf,s);
insert(0,day+i,inf,p);
}
int x;
for(int i=1;i<=day;i++)
{
scanf("%d",&x);
insert(0,i,x,0);
insert(day+i,T,x,0);
}
while(spfa())mcf();
printf("%d",ans);
return 0;
}最长不相交路径
【问题分析】
求最长两条不相交路径，用最大费用最大流解决。
【建模方法】
把第i个城市拆分成两个顶点
例题:
问题描述：
给定一张航空图，图中顶点代表城市，边代表 2 城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。
1 从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东
向西飞回起点(可途经若干城市)。
2 除起点城市外，任何城市只能访问 1 次。
编程任务：
对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。
数据输入：
第 1 行有 2 个正整数 N 和 V ， N 表示城市数， N<100 ， V 表示直飞航线数。接下来的 N 行中每一行是一个城市名，可乘飞机访问这些城市。城市名出现的顺序是从西向东。也就是说，设 i,j 是城市表列中城市出现的顺序，当 i>j 时，表示城市 i 在城市 j 的东边，而且不会有 2 个城市在同一条经线上。城市名是一个长度不超过 15 的字符串，串中的字符可以是字母或阿拉伯数字。例如， AGR34 或 BEL4 。
再接下来的 V 行中，每行有 2 个城市名，中间用空格隔开，如 city1 city2 表示 city1到 city2 有一条直通航线，从 city2 到 city1 也有一条直通航线。
结果输出：
输出第 1 行是旅行路线中所访问的城市总数 M 。接下来的 M＋1 行是旅行路线的城市名，每行写 1 个城市名。首先是出发城市名，然后按访问顺序列出其它城市名。注意，最后 1 行（终点城市）的城市名必然是出发城市名。如果问题无解，则输出“ No Solution! ” 。
输入文件示例：
8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary
输出文件示例：
7
Va
ncouver
Edmonton
Montreal
Halifax
To
ronto
Winnipeg
Calgary
Va
ncouver
【问题分析】
求最长两条不相交路径，用最大费用最大流解决。
【建模方法】
把第i个城市拆分成两个顶点
/*
* Problem: 线性规划与网络流24题 #11 航空路线问题
* Author: Guo Jiabao
* Time: 2009.6.28 16:54
* State: Solved
* Memo: 最大费用最大流
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=1001,MAXM=MAXN*4*2,INF=~0U>>1;
struct Queue
{
int Q[MAXN],head,tail,size;
bool inq[MAXN];
void init()
{
memset(inq,0,sizeof(inq));
head = size =0; tail = -1;
}
void ins(int p)
{
size++;
if (++tail == MAXN) tail = 0;
Q[tail] = p;
inq[p]=true;
}
int pop()
{
size--;
int p=Q[head];
if (++head == MAXN) head = 0;
inq[p]=false;
return p;
}
}Q;
struct edge
{
edge *next,*op;
int t,c,v;
}*V[MAXN],ES[MAXM],*fe[MAXN];
char City[MAXN][16];
int N,M,S,T,EC,Ans,Costflow;
int dist[MAXN],ft[MAXN];
inline void addedge(int a,int b,int c,int v)
{
ES[++EC].next = V[a]; V[a]=ES+EC; V[a]->t=b; V[a]->c=c; V[a]->v=v;
ES[++EC].next = V[b]; V[b]=ES+EC; V[b]->t=a; V[b]->c=0; V[b]->v=-v;
V[a]->op = V[b]; V[b]->op = V[a];
}
int getcity(char *s)
{
for (int i=1;i<=N;i++)
if (strcmp(s,City[i])==0)
return i;
return -1;
}
void init()
{
int i,a,b;
char name[16];
freopen("airl.in","r",stdin);
freopen("airl.out","w",stdout);
scanf("%d%d",&N,&M);
for (i=1;i<=N;i++)
{
scanf("%s",City[i]);
if (i==1 || i==N)
addedge(i,i+N,2,-1);
else
addedge(i,i+N,1,-1);
}
for (i=1;i<=M;i++)
{
scanf("%s",name);a=getcity(name);
scanf("%s",name);b=getcity(name);
if (a<b)
addedge(a+N,b,1,0);
else
addedge(b+N,a,1,0);
}
S=1; T=N+N;
}
bool SPFA()
{
int i,j;
for (i=S;i<=T;i++)
dist[i]=INF;
dist[S]=0;
Q.ins(S);
while (Q.size)
{
i=Q.pop();
for (edge *e=V[i];e;e=e->next)
{
j=e->t;
if (e->c && dist[i] + e->v < dist[j])
{
dist[j] = dist[i] + e->v;
ft[j] = i;
fe[j] = e;
if (!Q.inq[j])
Q.ins(j);
}
}
}
return dist[T]!=INF;
}
void Augment()
{
int i,delta=INF;
for (i=T;i!=S;i=ft[i])
if (fe[i]->c < delta)
delta = fe[i]->c;
for (i=T;i!=S;i=ft[i])
{
fe[i]->c -= delta;
fe[i]->op->c += delta;
Costflow += fe[i]->v * delta;
}
}
void SPFAFlow()
{
Q.init();
while (SPFA())
Augment();
}
int main()
{
init();
SPFAFlow();
Costflow =-Costflow;
Costflow -= 2;
if (ES[1].c!=0)
Costflow = 1;
printf("%d\n",Costflow);
return 0;
}
最小转移代价
【问题分析】
求一个状态到另一个状态变换的最少费用，最短路径问题。
【建模方法】
软件的状态用二进制位表示，第i位为第i个错误是否存在。把每个状态看做一个顶点，一个状态应用一个补丁到达另一状态，连接一条权值为补丁时间的有向边。求从初始状态到目标状态的最短路径即可。
例题:
T 公司发现其研制的一个软件中有 n 个错误， 随即为该软件发放了一批共 m 个补丁程
序。 每一个补丁程序都有其特定的适用环境， 某个补丁只有在软件中包含某些错误而同时又
不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时， 往往会加入另一些错误。
换句话说， 对于每一个补丁 i， 都有 2 个与之相应的错误集合 B1[i]和 B2[i]，使得仅当软件
包含 B1[i]中的所有错误， 而不包含 B2[i]中的任何错误时， 才可以使用补丁 i。 补丁 i 将修复
软件中的某些错误 F1[i]， 而同时加入另一些错误 F2[i]。 另外， 每个补丁都耗费一定的时间。
试设计一个算法， 利用 T 公司提供的 m 个补丁程序将原软件修复成一个没有错误的软
件， 并使修复后的软件耗时最少。
输入文件示例
input.txt
3 3
1 000 00-
1 00- 0-+
2 0– -++
输出文件示例
output.txt
8
【分析】
sm网络流24题，怎么什么题都有。
明明就是一道最短路，就spfa就好了。。。
最小转移代价，但是没什么约束，所以用不着流，直接费用跑过。。
【问题分析】
求一个状态到另一个状态变换的最少费用，最短路径问题。
【建模方法】
软件的状态用二进制位表示，第i位为第i个错误是否存在。把每个状态看做一个顶点，一个状态应用一个补丁到达另一状态，连接一条权值为补丁时间的有向边。求从初始状态到目标状态的最短路径即可。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
#define Maxm 110
#define Maxn 1100000
#define INF 0xfffffff
int w[Maxm],b1[Maxm],b2[Maxm],f1[Maxm],f2[Maxm];
int dis[Maxn];
bool inq[Maxn];
queue<int > q;
int st,ed,n,m;
void spfa()
{
while(!q.empty()) q.pop();
memset(dis,63,sizeof(dis));
memset(inq,0,sizeof(inq));
q.push(st);dis[st]=0;inq[st]=1;
while(!q.empty())
{
int x=q.front();
for(int i=1;i<=m;i++) if((x&b1[i])==b1[i]&&(x&b2[i])==0)
{
int y=x-(x&f1[i]);
y|=f2[i];
if(dis[y]>dis[x]+w[i])
{
dis[y]=dis[x]+w[i];
if(!inq[y])
{
q.push(y);
inq[y]=1;
}
}
}
q.pop();inq[x]=0;
}
}
char s[30];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&w[i]);
scanf("%s",s);
b1[i]=b2[i]=f1[i]=f2[i]=0;
for(int j=0;j<n;j++)
if(s[j]=='+') b1[i]+=1<<j;
else if(s[j]=='-') b2[i]+=1<<j;
scanf("%s",s);
for(int j=0;j<n;j++)
if(s[j]=='-') f1[i]+=1<<j;
else if(s[j]=='+') f2[i]+=1<<j;
}
st=(1<<n)-1;ed=0;
spfa();
if(dis[ed]>=INF-100000) printf("0\n");
else printf("%d\n",dis[ed]);
return 0;
}网络判定
【问题分析】
分层图网络流问题，枚举答案，构造网络流判定。
【建模方法】
首先判断从地球到月球是否存在一条路线，如果不存在那么无解，否则把每个太空站按照每天拆分成d个点，
/*
* Problem: 线性规划与网络流24题 #13 星际转移问题
* Author: Guo Jiabao
* Time: 2009.6.28 19:36
* State: Solved
* Memo: 分层图网络最大流 枚举答案
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=20*50,MAXM=MAXN*20,INF=~0U>>1;
struct UFS
{
int f[MAXN];
void init(int N)
{
for (int i=1;i<=N;i++)
f[i]=i;
}
int getroot(int a)
{
int r=a,t;
while (r!=f[r]) r=f[r];
while (a!=r)
{
t=f[a];
f[a]=r;
a=t;
}
return r;
}
void merge(int a,int b)
{
f[getroot(a)]=getroot(b);
}
bool judge(int a,int b)
{
return getroot(a)==getroot(b);
}
}U;
struct ship
{
int c,len,p[21];
}Ship[21];
struct edge
{
edge *next,*op;
int t,c;
}*V[MAXN],*P[MAXN],ES[MAXM],*Stae[MAXN];
int N,M,K,S,T,EC,Ans,Maxflow;
int Lv[MAXN],Stap[MAXN];
inline void addedge(int a,int b,int c)
{
ES[++EC].next = V[a]; V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
ES[++EC].next = V[b]; V[b]=ES+EC; V[b]->t=a; V[b]->c=0;
V[a]->op = V[b]; V[b]->op = V[a];
}
void init()
{
int i,j,c;
freopen("home.in","r",stdin);
freopen("home.out","w",stdout);
scanf("%d%d%d",&N,&M,&K);
S=0; T=MAXN-1;
U.init(N+2);
for (i=1;i<=M;i++)
{
scanf("%d%d",&Ship[i].c,&Ship[i].len);
for (j=1;j<=Ship[i].len;j++)
{
scanf("%d",&c);
if (c==0)
c=N+2;
if (c==-1)
c=N+1;
Ship[i].p[j] = c;
if (j>1)
U.merge(Ship[i].p[j-1],c);
}
}
N+=2;
}
bool Dinic_Label()
{
int head,tail,i,j;
Stap[head=tail=0]=S;
memset(Lv,-1,sizeof(Lv));
Lv[S]=0;
while (head<=tail)
{
i=Stap[head++];
for (edge *e=V[i];e;e=e->next)
{
j=e->t;
if (e->c && Lv[j]==-1)
{
Lv[j] = Lv[i]+1;
if (j==T)
return true;
Stap[++tail] = j;
}
}
}
return false;
}
void Dinic_Augment()
{
int i,j,delta,Stop;
for (i=S;i<=T;i++)
P[i] = V[i];
Stap[Stop=1]=S;
while (Stop)
{
i=Stap[Stop];
if (i!=T)
{
for (;P[i];P[i]=P[i]->next)
if (P[i]->c && Lv[i] + 1 == Lv[j=P[i]->t])
break;
if (P[i])
{
Stap[++Stop] = j;
Stae[Stop] = P[i];
}
else
Stop--,Lv[i]=-1;
}
else
{
delta = INF;
for (i=Stop;i>=2;i--)
if (Stae[i]->c < delta)
delta = Stae[i]->c;
Maxflow += delta;
for (i=Stop;i>=2;i--)
{
Stae[i]->c -= delta;
Stae[i]->op->c += delta;
if (Stae[i]->c==0)
Stop = i-1;
}
}
}
}
void Dinic()
{
while (Dinic_Label())
Dinic_Augment();
}
inline int Point(int p,int d)
{
return d * N + p;
}
void solve()
{
int Day,i,a,b;
addedge(S,Point(N,0),INF);
addedge(Point(N-1,0),T,INF);
for (Day = 1;Maxflow < K;Day++)
{
addedge(S,Point(N,Day),INF);
addedge(Point(N-1,Day),T,INF);
for (i=1;i<=N;i++)
addedge(Point(i,Day-1),Point(i,Day),INF);
for (i=1;i<=M;i++)
{
a = Ship[i].p[ (Day - 1) % Ship[i].len + 1 ];
b = Ship[i].p[ Day % Ship[i].len + 1 ];
addedge(Point(a,Day-1),Point(b,Day),Ship[i].c);
}
Dinic();
}
Ans = Day - 1;
}
int main()
{
init();
if (U.judge(N-1,N))
solve();
else
Ans = 0;
printf("%d\n",Ans);
return 0;
}
分层图最短路径
【问题分析】
分层图最短路径问题。
【建模方法】
用P位二进制表示当前获得的钥匙状态，建立2^P层图。每层图表示在当前钥匙状态下的地图，每获得一把钥匙进入新的一层，BFS求最短路即可。
1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被
敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的
地形图。迷宫的外形是一个长方形，其南北方向被划分为N 行，东西方向被划分为M列，
于是整个迷宫被划分为N×M 个单元。每一个单元的位置可用一个有序数对(单元的行号，
单元的列号)来表示。南北或东西方向相邻的2 个单元之间可能互通，也可能有一扇锁着的
门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成P类，
打开同一类的门的钥匙相同，不同类门的钥匙不同。
大兵瑞恩被关押在迷宫的东南角，即(N，M)单元里，并已经昏迷。迷宫只有一个入口，
在西北角。也就是说，麦克可以直接进入(1，1)单元。另外，麦克从一个单元移动到另一个
相邻单元的时间为1，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。
«编程任务：
试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。
分层图最短路径问题。
【建模方法】
用P位二进制表示当前获得的钥匙状态，建立2^P层图。每层图表示在当前钥匙状态下的地图，每获得一把钥匙进入新的一层，BFS求最短路即可。
#include<bits/stdc++.h>
#define go(i,a,b) for(int i=a;i<=b;i++)
#define fo(i,a,x) for(int i=a[x];i>-1;i=e[i].next)
#define mem(a,b) memset(a,b,sizeof(a))
#define P 3000
#define inf 0x3f3f3f3f
using namespace std;const int N=203;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int n,m,p,f,S[N][N],id[N][N],key[N],head[N],k=0,s,t,dis[P][N];
struct E{int v,next,rar;}e[N*N*4];bool inq[P][N];
void ADD(int u,int v,int rar){e[k]=(E){v,head[u],rar};head[u]=k++;}
struct G{int x,y;};
int spfa()
{
mem(dis,0x3f);dis[1][1]=0;inq[1][1]=1;
queue<G>q;q.push((G){1,1});
while(!q.empty())
{
G U=q.front();q.pop();inq[U.x][U.y]=0;
dis[U.x|key[U.y]][U.y]=min(dis[U.x|key[U.y]][U.y],dis[U.x][U.y]);
U.x|=key[U.y];
fo(i,head,U.y)if(U.x%(e[i].rar<<1)>=e[i].rar)
{
int v=e[i].v;
if(dis[U.x][v]>dis[U.x][U.y]+1)
{
dis[U.x][v]=dis[U.x][U.y]+1;
if(!inq[U.x][v])
{
inq[U.x][v]=1;
q.push((G){U.x,v});
}
}
}
}
int ret=inf;go(i,1,P-1)ret=min(ret,dis[i][t]);
if(ret==inf)ret=-1;return ret;
}
int main()
{
int k,a,b,c;mem(S,-1);mem(head,-1);
scanf("%d%d%d%d",&n,&m,&p,&f);
go(i,1,n)go(j,1,m)id[i][j]=++t;
go(i,1,f){scanf("%d%d",&a,&b);a=id[a][b];
scanf("%d%d",&b,&c);b=id[b][c];
scanf("%d",&c);S[a][b]=S[b][a]=c;
if(c)ADD(a,b,1<<c),ADD(b,a,1<<c);}
go(i,1,n)go(j,1,m)
{
a=id[i][j];go(k,0,3)
{
int x=i+dx[k],y=j+dy[k];b=id[x][y];
if(S[a][b]==-1&&b)ADD(a,b,1);
}
}
scanf("%d",&f);
go(i,1,f)scanf("%d%d%d",&a,&b,&c),key[id[a][b]]|=(1<<c);
printf("%d\n",spfa());
return 0;
}最大权不相交路径
不相交其实就是拆点,拆点连流量为1,费用为其权值的边,这样保证了点只连一次,然后跑费用流.
问题描述:
给定一个由n 行数字组成的数字梯形如下图所示。梯形的第一行有m 个数字。从梯形
的顶部的m 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶
至底的路径。
规则1：从梯形的顶至底的m条路径互不相交。
规则2：从梯形的顶至底的m条路径仅在数字结点处相交。
规则3：从梯形的顶至底的m条路径允许在数字结点相交或边相交。
对于给定的数字梯形，分别按照规则1，规则2，和规则3 计算出从梯形的顶至底的m
条路径，使这m条路径经过的数字总和最大
【问题分析】
求图的最大权不相交路径及其变种，用费用最大流解决。
【建模方法】
规则(1)
把梯形中每个位置抽象为两个点
/*
* Problem: 线性规划与网络流24题 #16 digit
* Author: Guo Jiabao
* Time: 2009.6.29 16:38
* State: Solved
* Memo: 最大费用最大流
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXL=41,MAXN=1001*2,MAXM=MAXN*2*2,INF=~0U>>1;
struct Queue
{
int Q[MAXN],head,tail,size;
bool inq[MAXN];
void init()
{
memset(inq,0,sizeof(inq));
head = size =0; tail = -1;
}
void ins(int p)
{
size++;
if (++tail == MAXN) tail = 0;
Q[tail] = p;
inq[p]=true;
}
int pop()
{
size--;
int p=Q[head];
if (++head == MAXN) head = 0;
inq[p]=false;
return p;
}
}Q;
struct edge
{
edge *next,*op;
int t,c,v;
}*V[MAXN],ES[MAXM],*fe[MAXN];
int N,M,C,S,T,EC,Ans,Costflow;
int Poi[MAXL][MAXL],Value[MAXN],dist[MAXN],ft[MAXN];
inline void addedge(int a,int b,int c,int v)
{
ES[++EC].next = V[a]; V[a]=ES+EC; V[a]->t=b; V[a]->c=c; V[a]->v=v;
ES[++EC].next = V[b]; V[b]=ES+EC; V[b]->t=a; V[b]->c=0; V[b]->v=-v;
V[a]->op = V[b]; V[b]->op = V[a];
}
void init()
{
int i,j;
freopen("digit.in","r",stdin);
freopen("digit.out","w",stdout);
scanf("%d%d",&M,&N);
for (i=1;i<=N;i++)
for (j=1;j<=M+i-1;j++)
{
Poi[i][j] = ++C;
scanf("%d",&Value[C]);
}
}
bool SPFA()
{
int i,j;
for (i=S;i<=T;i++)
dist[i]=-INF;
dist[S]=0;
Q.ins(S);
while (Q.size)
{
i=Q.pop();
for (edge *e=V[i];e;e=e->next)
{
j=e->t;
if (e->c && dist[i] + e->v > dist[j])
{
dist[j] = dist[i] + e->v;
ft[j] = i;
fe[j] = e;
if (!Q.inq[j])
Q.ins(j);
}
}
}
return dist[T]!=-INF;
}
void Augment()
{
int i,delta=INF;
for (i=T;i!=S;i=ft[i])
if (fe[i]->c < delta)
delta = fe[i]->c;
for (i=T;i!=S;i=ft[i])
{
fe[i]->c -= delta;
fe[i]->op->c += delta;
Costflow += fe[i]->v * delta;
}
}
void SPFAFlow()
{
Q.init();
while (SPFA())
Augment();
}
void solve1()
{
int i,j;
S=0;T=C+C+1;EC=-1;
Costflow = 0;
memset(V,0,sizeof(V));
for (i=1;i<=C;i++)
addedge(i,i+C,1,Value[i]);
for (i=1;i<=M;i++)
addedge(S,Poi[1][i],1,0);
for (i=1;i<=M+N-1;i++)
addedge(Poi[N][i]+C,T,1,0);
for (i=1;i<N;i++)
for (j=1;j<=M+i-1;j++)
{
addedge(Poi[i][j]+C,Poi[i+1][j],1,0);
addedge(Poi[i][j]+C,Poi[i+1][j+1],1,0);
}
SPFAFlow();
}
void solve2()
{
int i,j;
S=0;T=C+1;EC=-1;
Costflow = 0;
memset(V,0,sizeof(V));
for (i=1;i<=M;i++)
addedge(S,Poi[1][i],1,0);
for (i=1;i<=M+N-1;i++)
addedge(Poi[N][i],T,INF,Value[Poi[N][i]]);
for (i=1;i<N;i++)
for (j=1;j<=M+i-1;j++)
{
addedge(Poi[i][j],Poi[i+1][j],1,Value[Poi[i][j]]);
addedge(Poi[i][j],Poi[i+1][j+1],1,Value[Poi[i][j]]);
}
SPFAFlow();
}
void solve3()
{
int i,j;
S=0;T=C+1;EC=-1;
Costflow = 0;
memset(V,0,sizeof(V));
for (i=1;i<=M;i++)
addedge(S,Poi[1][i],1,0);
for (i=1;i<=M+N-1;i++)
addedge(Poi[N][i],T,INF,Value[Poi[N][i]]);
for (i=1;i<N;i++)
for (j=1;j<=M+i-1;j++)
{
addedge(Poi[i][j],Poi[i+1][j],INF,Value[Poi[i][j]]);
addedge(Poi[i][j],Poi[i+1][j+1],INF,Value[Poi[i][j]]);
}
SPFAFlow();
}
void solve()
{
solve1();
printf("%d\n",Costflow);
solve2();
printf("%d\n",Costflow);
solve3();
printf("%d\n",Costflow);
}
int main()
{
init();
solve();
return 0;
}
网络费用流量
【问题分析】
费用流问题。
【建模方法】
把所有仓库看做二分图中顶点Xi，所有零售商店看做二分图中顶点Yi，建立附加源S汇T。
1、从S向每个Xi连一条容量为仓库中货物数量ai，费用为0的有向边。
2、从每个Yi向T连一条容量为商店所需货物数量bi，费用为0的有向边。
3、从每个Xi向每个Yj连接一条容量为无穷大，费用为cij的有向边。
求最小费用最大流，最小费用流值就是最少运费，求最大费用最大流，最大费用流值就是最多运费。
【建模分析】
把每个仓库想象成一个中转站，由源点运来ai单位货物，运费为0，每个商店也为一个中转站，运向目标汇点bi单位货物。每个仓库和零售商店之间有一条道路，容量为无穷大，费用为单位运费cij。求从源点到汇点的费用流，就是运费。
W 公司有m个仓库和n 个零售商店。第i 个仓库有ai 个单位的货物；第j 个零售商店
需要bj个单位的货物。货物供需平衡，即 sum(si）=sum(bj)
。从第i 个仓库运送每单位货物到
第j 个零售商店的费用为cij 。试设计一个将仓库中所有货物运送到零售商店的运输方案，
使总运输费用最少。
编程任务：
对于给定的m 个仓库和n 个零售商店间运送货物的费用，计算最优运输方案和最差运输方案。
输入描述 Input Description
的第1行有2 个正整数m和n，分别表示仓库数和
零售商店数。接下来的一行中有m个正整数ai ，1≤i≤m，表示第i个仓库有ai 个单位的货
物。再接下来的一行中有n个正整数bj ，1≤j≤n，表示第j个零售商店需要bj 个单位的货
物。接下来的m行，每行有n个整数，表示从第i 个仓库运送每单位货物到第j个零售商店
的费用cij 。
输出描述 Output Description
将计算出的最少运输费用和最多运输费用输出
样例输入 Sample Input
2 3
220 280
170 120 210
77 39 105
150 186 122
样例输出 Sample Output
48500
69140
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
const int MAXM = 100000;
const int INF = 0x3f3f3f3f;
struct Edge
{
int to,next,cap,flow,cost;
} edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N;//节点总个数，节点编号从0~N-1
void init(int n)
{
N = n;
tol = 0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost)
{
edge[tol].to = v;
edge[tol].cap = cap;
edge[tol].cost = cost;
edge[tol].flow = 0;
edge[tol].next = head[u];
head[u] = tol++;
edge[tol].to = u;
edge[tol].cap = 0;
edge[tol].cost = -cost;
edge[tol].flow = 0;
edge[tol].next = head[v];
head[v] = tol++;
}
bool spfa(int s,int t)
{
queue<int>q;
for(int i = 0; i < N; i++)
{
dis[i] = INF;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(edge[i].cap > edge[i].flow &&
dis[v] > dis[u] + edge[i].cost )
{
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
if(pre[t] == -1)return false;
else return true;
}
//返回的是最大流，cost存的是最小费用
int minCostMaxflow(int s,int t,int &cost)
{
int flow = 0;
cost = 0;
while(spfa(s,t))
{
int Min = INF;
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
{
if(Min > edge[i].cap - edge[i].flow)
Min = edge[i].cap - edge[i].flow;
}
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
{
edge[i].flow += Min;
edge[i^1].flow -= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
return flow;
}
int a[105];
int b[105];
int c[105][105];
int T;
int n,m,t;
int main()
{
freopen("tran.in","r",stdin);
freopen("tran.out","w",stdout);
// freopen("data.txt","r",stdin);
// scanf("%d", &T);
// while(T--)
// {
//
// }
int sum = 0;
int ss,tt;
scanf("%d%d", &m, &n);
ss=0,tt=m+n+1;
init(500);
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
addedge(0,i,a[i],0);
// for(int j=k+1;j<=k+m;j++)
// {
// addEdge(i,j,1);
// }
}
for(int j=m+1;j<=n+m;j++)
{
scanf("%d",&b[j]);
addedge(j,tt,b[j],0);
// for(int i=0;i<t;i++)
// {
// scanf("%d",&w);
// addEdge(w,j,1);
// }
}
for(int i = 1 ;i <= m; i++)
{
for(int j = 1;j <= n; j++)
{
scanf("%d",&c[i][j]);
addedge(i,j+m,INF,c[i][j]);
}
}
int cost =0 ;
minCostMaxflow(ss, tt,cost);
printf("%d\n",cost);
init(500);
for(int i=1;i<=m;i++)
{
addedge(0,i,a[i],0);
// for(int j=k+1;j<=k+m;j++)
// {
// addEdge(i,j,1);
// }
}
for(int j=m+1;j<=n+m;j++)
{
addedge(j,tt,b[j],0);
// for(int i=0;i<t;i++)
// {
// scanf("%d",&w);
// addEdge(w,j,1);
// }
}
for(int i = 1 ;i <= m; i++)
{
for(int j = 1;j <= n; j++)
{
addedge(i,j+m,INF,-c[i][j]);
}
}
minCostMaxflow(ss, tt,cost);
printf("%d\n",-cost);
// if(Maxflow(ss, tt)<sum)
// {
// printf("NoSolution!\n");
// }
// else
// {
//
// for(int i=1;i<=k;i++)
// {
// printf("%d:",i);
// for(int j = head[i]; j != -1; j = edge[j].next)
// {
// if(edge[j].flow==1)
// {
// printf("%d ",edge[j].to-k);
//
// }
// }
// printf("\n");
// }
//
//
// }
return 0;
}
二分图最佳匹配
【问题分析】
二分图最佳匹配问题，可以费用流解决（或KM算法）。
【建模方法】
把所有人看做二分图中顶点Xi，所有工作看做二分图中顶点Yi，建立附加源S汇T。
1、从S向每个Xi连一条容量为1，费用为0的有向边。
2、从每个Yi向T连一条容量为1，费用为0的有向边。
3、从每个Xi向每个Yj连接一条容量为无穷大，费用为Cij的有向边。
求最小费用最大流，最小费用流值就是最少运费，求最大费用最大流，最大费用流值就是最多运费。
【建模分析】
二分图最佳匹配建模方法为费用流模型。
题目描述 Description
有n件工作要分配给n个人做。第i 个人做第j 件工作产生的效益为ij c 。试设计一个将
n件工作分配给n个人做的分配方案，使产生的总效益最大。
«编程任务：
对于给定的n件工作和n个人，计算最优分配方案和最差分配方案。
输入描述 Input Description
第1 行有1 个正整数n，表示有n件工作要分配给n 个人做。接下来的n 行中，每行有n 个整数 cij ，1≤i≤n，1≤j≤n，表示第i 个人做第j件工作产生的效益为cij
输出描述 Output Description
将计算出的最小总效益和最大总效益输出
样例输入 Sample Input
5
2 2 2 1 2
2 3 1 2 4
2 0 1 1 1
2 3 4 3 3
3 2 1 2 1
样例输出 Sample Output
5
14
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
const int MAXM = 100000;
const int INF = 0x3f3f3f3f;
struct Edge
{
int to,next,cap,flow,cost;
} edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N;//节点总个数，节点编号从0~N-1
void init(int n)
{
N = n;
tol = 0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost)
{
edge[tol].to = v;
edge[tol].cap = cap;
edge[tol].cost = cost;
edge[tol].flow = 0;
edge[tol].next = head[u];
head[u] = tol++;
edge[tol].to = u;
edge[tol].cap = 0;
edge[tol].cost = -cost;
edge[tol].flow = 0;
edge[tol].next = head[v];
head[v] = tol++;
}
bool spfa(int s,int t)
{
queue<int>q;
for(int i = 0; i < N; i++)
{
dis[i] = INF;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(edge[i].cap > edge[i].flow &&
dis[v] > dis[u] + edge[i].cost )
{
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
if(pre[t] == -1)return false;
else return true;
}
//返回的是最大流，cost存的是最小费用
int minCostMaxflow(int s,int t,int &cost)
{
int flow = 0;
cost = 0;
while(spfa(s,t))
{
int Min = INF;
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
{
if(Min > edge[i].cap - edge[i].flow)
Min = edge[i].cap - edge[i].flow;
}
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
{
edge[i].flow += Min;
edge[i^1].flow -= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
return flow;
}
int a[105];
int b[105];
int c[105][105];
int T;
int n,m,t;
int main()
{
freopen("job.in","r",stdin);
freopen("job.out","w",stdout);
// freopen("data.txt","r",stdin);
// scanf("%d", &T);
// while(T--)
// {
//
// }
int ss,tt;
scanf("%d", &n);
ss=0,tt=n+n+1;
init(500);
for(int i=1;i<=n;i++)
{
addedge(0,i,1,0);
}
for(int j=n+1;j<=n+n;j++)
{
addedge(j,tt,1,0);
// for(int i=0;i<t;i++)
// {
// scanf("%d",&w);
// addEdge(w,j,1);
// }
}
for(int i = 1 ;i <= n; i++)
{
for(int j = 1;j <= n; j++)
{
scanf("%d",&c[i][j]);
addedge(i,j+n,1,c[i][j]);
}
}
int cost =0 ;
minCostMaxflow(ss, tt,cost);
printf("%d\n",cost);
init(500);
for(int i=1;i<=n;i++)
{
addedge(0,i,1,0);
}
for(int j=n+1;j<=n+n;j++)
{
addedge(j,tt,1,0);
}
for(int i = 1 ;i <= n; i++)
{
for(int j = 1;j <= n; j++)
{
addedge(i,j+n,1,-c[i][j]);
}
}
minCostMaxflow(ss, tt,cost);
printf("%d\n",-cost);
// if(Maxflow(ss, tt)<sum)
// {
// printf("NoSolution!\n");
// }
// else
// {
//
// for(int i=1;i<=k;i++)
// {
// printf("%d:",i);
// for(int j = head[i]; j != -1; j = edge[j].next)
// {
// if(edge[j].flow==1)
// {
// printf("%d ",edge[j].to-k);
//
// }
// }
// printf("\n");
// }
//
//
// }
return 0;
}
最小代价供求
【问题分析】
转化为供求平衡问题，用最小费用最大流解决。
【建模方法】
首先求出所有仓库存货量平均值，设第i个仓库的盈余量为A[i]，A[i] = 第i个仓库原有存货量 - 平均存货量。建立二分图，把每个仓库抽象为两个节点Xi和Yi。增设附加源S汇T。
1、如果A[i]>0，从S向Xi连一条容量为A[i]，费用为0的有向边。
2、如果A[i]<0，从Yi向T连一条容量为-A[i]，费用为0的有向边。
3、每个Xi向两个相邻顶点j，从Xi到Xj连接一条容量为无穷大，费用为1的有向边，从Xi到Yj连接一条容量为无穷大，费用为1的有向边。
求最小费用最大流，最小费用流值就是最少搬运量。
【建模分析】
计算出每个仓库的盈余后，可以把问题转化为供求问题。建立供求网络，把二分图X集合中所有节点看做供应节点，Y集合所有节点看做需求节点，在能一次搬运满足供需的Xi和Yj之间连接一条费用为1的有向边，表示搬运一个单位货物费用为1。另外还要在Xi与相邻的Xj之间连接边，表示货物可以暂时搬运过去，不立即满足需求，费用也为1。最大流满足了所有的盈余和亏损供求平衡，最小费用就是最少搬运量。
G 公司有n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最
少搬运量可以使n 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。
«编程任务：
对于给定的n 个环形排列的仓库的库存量，编程计算使n 个仓库的库存数量相同的最少
搬运量。
输入描述 Input Description
第1 行中有1 个正整数n（n<=100），表示有n
个仓库。第2 行中有n个正整数，表示n个仓库的库存量。
输出描述 Output Description
将计算出的最少搬运量输出
样例输入 Sample Input
5
17 9 14 16 4
样例输出 Sample Output
11
数据范围及提示 Data Size & Hint
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
const int MAXM = 100000;
const int INF = 0x3f3f3f3f;
struct Edge
{
int to,next,cap,flow,cost;
} edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N;//节点总个数，节点编号从0~N-1
void init(int n)
{
N = n;
tol = 0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost)
{
edge[tol].to = v;
edge[tol].cap = cap;
edge[tol].cost = cost;
edge[tol].flow = 0;
edge[tol].next = head[u];
head[u] = tol++;
edge[tol].to = u;
edge[tol].cap = 0;
edge[tol].cost = -cost;
edge[tol].flow = 0;
edge[tol].next = head[v];
head[v] = tol++;
}
bool spfa(int s,int t)
{
queue<int>q;
for(int i = 0; i < N; i++)
{
dis[i] = INF;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(edge[i].cap > edge[i].flow &&
dis[v] > dis[u] + edge[i].cost )
{
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
if(pre[t] == -1)return false;
else return true;
}
//返回的是最大流，cost存的是最小费用
int minCostMaxflow(int s,int t,int &cost)
{
int flow = 0;
cost = 0;
while(spfa(s,t))
{
int Min = INF;
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
{
if(Min > edge[i].cap - edge[i].flow)
Min = edge[i].cap - edge[i].flow;
}
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
{
edge[i].flow += Min;
edge[i^1].flow -= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
return flow;
}
int a[105];
int b[105];
int c[105][105];
int T;
int n,m,t;
int main()
{
freopen("overload.in","r",stdin);
freopen("overload.out","w",stdout);
// freopen("data.txt","r",stdin);
// scanf("%d", &T);
// while(T--)
// {
//
// }
int ss,tt;
scanf("%d",&n);
int sum =0;
ss=0,tt=n+1;
init(500);
for(int i=1;i<=n;i++)
{
scanf("%d",&t);
sum+=t;
addedge(0,i,t,0);
}
for(int i=1;i<=n;i++)
{
if(i!=1)
addedge(i,i-1,INF,1);
else
addedge(i,n,INF,1);
if(i!=n)
addedge(i,i+1,INF,1);
else
addedge(i,1,INF,1);
}
for(int j=1;j<=n;j++)
{
addedge(j,tt,sum/n,0);
}
int cost =0 ;
minCostMaxflow(ss,tt,cost);
printf("%d\n",cost);
return 0;
}
最大权不相交路径
【问题分析】
最大权不相交路径问题，可以用最大费用最大流解决。
【建模方法】
方法1
按左端点排序所有区间，把每个区间拆分看做两个顶点
/*
* Problem: 线性规划与网络流24题 #21 最长k可重区间集问题
* Author: Guo Jiabao
* Time: 2009.6.30 12:32
* State: Solved
* Memo: 最大费用最大流
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=501*2,MAXM=(MAXN*MAXN/4+MAXN*3)*2,INF=~0U>>1;
struct Queue
{
int Q[MAXN],head,tail,size;
bool inq[MAXN];
void init()
{
memset(inq,0,sizeof(inq));
head = size =0; tail = -1;
}
void ins(int p)
{
size++;
if (++tail == MAXN) tail = 0;
Q[tail] = p;
inq[p]=true;
}
int pop()
{
size--;
int p=Q[head];
if (++head == MAXN) head = 0;
inq[p]=false;
return p;
}
}Q;
struct interval
{
int a,b;
}I[MAXN];
struct edge
{
edge *next,*op;
int t,c,v;
}*V[MAXN],ES[MAXM],*fe[MAXN],*P[MAXN];
int N,K,S,SS,T,EC,Ans,Costflow;
int dist[MAXN],ft[MAXN];
inline void addedge(int a,int b,int c,int v)
{
ES[++EC].next = V[a]; V[a]=ES+EC; V[a]->t=b; V[a]->c=c; V[a]->v=v;
ES[++EC].next = V[b]; V[b]=ES+EC; V[b]->t=a; V[b]->c=0; V[b]->v=-v;
V[a]->op = V[b]; V[b]->op = V[a];
//printf("(%d,%d) c=%d v=%d\n",a,b,c,v);
}
inline int cmp(const void *a,const void *b)
{
return ((interval *)a)->a - ((interval *)b)->a;
}
void init()
{
int i,j;
freopen("interv.in","r",stdin);
freopen("interv.out","w",stdout);
scanf("%d%d",&N,&K);
S=0; T=N+N+2; SS=T-1;
addedge(S,SS,K,0);
for (i=1;i<=N;i++)
{
scanf("%d%d",&I[i].a,&I[i].b);
addedge(SS,i,1,0);
addedge(i+N,T,1,0);
}
qsort(I+1,N,sizeof(I[0]),cmp);
for (i=1;i<=N;i++)
{
addedge(i,i+N,1,I[i].b-I[i].a);
P[i] = ES+EC-1;
for (j=i+1;j<=N;j++)
if (I[j].a>=I[i].b)
addedge(i+N,j,1,0);
}
}
bool SPFA()
{
int i,j;
for (i=S;i<=T;i++)
dist[i]=-INF;
dist[S]=0;
Q.ins(S);
while (Q.size)
{
i=Q.pop();
for (edge *e=V[i];e;e=e->next)
{
j=e->t;
if (e->c && dist[i] + e->v > dist[j])
{
dist[j] = dist[i] + e->v;
ft[j] = i;
fe[j] = e;
if (!Q.inq[j])
Q.ins(j);
}
}
}
return dist[T]!=-INF;
}
void Augment()
{
int i,delta=INF;
for (i=T;i!=S;i=ft[i])
if (fe[i]->c < delta)
delta = fe[i]->c;
for (i=T;i!=S;i=ft[i])
{
fe[i]->c -= delta;
fe[i]->op->c += delta;
Costflow += fe[i]->v * delta;
}
}
void SPFAFlow()
{
Q.init();
while (SPFA())
Augment();
}
int main()
{
init();
SPFAFlow();
printf("%d\n",Costflow);
/*for (int i=1;i<=N;i++)
if (P[i]->c==0)
printf("%d %d\n",I[i].a,I[i].b);*/
return 0;
}
/*
* Problem: 线性规划与网络流24题 #21 最长k可重区间集问题
* Author: Guo Jiabao
* Time: 2009.6.30 12:51
* State: Solved
* Memo: 最大费用最大流 区间离散化
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=501*2,MAXM=MAXN*2*2,INF=~0U>>1;
struct Queue
{
int Q[MAXN],head,tail,size;
bool inq[MAXN];
void init()
{
memset(inq,0,sizeof(inq));
head = size =0; tail = -1;
}
void ins(int p)
{
size++;
if (++tail == MAXN) tail = 0;
Q[tail] = p;
inq[p]=true;
}
int pop()
{
size--;
int p=Q[head];
if (++head == MAXN) head = 0;
inq[p]=false;
return p;
}
}Q;
struct interval
{
int a,b,len;
}I[MAXN];
struct edge
{
edge *next,*op;
int t,c,v;
}*V[MAXN],ES[MAXM],*fe[MAXN];
int N,K,C,S,T,EC,Ans,Costflow;
int dist[MAXN],ft[MAXN];
int *IA[MAXN];
inline void addedge(int a,int b,int c,int v)
{
ES[++EC].next = V[a]; V[a]=ES+EC; V[a]->t=b; V[a]->c=c; V[a]->v=v;
ES[++EC].next = V[b]; V[b]=ES+EC; V[b]->t=a; V[b]->c=0; V[b]->v=-v;
V[a]->op = V[b]; V[b]->op = V[a];
// printf("(%d,%d) c=%d v=%d\n",a,b,c,v);
}
inline int cmp(const void *a,const void *b)
{
return *(*(int **)a) - *(*(int **)b);
}
void init()
{
int i,last;
freopen("interv.in","r",stdin);
freopen("interv.out","w",stdout);
scanf("%d%d",&N,&K);
S=0; T=N+N+1;
for (i=1;i<=N;i++)
{
scanf("%d%d",&I[i].a,&I[i].b);
I[i].len = I[i].b - I[i].a;
IA[++C] = &I[i].a;
IA[++C] = &I[i].b;
}
qsort(IA+1,C,sizeof(IA[0]),cmp);
IA[0] = &S;
for (i=1,last=-INF;i<=C;i++)
{
if (*IA[i]!=last)
{
last = *IA[i];
*IA[i] = *IA[i-1] + 1;
}
else
*IA[i] = *IA[i-1];
}
addedge(S,1,K,0);
addedge(*IA[C],T,K,0);
for (i=1;i<C;i++)
addedge(i,i+1,INF,0);
for (i=1;i<=N;i++)
addedge(I[i].a,I[i].b,1,I[i].len);
}
bool SPFA()
{
int i,j;
for (i=S;i<=T;i++)
dist[i]=-INF;
dist[S]=0;
Q.ins(S);
while (Q.size)
{
i=Q.pop();
for (edge *e=V[i];e;e=e->next)
{
j=e->t;
if (e->c && dist[i] + e->v > dist[j])
{
dist[j] = dist[i] + e->v;
ft[j] = i;
fe[j] = e;
if (!Q.inq[j])
Q.ins(j);
}
}
}
return dist[T]!=-INF;
}
void Augment()
{
int i,delta=INF;
for (i=T;i!=S;i=ft[i])
if (fe[i]->c < delta)
delta = fe[i]->c;
for (i=T;i!=S;i=ft[i])
{
fe[i]->c -= delta;
fe[i]->op->c += delta;
Costflow += fe[i]->v * delta;
}
}
void SPFAFlow()
{
Q.init();
while (SPFA())
Augment();
}
int main()
{
init();
SPFAFlow();
printf("%d\n",Costflow);
/*for (int i=1;i<=N;i++)
if (P[i]->c==0)
printf("%d %d\n",I[i].a,I[i].b);*/
return 0;
}
二分图最大独立集
【问题分析】
二分图最大独立集，转化为二分图最大匹配，从而用最大流解决。
【建模方法】
首先把棋盘黑白染色，使相邻格子颜色不同。把所有可用的黑色格子看做二分图X集合中顶点，可用的白色格子看做Y集合顶点。建立附加源S汇T，从S向X集合中每个顶点连接一条容量为1的有向边，从Y集合中每个顶点向T连接一条容量为1的有向边。从每个可用的黑色格子向骑士一步能攻击到的可用的白色格子连接一条容量为无穷大的有向边。求出网络最大流，要求的结果就是可用格子的数量减去最大流量。
【建模分析】
用网络流的方法解决棋盘上的问题，一般都要对棋盘黑白染色，使之成为一个二分图。放尽可能多的不能互相攻击的骑士，就是一个二分图最大独立集问题。有关二分图最大独立集问题，更多讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。
该题规模比较大，需要用效率较高的网络最大流算法解决。
在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘
上某些方格设置了障碍，骑士不得进入。
对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑
士，使得它们彼此互不攻击。
输入描述 Input Description
第一行有2 个正整数n 和m (1<=n<=200, 0<=m
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 41000;
const int MAXM = 10000010;
const int INF = 0x3f3f3f3f;
//const ll MOD = 998244353;
int dir[8][2]={ {2,1},{-2,1},{2,-1},{-2,-1} , {1,2},{1,-2},{-1,2},{-1,-2} };
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
struct Edge
{
int from, to, cap, flow, next;
};
Edge edge[MAXM];
int head[MAXN], cur[MAXN], edgenum;
int dist[MAXN];
bool vis[MAXN];
int N, M,ss,tt;
void init()
{
edgenum = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int w)
{
Edge E1 = {u, v, w, 0, head[u]};
edge[edgenum] = E1;
head[u] = edgenum++;
Edge E2 = {v, u, 0, 0, head[v]};
edge[edgenum] = E2;
head[v] = edgenum++;
}
bool BFS(int s, int t)
{
queue<int> Q;
memset(dist, -1, sizeof(dist));
memset(vis, false, sizeof(vis));
dist[s] = 0;
vis[s] = true;
Q.push(s);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
for(int i = head[u]; i != -1; i = edge[i].next)
{
Edge E = edge[i];
if(!vis[E.to] && E.cap > E.flow)
{
dist[E.to] = dist[u] + 1;
if(E.to == t) return true;
vis[E.to] = true;
Q.push(E.to);
}
}
}
return false;
}
int DFS(int x, int a, int t)
{
if(x == t || a == 0) return a;
int flow = 0, f;
for(int &i = cur[x]; i != -1; i = edge[i].next)
{
Edge &E = edge[i];
if(dist[E.to] == dist[x] + 1 && (f = DFS(E.to, min(a, E.cap - E.flow), t)) > 0)
{
edge[i].flow += f;
edge[i^1].flow -= f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
int Maxflow(int s, int t)
{
int flow = 0;
while(BFS(s, t))
{
memcpy(cur, head, sizeof(head));
flow += DFS(s, INF, t);
}
return flow;
}
int mm[205][205];
int m,n;
int u,v;
int getnum(int x,int y)
{
return (x-1)*n+y;
}
void dfs(int curx,int cury,int now)
{
mm[curx][cury] = now;
for(int i=0 ;i<8;i++)
{
int xx = curx + dir[i][0];
int yy = cury + dir[i][1];
if(xx<1||xx>n||yy<1||yy>n||mm[xx][yy])
{
continue;
}
if(now==2)
{
// addEdge(getnum(curx,cury),getnum(xx,yy),INF);
dfs(xx,yy,3);
}
else
{
// addEdge(getnum(xx,yy),getnum(curx,cury),INF);
dfs(xx,yy,2);
}
}
}
int main()
{
// freopen("data.txt","r",stdin);
ios_base::sync_with_stdio(false);
cin >> n>>m;
init();
int s = 0;
int t = n*n+1;
for(int i=0;i<m;i++)
{
cin >> u>>v;
mm[u][v]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mm[i][j]==0)
{
dfs(i,j,2);
}
}
}
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=n;j++)
// {
// cout << mm[i][j]<<" ";
// }
// cout <<endl;
// }
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mm[i][j]==2)
{
addEdge(s,getnum(i,j),1);
for(int d=0 ;d<8;d++)
{
int xx = i + dir[d][0];
int yy = j + dir[d][1];
if(xx<1||xx>n||yy<1||yy>n)
{
continue;
}
if(mm[xx][yy]==3)
{
addEdge(getnum(i,j),getnum(xx,yy),INF);
}
}
}
if(mm[i][j]==3)
{
addEdge(getnum(i,j),t,1);
}
}
}
cout << n*n-m-Maxflow(s,t)<<endl;
return 0;
}