题目来源：http://poj.org/problem?id=1486
题意：
算出所有独一无二的字母与数字的组合，使二分图完全匹配
我以为所有点都要独一无二匹配时输出匹配方法
题解：
先得到一个完全匹配，然后每次割边，如果某次割边后可以完全匹配，则这条边不是必须的匹配
如果没有完全匹配或必要的组合数为零时，输出none
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=100;
bool ma[maxn][maxn],used[maxn];
int match[maxn];
int ans[maxn];
int cnd=0,n;
struct Node
{
int a,b,c,d;
}node[maxn];
bool dfs(int x)
{
if(used[x]==1)return 0;
else used[x]=1;
for(int i=1;i<=n;i++)
{
if(ma[x][i]==0)continue;
if(match[i]==0||dfs(match[i]))
{
match[i]=x;
return 1;
}
}
return 0;
}
int hug()
{
for(int i=1;i<=n;i++)
{
match[i]=0;
}
int res=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)used[j]=0;
if(dfs(i))res++;
}
return res;
}
int main()
{
while(scanf("%d",&n)==1)
{
if(n==0)break;
cnd++;
printf("Heap %d\n",cnd);
memset(ma,0,sizeof(ma));
for(int i=1;i<=n;i++)
scanf("%d %d %d %d",&node[i].a,&node[i].b,&node[i].c,&node[i].d);
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
for(int j=1;j<=n;j++)
{
if(x>=node[j].a&&x<=node[j].b&&y>=node[j].c&&y<=node[j].d)
{
ma[i][j]=1;
}
}
}
if(hug()==n)
{
for(int i=1;i<=n;i++)
ans[i]=match[i];
int fla=n;
for(int i=1;i<=n;i++)
{
int k=ans[i];
ma[k][i]=0;
if(hug()==n)
{
ans[i]=0;fla--;
}
ma[k][i]=1;
}
if(fla==0)
{
cout<<"none"<<endl;
}
else
{
int k=0;
for(int i=1;i<=n;i++)
{
if(ans[i]==0)continue;
printf("(%c,%d)",'A'+i-1,ans[i]);
k++;
if(k==fla)cout<<endl;
else cout<<" "; }
}
}
else
{
cout<<"none"<<endl;
}
cout<<endl;
}
return 0;
}