二分图（专题）
解题报告：二分出来答案，让小于等于答案的罪犯放在同一个监狱，让大于答案的放在另一个监狱，看是否染色成功。
#include<iostream>
#include<cstring>
using namespace std;
const int N=20010,M=200010;
int h[N],e[M],ne[M],w[M],idx;
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int n,m;
int color[N];
bool dfs(int u,int c,int mid)
{
color[u]=c;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(w[i]<=mid) continue;
if(color[j]==3-c) continue;
if(color[j]==c) return false;
if(!color[j]) if(!dfs(j,3-c,mid)) return false;
}
return true;
}
bool check(int mid)
{
memset(color,0,sizeof color);
for(int i=1;i<=n;i++)
{
if(!color[i])
{
if(!dfs(i,1,mid))
return false;
}
}
return true;
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
int l=0,r=1e9;
while(l<r)
{
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",r);
return 0;
}
解题报告：由于这题符合二分图染色的奇偶性质(即：不同颜色的格子之间有一条边）问最大的匹配数，枚举每个没有坏的格子，然后匈牙利匹配算法。
#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
typedef pair<int,int> PII;
bool g[N][N],st[N][N];
PII match[N][N];
int dx[4]={
1,-1,0,0},dy[4]={
0,0,1,-1};
int n,t;
bool find(int a,int b)
{
for(int i=0;i<4;i++)
{
int tx=a+dx[i];
int ty=b+dy[i];
if(tx<=0||ty<=0||tx>n||ty>n||g[tx][ty]) continue;
if(st[tx][ty]) continue;
st[tx][ty]=true;
if(match[tx][ty].first==0||find(match[tx][ty].first,match[tx][ty].second))
{
match[tx][ty]={
a,b};
return true;
}
}
return false;
}
int main()
{
cin>>n>>t;
while(t--)
{
int a,b;
cin>>a>>b;
g[a][b]=true;
}
int res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!g[i][j]&&(i+j)%2==1)
{
memset(st,0,sizeof st);
if(find(i,j))
res++;
}
cout<<res<<endl;
return 0;
}
解题报告：这题是最小覆盖模型，由于机器是从0开始的，每变换一次都需要重启，所以我们一开始把含有0的都过滤掉，然后往每个a、b之间连一条边，题目就可以抽象成一个在所有匹配边上选点并且覆盖所有边，结论就等于最大匹配数。
#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
bool g[N][N];
bool st[N];
int match[N];
int n,m,k;
bool find(int x)
{
for(int i=1;i<m;i++)
{
if(st[i]) continue;
if(g[x][i])
{
st[i]=true;
int t=match[i];
if(t==0||find(t))
{
match[i]=x;
return true;
}
}
}
return false;
}
int main()
{
while(cin>>n,n)
{
cin>>m>>k;
memset(g,0,sizeof g);
memset(match,0,sizeof match);
while(k--)
{
int id,a,b;
cin>>id>>a>>b;
if(a==0||b==0) continue;
g[a][b]=true;
}
int res=0;
for(int i=1;i<=n-1;i++)
{
memset(st,0,sizeof st);
if(find(i))
res++;
}
cout<<res<<endl;
}
return 0;
}
解题报告：这题是最大独立集问题，最大独立集就是集合中的点相互之间没有边相连，最大独立集的数量就是所有点减去最大匹配的数量。在这里还要减去废掉的点。
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int,int> pii;
const int N=110;
pii match[N][N];
bool g[N][N];
bool st[N][N];
int n,m,t;
int dx[8]={
2,-2,1,-1,1,2,-2,-1};
int dy[8]={
1,1,2,2,-2,-1,-1,-2};
bool find(int x,int y)
{
for(int i=0;i<8;i++)
{
int tx=x+dx[i];
int ty=y+dy[i];
if(tx<=0||ty<=0||tx>n||ty>m) continue;
if(!g[tx][ty]||st[tx][ty]) continue;
st[tx][ty]=1;
if(match[tx][ty].first==0||find(match[tx][ty].first,match[tx][ty].second))
{
match[tx][ty]={
x,y};
return true;}
}
return false;
}
int main()
{
cin>>n>>m>>t;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
g[i][j]=true;
for(int i=0;i<t;i++)
{
int a,b;
cin>>a>>b;
g[a][b]=false;
}
int res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
memset(st,0,sizeof st);
if(g[i][j]&&(i+j)%2&&find(i,j))
res++;
}
cout<<n*m-res-t<<endl;
}
解题报告：这题是最小路径重复点覆盖的问题，先把该问题变成最小路径覆盖问题，即做一遍传递闭包，然后变成所有点减去最大匹配数。其实答案也是出度为0的点个数，就是终点的个数。
#include<iostream>
#include<cstring>
using namespace std;
const int N=210;
bool g[N][N];
bool d[N][N];
int match[N];
int n,m;
bool st[N];
bool find(int x)
{
for(int i=1;i<=n;i++)
{
if(d[x][i]&&!st[i])
{
st[i]=true;
int t=match[i];
if(t==0||find(t))
{
match[i]=x;
return true;
}
}
}
return false;
}
int main()
{
cin>>n>>m;
while(m--)
{
int a,b;
cin>>a>>b;
g[a][b]=true;
}
memcpy(d,g,sizeof g);
int res=0;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]|=d[i][k]&d[k][j];
for(int i=1;i<=n;i++)
{
memset(st,0,sizeof st);
if(find(i))
res++;
}
cout<<n-res<<endl;
}
