@[toc]
例题：
NC20483 [ZJOI2009]假期的宿舍
题目描述：
学校放假了 · · · · · · 有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是 B 睡 A 的床而 C 睡 B 的床。
而实际情况可能非常复杂，有的人可能认识好多在校学生，在校学生之间也不一定都互相认识。我们已知一共有 n 个人，并且知道其中每个人是不是本校学生，也知道每个本校学生是否回家。
问是否存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。
题解：
构造二分图
一边是
本校学生有相应的床
一边是
要到学校的人
床与人构造边
• 左集合为所有需要床的人，右集合为所有的床
• 当第x个人可以睡第y张床（即认识第y个床的主人）那么就可以连边
• 求出最大匹配即可
详细题解+代码看
NC51316 Going Home
题目描述：
n 个小人回到 n 间房子，要求一对一，告诉每个人的位置和每个房子的位置，问n个人移动的总距离最少是多少
题解：
最小权值匹配模板
将所有值取相反数，然后跑一遍最优权值匹配模板
NC107638 poj3041 Asteroids
题目描述：
网格图中有若干个陨石，每次发射武器可以打掉某一行或某一列的所有陨石，求打完所有陨石的最少次数
题解：
首先，贪心的打星球最多的行/列有反例，如：
0 0 0 0
1 1 0 0
1 0 1 0
1 0 0 1
正解：
我们把行和列抽象为点，把陨石抽象为边，即当（x,y）有一个陨石的时候 ，将左边的第x个
点与右边的第y个点连边
• 最后是要找到最少的点（行/列）来覆盖掉所有的边（陨石）
• 也就是二分图的最小点覆盖！
最小点覆盖：在二分图中选尽量少的点覆盖所有的边
我们将问题转化为选左右最少数量的点可以覆盖所有边
而 最小点覆盖=最大匹配
比如例子：
0 0 0 0
1 1 0 0
1 0 1 0
1 0 0 1
NC20472 [ZJOI2007]矩阵游戏
题目描述：
• 小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。
矩阵游戏在一个N *N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。
• 每次可以对该矩阵进行两种操作：
• 行交换操作：选择 矩阵的任意两行，交换这两行（即交换对应格子的颜***r>• 列交换操作：选择矩阵的任意行列，交换这两列（即交换 对应格子的颜***r>• 游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。
• 对于某些关卡，小Q百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！！于是小Q决定写一个程序来判断这些关卡是否有解。
• N<=200
题解：
问题可以转化成：
• 每一行只保留一个黑色的点，且让这些黑色的点所在的列各不相同（即覆盖到每一列）
• 把行列抽象成点，分别为左集合和右集合
• 把黑点抽象成边，连接对应的行和列
• 看最大匹配是不是等于n，如果等于n就可行
NC110335 CF387D George and Interesting Graph
题目：
给你一个无重边的有向图，你每次操作可以加一条边或者删一条边，求让图变成一个“有趣
图”的最小操作次数
• “有趣图”，满足：
• 存在一个中心结点v，它和其他每个点都有双向边，且和自身有自环。
• 除了中心结点之外，其他结点的入度和出度都为2。 • 2 ≤ n ≤ 500, 1 ≤ m ≤ 1000
题解：
题目要求的其他节点的入度和出度都为2，因为中心节点要与其他点都有一条边，去除中心节点 v之后（以及v所关联的边），剩下所有点组成环（一个或者多个不想交的环，因为环上的点入度出度都为1）
N不大，考虑枚举中心点u • 分类讨论：
• 和u有关的边：
• u的自环 ——没有就+1条，有就不管了
• u到每一个点的出边和入边——如果没有就加上这1条，如果有就不管
和u无关的边
将每个点的入度与出度分为左集合和右集合
• 当我们把和u有关的边都删掉以后，每个点的出度和入度都应该是1 • 在这种情况下我们要操作的次数最小，也就是保留尽量多的原来的边——把每个点拆成
入点和出点，所有的入点和出点分别为左集合和右集合，求出来的最大匹配就是能保留
的边，其他的边要删掉；而如果最大匹配数不等于非中心节点数，显然就还需要加边
（需要将二分图匹配加成满配才能满足每个点入度1出度1，这样原图也就变成了一个环或者多个不相交的环。）
代码：
目前为WA，没发现哪里错了。。。感觉应该没问题的
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
return s*w;
}
const int maxn=600;
const int mod=500;
int g[maxn][maxn];
int a[1030][1030];
int tot=0;
int vis[maxn];
int link[maxn];
int n,m;
int maxmatch(int x)
{
for(int i=1+n;i<=n+n;i++)
{
if(a[x][i]==0||vis[i])continue;
vis[i]=1;
if(link[i]==0||maxmatch(link[i]))
{
link[i]=x;
return 1;
}
}
return 0;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
g[x][y]=1;
}
int maxx=0x7f;
for(int i=1;i<=n;i++)
{
memset(link,0,sizeof(link));
tot=0;
if(g[i][i]!=1)tot++;
for(int j=1;j<=n;j++)
{
if(j==i)continue;
if(g[i][j]==0)tot++;
if(g[j][i]==0)tot++;
}
int sum=0;
int ans=0;
for(int j=1;j<=n;j++)
{
if(j==i)continue;
for(int k=1;k<=n;k++)
{
if(k==i)continue;
if(g[j][k])
{
a[j][k+n]=1;
a[k+n][j]=1;
ans++;
}
}
}
//int op=0;
for(int j=1;j<=n;j++)
{
if(j==i)continue;
memset(vis,0,sizeof(vis));
sum+=maxmatch(j);
}
tot+=ans-sum;
tot+=n-1-sum;
maxx=min(maxx,tot);
}
cout<<maxx;
}
网上找的AC代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int match[600];
int vis[600];
int a[600][600];
int x[4545];
int y[4545];
int n,m;
int find(int u)
{
for(int i=1;i<=n;i++)
{
if(a[u][i]==1&&vis[i]==0)
{
vis[i]=1;
if(match[i]==-1||find(match[i]))
{
match[i]=u;
return 1;
}
}
}
return 0;
}
int Slove(int u)
{
int ans=0,tot=0;
memset(a,0,sizeof(a));
for(int i=1;i<=m;i++)a[x[i]][y[i]]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]==1&&(i!=u)&&(j!=u))tot++;
if(a[i][j]==0&&(i==u||j==u))
{
ans++;
}
if(i==u||j==u)a[i][j]=0;
}
}
memset(match,-1,sizeof(match));
int output=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(i==u)continue;
if(find(i))output++;
}
ans+=n-1-output;
ans+=tot-output;
return ans;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x[i],&y[i]);
}
int ans=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
int tmp=Slove(i);
ans=min(ans,tmp);
}
printf("%d\n",ans);
}
} 代码：
NC131152 Gym 101873F Plug It In
题意：
有m个插座，n个电器，每个插座最多可连接一个电器。另外有一个插线板，可以使得一个插座连接三个电器，给出每个插座能插的电器，问最多能插电器的个数是多少。
• N,m<=1500, k(边数)<=75000
题解：
先不考虑插线板 ——二分图最大匹配
• 插线板会使得某个插头被复制两份
• ——枚举插头然后加倍再跑最大匹配行不行？
• 会tle
• 因为插一个插头其实只是加了两个点——先把原图的最大匹配结果保留下来
• 然后每次在这个结果上加两个点，给它两找增广路即可。
代 码：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
return s*w;
}
const int maxn=1508;
int a[maxn][maxn];
int vis[maxn];
int link[maxn];
int link1[maxn];
int n,m,k;
int maxmatch(int x)
{
for(int i=1;i<=m;i++)
{
if(vis[i]||a[x][i]==0)continue;
vis[i]=1;
if(link[i]==0||maxmatch(link[i]))
{
link[i]=x;
return 1;
}
}
return 0;
}
void init()
{
for(int i=1;i<=m;i++)
{
link[i]=link1[i];
}
}
int main()
{
cin>>n>>m>>k;
//while(scanf("%d%d%d", &n, &m, &k) == 3)
{
for(int i=1;i<=k;i++)
{
int x,y;
cin>>x>>y;
a[x][y]=1;
//a[y][x]=1;
}
int sum=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
sum+=maxmatch(i);
}
// cout<<"sum="<<sum<<endl;
int maxx=0;
for(int i=1;i<=m;i++)
{
link1[i]=link[i];
}
for(int i=1;i<=n;i++)
{
init();
int tot=0;
for(int j=1;j<=2;j++)
{
memset(vis,0,sizeof(vis));
tot+=maxmatch(i);
}
maxx=max(maxx,tot);
//cout<<"tot="<<tot<<endl;
// cout<<"sum="<<sum<<endl;
}
cout<<sum+maxx<<endl;
}
}
NC112788 CF981F Round Marriage
题目：
• n个新郎和n个新娘围成一个环，环的长度为L，给出所有新郎可以站的位置和新娘可以站的位置，将新郎新娘安排到这些位置上，最 小化每一对新郎和新娘距离的最大值。
• 1≤n≤2*10^5^ ，1 ≤ L≤ 10^9^
题解：
• 二分答案
• 每次只添加男女之间不超过mid的边，求最大匹配
• 会tle
• Hall定理：对于一个二分图，如果对于左边任意子集S，其对应边连接了一个右边的点集T，
都有|S|≤|T|，那么这个二分图有完美匹配。(充要)
对于本题来说，左集合的点x，在右集合能匹配的点刚好是一个区间，记为[Lx,Rx] • 因为当x增大的时候，对应的区间也是右移的，所以我们只需要看连续的左集合——左集合中
任意区间[a,b]都需要满足其对应区间[La，Rb]中的元素比他多
• 即b-a<=Rb-La
• 移项： b-Rb<=a-La
sum[b]:b点及以前新郎个数
sum2[b]：b点及以前新娘个数
x是第几个新郎，Lx，Ly是新娘的范围
再枚举a，b
二分答案，判mid是否合法
如何判断：如果是在直线上，那么遍历匹配即可
现在在环上，即既可以向前匹配也可以向后匹配，那么将环拆开，扩展成三倍
显然a和b的匹配边是不可能交叉的，因为交叉必定没有不交叉优
hall定理：二分图两个点集A,B，连续一段A的点对应连续一段B的点的 充要条件是 这些点对的匹配边之间不交叉
重要推论：二部图G中的两部分顶点组成的集合分别为X,Y, 若|X|=|Y|,
且G中有一组无公共端点的边，一端恰好组成X中的点，一端恰好组成Y中的点，则称二部图G中存在完美匹配
有了这个定理，就可以用在判定上：a的点集对应b点集的连续一段，即b的n个点也是连续的，因为之前已经确定匹配边不交叉
先求出a[1]的范围[a[1]-mid,a[1]+mid]对应的能控制的b数组的范围[l1,r1]
那么a[2]的控制范围要和[l1+1,r1+1]交叉得到[l2,r2]
那么a[3]的控制范围要和[l2+1,r2+1]交叉得到[l3,r3]
...依次类推
可以这个区间长度只会减小不会变大
答案：
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
long long n,L,a[maxn],b[maxn<<2],c[maxn],m;
int judge(int mid){//a[i]的控制区间是[a[i]-mid,a[i]+mid]
int l=1,r=m;
for(int i=1;i<=n;i++){
while(a[i]-mid>b[l])
++l;
while(a[i]+mid<b[r])
--r;
if(l>r)return 0;
++l,++r;
}
return 1;
}
int main(){
cin>>n>>L;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>c[i];
sort(c+1,c+1+n);sort(a+1,a+1+n);
for(int i=1;i<=n;i++)b[i]=c[i]-L;
for(int i=1;i<=n;i++)b[i+n]=c[i];
for(int i=1;i<=n;i++)b[i+2*n]=c[i]+L;
m=3*n;
int l=0,r=L,ans,mid;
while(l<=r){
mid=l+r>>1;
if(judge(mid))
ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans<<'\n';
} 
京公网安备 11010502036488号