分析：将行和列缩点，即行对应二分图的X部，列对应二分图的Y部，然后交点为连接该行和该列的一条边。匹配时每点都会把整行整列占了，因此就不会出现冲突了。
传送门：hdu1281 棋盘游戏
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 110
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
int match[N],vis[N],n,m,k;
int g[N][N],a[N*N][],x,y;
int dfs(int u)
{
for(int i=;i<=m;i++)
{
if(!vis[i]&&g[u][i])
{
vis[i]=;
if(match[i]==-||dfs(match[i]))
{
match[i]=u;
return ;
}
}
}
return ;
}
int hungary()
{
memset(match,-,sizeof(match));
int ans=;
for(int i=;i<=n;i++)
{
memset(vis,,sizeof(vis));
if(dfs(i))ans++;
}
return ans;
}
int main()
{
int cas=;
while(scanf("%d%d%d",&n,&m,&k)>)
{
memset(g,,sizeof(g));
for(int i=;i<=k;i++)
{
scanf("%d%d",&x,&y);
g[x][y]=;
a[i][]=x;
a[i][]=y;
}
int res=hungary();
int ans=;
for(int i=;i<=k;i++)
{
g[a[i][]][a[i][]]=;
int maxn=hungary();
if(maxn<res)ans++;
g[a[i][]][a[i][]]=;
}
printf("Board %d have %d important blanks for %d chessmen.\n",cas++,ans,res);
}
}
传送门：hdu2819 Swap
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 110
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
int match[N],vis[N],n,m;
int g[N][N],a[N*N][];
int dfs(int u)
{
for(int i=;i<=n;i++)
{
if(!vis[i]&&g[u][i])
{
vis[i]=;
if(match[i]==-||dfs(match[i]))
{
match[i]=u;
return ;
}
}
}
return ;
}
int hungary()
{
memset(match,-,sizeof(match));
int ans=;
for(int i=;i<=n;i++)
{
memset(vis,,sizeof(vis));
if(dfs(i))ans++;
}
return ans;
}
int main()
{
int cas=;
while(scanf("%d",&n)>)
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&g[i][j]);
int res=hungary();
if(res!=n)
{
puts("-1");
continue;
}
int sum=,i,j;
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
{
if(match[j]==i)break;
}
if(i==j)continue;
sum++;
a[sum][]=i;
a[sum][]=j;
swap(match[i],match[j]);
}
printf("%d\n",sum);
for(int i=;i<=sum;i++)
printf("C %d %d\n",a[i][],a[i][]);
}
}