板子
两种写法：（核心思想是一样的，使用时实测并没有什么区别
两个参数版（洛谷题解
bool dfs(ll u,ll ti)
{
if(vis[u]==ti)return 0;
vis[u]=ti;
for(int i=head[u];i;i=next[i])
{
if(mh[e[i].v]==0||dfs(mh[e[i].v],ti))
{
mh[e[i].v]=u;
return 1;
}
}
return 0;
}
一个参数版（网上题解多用
bool find(int u)
{
for(int i=head[u];i;i=next[i])
{
int v=e[i].v;
if(!vis[v])
{
vis[v]=1;
if(mh[v]==0||find(mh[v]))
{
mh[v]=u;
return 1;
}
}
}
return 0;
}
特别注意：使用一个参数版时，每次使用前vis数组都要清零！
超级英雄Hero
啊这，这不是板子吗？
然后就因为不读题+2了。
建图：锦囊妙计编号是一边，题目编号是一边，从锦囊向题目连边，然后跑匈牙利
注意题意：只有通过一题才能继续答题，所以如果中途断了直接跳出
另外：二分图有重边似乎对匈牙利算法并没有影响
文理分班
首先建图，考虑到分班前后座位的变化，我们可以用前后座位建图，如果之前坐在(a)处的同学分班后有可能坐到(b)处，则从(a)向(b)连边。
同时注意，如果一个人是本班的，且不调班，那他是可以不换座位的，这样我们就直接从他的座位(a)向(a)连边
那么只要最后每个人都有座位坐就是可行的方案
所以建图完了以后我们跑二分图匹配，如果全都能够匹配则可行
放置机器人
建图过程很有意思的一道题～
可以分别考虑每一行，每一列，并将每行每列以墙分隔成几个小部分，那么显然，每一个小部分中是只能放置一个机器人的。
我们又知道给定的行列信息能确定唯一位置，分隔后同样如此。我们可以把所有空地 按行分割所属部分 的编号向它们 按列分割所属部分 的编号连边，那么每一条边都代表了一个可放置机器人的位置，在得到的这个二分图上跑匈牙利，那么最大匹配边数即为最大能放置的机器人数。
挺有意思的，放下代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ZZ_zuozhe int main()
#define N 55
#define E 2550
struct edge
{
ll u,v;
}e[E];
ll tot,head[E],next[E];
void add(ll a,ll b)
{
++tot;
e[tot].u=a;
e[tot].v=b;
next[tot]=head[a];
head[a]=tot;
}
ll T;
ll n,m;
ll tmp,xcn,ycn,xt;
ll kd[N][N],xnm[N][N],ynm[N][N];
ll in(ll &a)
{
char ch=getchar();
if(ch=='#')return a=0;
else if(ch=='o')return a=1;
else if(ch=='*')return a=2;
}
ll vis[E],mh[E];
bool find(ll u)
{
for(int i=head[u];i;i=next[i])
{
ll v=e[i].v;
if(!vis[v])
{
vis[v]=1;
if(mh[v]==0||find(mh[v]))
{
mh[v]=u;
return 1;
}
}
}
return 0;
}
ll ans;
ZZ_zuozhe
{
memset(e,0,sizeof e);
memset(kd,0,sizeof kd);
memset(xnm,0,sizeof xnm);
memset(ynm,0,sizeof ynm);
memset(mh,0,sizeof mh);
tmp=xt=ans=0;
xcn=ycn=1;
scanf("%lld%lld",&n,&m);
getchar();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
in(kd[i][j]);
// cout<<kd[i][j]<<' ';
if(j==1&&tmp==1)tmp=0,xcn++;
if(kd[i][j]==1)xnm[i][j]=xcn,tmp=1,xt=xcn;
if(kd[i][j]==0&&tmp==1)tmp=0,xcn++;
}
getchar();
}
tmp=0;
for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)
{
if(j==1&&tmp==1)tmp=0,ycn++;
if(kd[j][i]==1)ynm[j][i]=ycn,tmp=1;
if(kd[j][i]==0&&tmp==1)tmp=0,ycn++;
}
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
{
add(xnm[i][j],ynm[i][j]);
}
for(int i=1;i<=xt;i++)
{
memset(vis,0,sizeof vis);
if(find(i))ans++;
}
// cout<<xcn<<' '<<ycn<<' '<<xt<<endl;
printf("%lld
",ans);
return 0;
}
猫和狗
运用了最大独立集的思想
关于最大独立集什么的：这篇博客写的超超超超详细啊qaq
明确了定义，我们来看题awa
题中，有人喜欢猫讨厌狗，有人喜欢狗讨厌猫，而且都是喜欢/讨厌特定的某只猫/狗，这个过程中，必然会产生冲突。
那么，我们要使留下来的顾客尽量多，就必须不满足一些顾客的要求，进而消除冲突
这个时候，我们可以这样建图：把喜欢猫的顾客归为一类，将喜欢狗的顾客归为一类，如果他们的需求出现了冲突，就将有冲突的两人连边。
我们得到答案的过程是一个消除冲突的过程，那么这个过程中定会放弃部分顾客，用二分图的思想理解，就是说要把一些点抠掉，这样一些边就会消失。
那么，我们的目的就转化成了将二分图上尽可能多的点留下，但要使任意留下的两点间没有连边。
熟不熟？
这不就最大独立集定义嘛！
由(König)定理：最大匹配(=)最小顶点覆盖
（还不太会证这个东西，留一个坑
又因为最大独立集(=)顶点个数(–)最小顶点覆盖（也就是最大匹配
（为何？最大匹配中任意两条边都是没有公共点的，那就每条边抠掉一个点嘛
所以，答案出来了，我们只要建图跑匈牙利，求出最大匹配，再用它减顶点个数（顶点个数是被减数）就行啦
代码仅供参考
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ZZ_zuozhe int main()
#define N 5005
#define E 90050
#define K 5005
struct edge
{
ll u,v;
}e[E];
ll tot=0,head[E],next[E];
void add(ll a,ll b)
{
++tot;
e[tot].u=a;
e[tot].v=b;
next[tot]=head[a];
head[a]=tot;
}
ll vis[N],mh[N];
bool find(ll u)
{
for(int i=head[u];i;i=next[i])
{
ll v=e[i].v;
if(!vis[v])
{
vis[v]=1;
if(!mh[v]||find(mh[v]))
{
mh[v]=u;
return 1;
}
}
}
return 0;
}
ll n,m,k;
string s1,s2;
ll n1,n2;
ll ans=0;
ll c[K],d[K],ln[K],ht[K];
ll ccn=0,dcn=0;
ZZ_zuozhe
{
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=k;i++)
{
s1.clear(),s2.clear();
cin>>s1>>s2;
ll l1=s1.length(),l2=s2.length();
n1=n2=0;
for(int j=1;j<l1;j++)n1*=10,n1+=(ll)s1[j]-'0';
for(int j=1;j<l2;j++)n2*=10,n2+=(ll)s2[j]-'0';
if(s1[0]=='C')c[++ccn]=i;
else d[++dcn]=i;
ln[i]=n1;ht[i]=n2;
}
for(int i=1;i<=ccn;i++)for(int j=1;j<=dcn;j++)
{
if(ln[c[i]]==ht[d[j]]||ln[d[j]]==ht[c[i]])add(c[i],d[j]);
}
for(int i=1;i<=ccn;i++)
{
memset(vis,0,sizeof vis);
if(find(c[i]))ans++;
}
printf("%lld
",k-ans);
return 0;
}
Girls and Boys
首先需要提一下这题的读入技巧
他的输入文件给的花里胡哨的，我以前都是读到字符串里再暴力把数字提取出来……（时间爆炸）
今天看到一个题解里是这样写的：
scanf("%lld: ",&x);
scanf("(%lld)",&tmp);
啊这，还有这种操作？？？
简直不要更方便了啊qaq
（我是不是致远星了
然后我们来看题目，题意挺清楚的就是一个最大独立集
然后发现并不知道是男是女，所以二分图两边我们都用所有人的编号，给他求最大匹配，然后(n-ans/2)就好
因为我们知道最大独立集(=n-)最大匹配
诶？为啥是(/2)？
其实可以这样考虑：左右有男有女，我们把他们分开，男的放上面，女的放下面，因为不存在男男，也不存在女女，所以这个时候连完线，并求完最大匹配后整个图应该是对称的，而且不存在一条线同时经过了男部分和女部分，这个时候我们左边只留下男生，右边只留下女生，最大匹配就变成了原来的一半
（多画点图就显然了
其实代码跟上一题相似
Treasure Exploration
可相交最小路径覆盖。
关于定义：看上面链接
关于两种最小路径覆盖：某位dalao的csdn
题意是很裸的，这里主要记一下两种最小路径覆盖解题过程的差别
- 不相交：这个时候就是给每一条边起点终点连边，跑最大匹配
- 相交：这个时候需要预处理每两个点是否联通，如果是则连边，这个时候就相当于不考虑中间经过的，而且起点和终点此时就都已经经过了，不会影响下一步的选择
另外，为什么答案是(n-cnt)？其实，刚开始时，我们每个结点都要放一个机器人，而我们每确定一条要走的边，就可以少放一个（连通了嘛），所以当最大匹配时，我们要放的机器人数量是取最小值的
再另外……
数据太大，存图一定要手动清空QAQ，(memset())是(O(n))的，如果你正好开了很大的数组就会直接gg
如果嫌手动清空麻烦，用数组存边也是个不错的选择……（顺便还能把连通性判了）
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ZZ_zuozhe int main()
#define N 1005
#define E 1005
ll n,m,a,b;
ll mh[E],vis[E];
bool mp[N][N]={0};
bool find(ll u)
{
for(int v=1;v<=n;v++)
{
if(!mp[u][v])continue;
if(!vis[v])
{
vis[v]=1;
if(!mh[v]||find(mh[v]))
{
mh[v]=u;
return 1;
}
}
}
return 0;
}
ll ans=0;
ZZ_zuozhe
{
while(scanf("%lld%lld",&n,&m)&&(n!=0||m!=0))
{
memset(mh,0,sizeof mh);
memset(mp,0,sizeof mp);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&a,&b);
mp[a][b]=1;
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)
{
mp[i][j]|=(mp[i][k]&mp[k][j]);
}
ans=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof vis);
ans+=find(i);
}
printf("%lld
",n-ans);
}
return 0;
}
怎么说呢……这居然好像是我第一次没用链式前向星存边……也算第一次尝到苦头吧qaq以后最好多准备几种存边方式……