爵士OIer查看:0 回复:2 评论:0 创建时间:2020-05-04T21:16:28用户:爵士OIer查看:0 回复:2 评论:0 创建时间:2020-05-04T21:16:28
这是提高教程。
完备匹配、多重匹配
给定一张二分图，其左部，右部节点数相同，均为N个节点。如果该二分图的最大匹配包含N条匹配边，则称该二分图具有完备匹配。
给定一张包含N个左部节点、M个右部节点的二分图。从中选出尽量多的边。使第i(1≤i≤N)个左部节点至多与kl_i条选出的边相连，第j(1≤j≤M)个右部节点至多与kr_ j条选出的边相连。该问题被称为二分图的多重匹配。
当kl_i=kr_j=1时，二分图的多重匹配即简化为最大匹配。
多重匹配的解决方案
1.拆点：把第i个左部节点拆成kl_i个不同的左部节点，第j个右部节点拆成kr_j个右部节点。对于原图中的每条边(i,j)，在i拆成的所有节点与j拆成的所有节点之间连边。然后求解二分图最大匹配。
2.网络流（想展开讲是不可能的）
例题：导弹防御塔
问题描述
Freda Shi 的城堡遭受了M个入侵者的攻击！
Freda 控制着N座导弹防御塔，每座塔都有足够数量的导弹，但是每次只能发射一枚。每座塔每次发射前需要预热T1秒，发射后需要冷却T2秒。
给定塔和入侵者的坐标。导弹从塔发出直到击中目标所需的飞行时间=塔和入侵者之间的距离。
由于小伙伴 Rainbow Li 就要来拜访她的城堡，Freda 想用最少的时间击退所有的入侵者，请你告诉她一种攻击方案。
输入格式
第一行五个正整数N,M,T1,T2,V。
接下来 M 行每行两个整数，代表入侵者的坐标。
接下来 N 行每行两个整数，代表防御塔的坐标。
输出格式
输出一个实数，表示最少需要多少分钟才能击中所有的入侵者，四舍五入保留六位小数。
数据范围
1≤N,M≤50,坐标绝对值不超过10000，T1,T2,V不超过2000。
输入样例：
3 3 30 20 1
0 0
0 50
50 0
50 50
0 1000
1000 0
输出样例：91.500000
最值不容易解决，转化为判定——二分答案T，判定能否在T秒内击退所有入侵者。寻找要素——二分图中的“1”： 每个入侵者被攻击1次后就会被击退。 每座塔可以发射很多次导弹，但是每枚导弹只能攻击1个入侵者。拆点：若某座塔在T秒内可以发射X次导弹，就把这座塔拆成X个点。入侵者、拆点后的导弹分别构成二分图中的左右两部。寻找要素——二分图两部点之间的关系 导弹A在S秒时发射，飞到入侵者B需V秒，若S+V<=T，A到B连边。计算二分图的最大匹配，若每个左部点都能找到匹配，则说明T秒内能击退所有入侵者，可另二分上界r=T，否则令下界l=T+1
Code：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=50+10;
struct Node
{
int x,y;
Node() {}
Node(int a,int b):x(a),y(b) {}
} def[maxn],ta[maxn];
int vis[maxn*maxn],pre[maxn*maxn];
double times[maxn][maxn];
double t1,t2,V;
vector<int >G[maxn];
int n,m;
bool DFS(int u)
{
for(int i=0; i<G[u].size(); i++)
{
int v=G[u][i];
if(vis[v])
continue;
vis[v]=1;
if(pre[v]==0||DFS(pre[v]))
{
pre[v]=u;
return true;
}
}
return false;
}
bool judge(double mid)
{
for(int i=1; i<=m; i++)
G[i].clear();
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
{
double now=0;
for(int k=0; k<=m; k++)
{
now=k*(t1+t2);
if(mid-(now+t1+times[i][j])>1e-7)
{
G[i].push_back(j*(m+1)+k-m-1);
}
else
break;
}
}
memset(pre,0,sizeof(pre));
for(int i=1; i<=m; i++)
{
memset(vis,0,sizeof(vis));
if(!DFS(i))
return false;
}
return true;
}
int main()
{
cin>>n>>m>>t1>>t2>>V;
t1/=60.0;
for(int i=1; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
ta[i]=Node(x,y);
}
for(int i=1; i<=n; i++)
{
int x,y;
scanf("%d%d",&x,&y);
def[i]=Node(x,y);
}
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
times[i][j]=sqrt((ta[i].x-def[j].x)*(ta[i].x-def[j].x)+(ta[i].y-def[j].y)*(ta[i].y-def[j].y))/V;
double l=0,r=1000000,ans=r;
while(r-l>1e-9)
{
double mid=(l+r)/2.0;
if(judge(mid))
ans=min(ans,mid),r=mid;
else
l=mid;
}
printf("%.6lf\n",ans);
}
二分图最小点覆盖（Minimum Vertex Cover）
König定理
二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数
证明：
首先因为最大匹配是原二分图边集的一个子集，并且所有边都不相交，所以至少需要从每条匹配中选出一个端点。因此最小点覆盖包含的点数不可能小于最大匹配包含的边数。如果能对任意二分图构造出一组点覆盖，其包含的点数等于最大匹配包含的边数，定理即得证。
构造方法
1.求出最大匹配
2.从右部每个未匹配点出发寻找增广路（一定失败），标记访问过的节点。
3.取左部标记点，右部未标记点，构成一组最小覆盖。
经过上述构造方法后，
右部未匹配点一定是标记点——因为它们是出发点
左部未匹配点一定是未标记点——如果被标记(访问)则找到了增广路，矛盾
一对匹配点都被标记或者都未标记——因为左部匹配点只能通过右部到达
取左部标记点、右部未标记点，恰好使得每对匹配点被取走一个
数值上的相等性得证
匹配边一定被覆盖——每对匹配点取走一个
不存在连接两个未匹配点的边——否则出现仅包含1条边的增广路，矛盾
连接左部匹配点和右部未匹配点的边——后者是出发点，前者一定被标记
连接左部未匹配点和右部匹配点的边——后者未被标记，否则存在增广路
所有边都被覆盖，合法性得证
例题：Muddy Fields
问题描述
在一块N*M的矩形地面上，有一些格子是泥泞的。
用一些宽为1的木板把泥地盖住，并且不能盖住好地，木板可以重叠。
问最少需要多少木板？ N,M<=50。
解题思路
不能盖住好地，那么宽为1的木板只能放在行、列泥泞块里。
每个泥格子都要被盖住，选择一个块可以盖住一些泥格子。
行、列泥泞块对应左、右部中的点，泥格子对应边。
答案=二分图最小点覆盖。
Code：
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#define N 1100
int G[N][N], vis[N], used[N];
char maps[N][N];
int m, n, x, y;
bool Find(int u)
{
int i;
for(i = 1 ; i <= y ; i++)
{
if(!vis[i] && G[u][i])
{
vis[i] = 1;
if(!used[i] || Find(used[i]))
{
used[i] = u;
return true;
}
}
}
return false;
}
void Build()//构图
{
int i, j, a[N][N] , b[N][N];
x = y = 0;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for(i = 1 ; i <= m ; i++)
{
for(j = 1 ; j <= n ; j++)
{
if(maps[i][j] == '*')
{
if(maps[i][j - 1] == '*')
a[i][j] = a[i][j - 1];
else
a[i][j] = ++x;
}
}
}//木板横着放
for(i = 1 ; i <= m ; i++)
{
for(j = 1 ; j <= n ; j++)
{
if(maps[i][j] == '*')
{
if(maps[i - 1][j] == '*')
b[i][j] = b[i - 1][j];
else
b[i][j] = ++y;
G[a[i][j]][b[i][j]] = 1;
}
}
}//木板竖着放
}
int main()
{
int i, j, ans;
while(~scanf("%d%d", &m, &n))
{
ans = 0;
memset(G, 0, sizeof(G));
for(i = 1 ; i <= m ; i++)
{
getchar();
for(j = 1 ; j <= n ; j++)
{
scanf("%c", &maps[i][j]);
}
}
Build();
memset(used, 0, sizeof(used));
for(i = 1 ; i <= x ; i++)//X集合中的点与Y集合中的点找最大匹配
{
memset(vis, 0, sizeof(vis));
if(Find(i))
ans++;
}
printf("%d\n", ans);
}
return 0;
}
二分图最大独立集（Maximum Independent Set）
任意两点在图中都没有边相连的点集称为图的独立集。
定理：二分图最大独立集 = 图的点数 – 二分图最大匹配
证明：选出最多的点构成独立集
在图中去掉最少的点，使剩下的点之间没有边。
用最少的点覆盖所有的边，去掉的是最小覆盖。
例题：骑士放置
问题描述
给定一个N*M的棋盘，有一些格子不能放棋子。问棋盘上最多能放多少个不能互相攻击的骑士（马）。
解题思路：
对棋盘黑白染色，黑、白色的点分别属于左、右部。
可以攻击到的两个格子之间连边。
马沿日字形攻击，所以肯定是在不同颜色的点之间连边。
不能互相攻击，就是寻找一个最大独立集。
Code：
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;
co int N=101;
int n,m,t,ans,fx[N][N],fy[N][N];
bool a[N][N],v[N][N];
co int dx[8]={-2,-2,-1,-1,1,1,2,2};
co int dy[8]={-1,1,-2,2,-2,2,-1,1};
bool dfs(int x,int y){
for(int i=0;i<8;++i){
int nx=x+dx[i],ny=y+dy[i];
if(nx<1||nx>n||ny<1||ny>m||a[nx][ny]||v[nx][ny]) continue;
v[nx][ny]=1;
if(!fx[nx][ny]||dfs(fx[nx][ny],fy[nx][ny])){
fx[nx][ny]=x,fy[nx][ny]=y;
return 1;
}
}
return 0;
}
int main(){
read(n),read(m),read(t);
for(int i=1;i<=t;++i) a[read<int>()][read<int>()]=1;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
if(i+j&1||a[i][j]) continue;
memset(v,0,sizeof v);
ans+=dfs(i,j);
}
printf("%d\n",n*m-t-ans);
return 0;
}
有向无环图的最小路径点覆盖
最小路径覆盖：用尽量少的不相交简单路径覆盖有向无环图的所有顶点。(即每个顶点恰好被覆盖一次)
把原图中的每个点拆成二分图中左、右两个点；
对于每条有向边(u,v)，从u的左部点（成为出点）向v的右部点（称为入点）连一条有向边。
最小路径覆盖数 = 原有向图节点数 – 新二分图最大匹配数。
· 不相交的最小路径覆盖->每个点的入度、出度均不超过1
· 拆点转化->二分图每个点连接的边不超过1条->一个匹配
· 有向图路径上的每条边 对应 二分图匹配中的一条匹配边
· 有向图路径上每条边的出点 对应 二分图匹配边的左部点
· 每条路径的最后一个点没有对应
· 最小路径覆盖的路径数 = 最少未匹配的点数 = 原图节点数 – 二分图最大匹配数。
例题：Air Raid
问题描述
N个城市M条道路形成有向无环图。
现在要求派一些伞兵空降在某些城市，然后这些伞兵可以沿着道路访问到其他城市，但是不能有两个或两个以上伞兵访问同一个城市。
问最少需要多少个伞兵。N<=120。
代码不上了，自己想。