最近又重新过了一遍二分匹配，发现了一些之前理解上的误区，这几天的纠结还是很值得的
//分别以行和列为单位，那么确定的和行和列唯一确定一个格子
//行向列连边，求最多的可放置的格子，也就是求最大匹配
//求重要点数，删除已匹配的边，判断是否存在最大匹配
View Code
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 101;
int n,m,my[N],mx[N];
bool vis[N],mat[N][N];
//分别以行和列为单位，那么确定的和行和列唯一确定一个格子
//行向列连边，求最多的可放置的格子，也就是求最大匹配
//求重要点数，删除已匹配的边，判断是否存在最大匹配
int path(int s)
{
for(int i=0;i<m;i++)
if(mat[s][i] && !vis[i])
{
vis[i]=1;
if(my[i]==-1 || path(my[i]))
{
my[i]=s;
mx[s]=i;
return 1;
}
}
return 0;
}
int match()
{
memset(mx,-1,sizeof(mx));
memset(my,-1,sizeof(my));
int ans=0;
for(int i=0;i<n;i++)
{
memset(vis,false,sizeof(vis));
ans+=path(i);
}
return ans;
}
int main()
{
int k,a,b,cas=0;
while(scanf("%d %d %d",&n,&m,&k)==3)
{
memset(mat,false,sizeof(mat));
for(int i=0;i<k;i++)
{
scanf("%d %d",&a,&b);
a--,b--;
mat[a][b]=1;
}
int ans=match();
int maxx=0;
int tmp[N];
memcpy(tmp,mx,sizeof(mx));
for(int i=0;i<n;i++)
{
if(tmp[i]==-1) continue;
int y=tmp[i];
mat[i][y]=false;
int tmp=match();
if(tmp<ans)
maxx++;
mat[i][y]=true;
}
printf("Board %d have %d important blanks for %d chessmen.\n",++cas,maxx,ans);
}
return 0;
}
hdu1507 Uncle Tom's Inherited Land*
//很经典的模型，类似于用1*2的木板覆盖空格，很明显，每一个木板覆盖的一定是一个奇点和一个偶点
//这就形成了一一对应的匹配关系，相邻的空格奇点向偶点连边，求最大匹配
//关键是输出路径，注意判重
View Code
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 5050;
int n,m,mx[N],my[N],hash1[110][110];
bool mat[110][110],vis[N];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct point
{
int i,j;
point(){}
point(int a,int b):i(a),j(b){}
};
point xx[N],yy[N];
vector<int> g[N];
//很经典的模型，类似于用1*2的木板覆盖空格，很明显，每一个木板覆盖的一定是一个奇点和一个偶点
//这就形成了一一对应的匹配关系，相邻的空格奇点向偶点连边，求最大匹配
//关键是输出路径，注意判重
int path(int s)
{
vector<int>::iterator it=g[s].begin();
for(;it!=g[s].end();it++)
{
int v=*it;
if(!vis[v])
{
vis[v]=true;
if(my[v]==-1 || path(my[v]))
{
mx[s]=v;
my[v]=s;
return 1;
}
}
}
return 0;
}
int match()
{
int ans=0;
memset(my,-1,sizeof(my));
memset(mx,-1,sizeof(mx));
for(int i=0;i<n;i++)
{
if(g[i].size()==0) continue;
memset(vis,false,sizeof(vis));
ans+=path(i);
}
return ans;
}
int main()
{
int nn,mm,k,a,b;
while(scanf("%d %d",&nn,&mm)==2 && (nn||mm))
{
scanf("%d",&k);
memset(mat,false,sizeof(mat));
while(k--)
{
scanf("%d %d",&a,&b);
a--,b--;
mat[a][b]=true;
}
n=m=0;
for(int i=0;i<nn;i++)
for(int j=0;j<mm;j++)
if(!mat[i][j] && ((i+j)&1))
{
xx[n]=point(i,j);
hash1[i][j]=n++;//将每一个点重新标号，并且保持坐标
}
else if(!mat[i][j])
{
yy[m]=point(i,j);
hash1[i][j]=m++;
}
for(int i=0;i<nn;i++)
for(int j=0;j<mm;j++)
if(!mat[i][j] && ((i+j)&1))//奇点向偶点连边
{
for(int t=0;t<4;t++)
{
int x=i+dir[t][0];
int y=j+dir[t][1];
if(x<0 || x>=nn || y<0 || y>=mm || mat[x][y])
continue;
g[hash1[i][j]].push_back(hash1[x][y]);
}
}
int ans=match();
printf("%d\n",ans);
memset(vis,false,sizeof(vis));
for(int i=0;i<n;i++)
{
if(mx[i]!=-1 && !vis[mx[i]])
{
int y=mx[i];
vis[y]=true;//注意要判重
printf("(%d,%d)--(%d,%d)\n",xx[i].i+1,xx[i].j+1,yy[y].i+1,yy[y].j+1);
}
}
puts("");
for(int i=0;i<n;i++)
g[i].clear();
}
return 0;
}
//每一个数字可以用其对应的行或列覆盖，那么对于每一个点，对应的行坐标向列坐标连边，
//那么求变成求最小点覆盖了，选择最少的行或列覆盖所有的边，每一条边对应一个点；
//当然，对应每一种数字，要单独判断
View Code
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 101;
vector<int> g[N *N];
int map[N][N], n, k, num[N], my[N];
bool flag[55], vis[N];
int path(int s)
{
vector<int>::iterator it = g[s].begin();
for(; it != g[s].end(); it++)
{
int v = *it;
if(!vis[v])
{
vis[v] = true;
if(my[v] == -1 || path(my[v]))
{
my[v] = s;
return 1;
}
}
}
return 0;
}
bool match(int u)
{
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
{
if(map[i][j] == u)
g[i].push_back(j);
}
int ans = 0;
memset(my, -1, sizeof(my));
for(int i = 0; i < n; i++)
{
if(g[i].size() == 0)continue;
memset(vis, false, sizeof(vis));
ans += path(i);
}
for(int i = 0; i < n; i++)
g[i].clear();
if(ans <= k)
return true;
return false;
}
void solve()
{
memset(flag, false, sizeof(flag));
int t = 0, ans[51];
for(int i = 1; i <= 50; i++)
if(num[i])
{
if(!match(i))
ans[t++] = i;
}
if(t == 0)
{
puts("-1");
return ;
}
printf("%d", ans[0]);
for(int i = 1; i < t; i++)
printf(" %d", ans[i]);
puts("");
return ;
}
int main()
{
while(scanf("%d %d", &n, &k) == 2 && (n || k))
{
memset(num, 0, sizeof(num));
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
{
scanf("%d", &map[i][j]);
num[map[i][j]]++;
}
solve();
}
return 0;
}
//二分图，奇点文物的关键点只可能与偶点的文物冲突
//注意，要先枚举所有文物再判断奇偶，保证奇点向偶点连边
//最小覆盖，选最少的点覆盖所有冲突
View Code
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1255;
int mat[55][55],n,m,hash1[55][55],my[N];
int dir[12][2] = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2},
{1, 2}, {2, 1}, {2, -1}, {1, -2},
{-1, 0}, {0, 1}, {1, 0}, {0, -1} };
bool vis[N];
vector<int> g[N];
//二分图，奇点文物的关键点只可能与偶点的文物冲突
//注意，要先枚举所有文物再判断奇偶，保证奇点向偶点连边
//最小覆盖，选最少的点覆盖所有冲突
int path(int s)
{
vector<int>::iterator it=g[s].begin();
for(;it!=g[s].end();it++)
{
int v=*it;
if(!vis[v])
{
vis[v]=true;
if(my[v]==-1 || path(my[v]))
{
my[v]=s;
return 1;
}
}
}
return 0;
}
int match()
{
int ans=0;
memset(my,-1,sizeof(my));
for(int i=0;i<n;i++)
{
if(g[i].size()==0) continue;
memset(vis,false,sizeof(vis));
ans+=path(i);
}
return ans;
}
int main()
{
int r,c,cas=0;
while(scanf("%d %d",&r,&c)==2 && (r||c))
{
n=m=0;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
{
scanf("%d",&mat[i][j]);
if(mat[i][j]!=-1)
{
if((i+j)&1)
hash1[i][j]=n++;
else hash1[i][j]=m++;
}
}
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
{
if(mat[i][j]==-1)
continue;
for(int k=0;k<12;k++)
{
if(!(mat[i][j]&(1<<k)))
continue;
int x=i+dir[k][0];
int y=j+dir[k][1];
if(x<0 || x>=r || y<0 || y>=c || mat[x][y]==-1)
continue;
if((i+j)&1)//这里跟之前的有所不同，因为二分图所有的边都是冲突的边，需要先枚举所有文物再判断奇偶点才能保证加入了所有的冲突边
g[hash1[i][j]].push_back(hash1[x][y]);
else g[hash1[x][y]].push_back(hash1[i][j]);
}
}
int ans=match();
printf("%d. %d\n",++cas,ans);
for(int i=0;i<n;i++)
g[i].clear();
}
return 0;
}
题意：有n Cat 和m只Dog ，现在有k观众，每一个观众只能选择给一只Cat（或 Dog） 投支持票，给一只Dog(或Cat） 投反对票，只有当观众支持的Cat 或 Dog没有被淘汰时，该观众会继续观看。。。问最多有多少观众留下
分析：一开始不知道怎么建图，，想着想着，突然想到最大权二分匹配了，也确实可以，每一个Cat i 和 Dog j 的匹配都有一个权值，结果悲剧的TLE，，，再想想，其实对象取错了，求的留下的观众，对象自然是观众了，，，如何寻找观众与观众的匹配？？当然是寻找冲突的匹配，对于同一只Cat 或者Dog ，如果观众i 和 观众j 一个投支持票，而另一个投反对票，那么俩者冲突，建立匹配边，那么就变成了一个求最大的不与其他观众冲突的观众的个数了（最大独立点集== N （点数）- 最大匹配）
通过这道题，还学到了一个知识点，就是sscanf， 用俩处理字符串还是听不错的
View Code
#include<iostream> #include<algorithm> using namespace std; const int N = 500+10; int nx,ny,match[N]; bool vis[N],mat[N][N]; struct Vote { int l,h; }Cat[N],Dog[N]; int path(int s) { for(int i=0;i<ny;i++) { if(mat[s][i] && !vis[i]) { vis[i]=true; if(match[i]==-1 || path(match[i])) { match[i]=s; return 1; } } } return 0; } int main() { char str1[20],str2[20]; int T,k,a,b,n,m; scanf("%d",&T); while(T--) { scanf("%d %d %d",&n,&m,&k); nx=ny=0; for(int i=0;i<k;i++) { scanf("%s %s",str1,str2); sscanf(str1,"%*c%d",&a);//%*c 表示滤掉第一个匹配的字符 sscanf(str2,"%*c%d",&b); if(str1[0]=='C') { Cat[nx].l=a; Cat[nx++].h=b; } else { Dog[ny].l=a; Dog[ny++].h=b; } } memset(mat,false,sizeof(mat)); for(int i=0;i<nx;i++) for(int j=0;j<ny;j++) { if(Cat[i].l==Dog[j].h || Cat[i].h==Dog[j].l) mat[i][j]=true; } memset(match,-1,sizeof(match)); int ans=0; for(int i=0;i<nx;i++) { memset(vis,false,sizeof(vis)); ans+=path(i); } printf("%d\n",k-ans); } return 0; }