Poj 2060 Taxi Cab Scheme
题意：在一个矩形城市里面，有间出租车公司收到翌日的预订行程M个，每个给出起点、终点坐标，两个地点之间的车程就是那两个点之间的曼哈顿距离，车起码要在一个行程的出发时间前一分钟到起点。求最少要多少出租车才够完成所有预订？
分析：记A，B是两个行程的起点，A'，B'分别是终点，假如由A'到B的时间还在B的规定时间前，那么要走完AA',BB'要用的出租车就只需要一台。添加一条有向边<A',B>，把图建好之后，求出最小路径覆盖就是答案。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
const int N=505;
bool map[N][N];
bool vis[N];
int match[N];
int m;
bool Dfs (int u)
{
for (int v=1;v<=m;v++)
if (vis[v] == false && map[u][v])
{
vis[v]=true;
if (match[v]==0 || Dfs(match[v]))
{
match[v]=u;
return true;
}
}
return false;
}
struct Point
{
int st,et;
int sx,sy,ex,ey,dis,len;
void Get ()
{
scanf("%d:%d %d%d%d%d",&st,&et,&sx,&sy,&ex,&ey);
sx++,sy++,ex++,ey++;
st=st*60+et;
dis=abs(sx-ex)+abs(sy-ey);
et=st+dis;
}
bool Cal (const Point& b) const
{
int d=abs(ex-b.sx)+abs(ey-b.sy);
if (d+et<b.st) //严格小于,<=,WA
return true;
return false;
}
}data[N];
int main ()
{
int T;
scanf("%d",&T);
for (int Cas=1;Cas<=T;Cas++)
{
memset(map,false,sizeof(map));
memset(match,0,sizeof(match));
scanf("%d",&m);
int i,sum;
for (i=1;i<=m;i++)
data[i].Get();
/*求最大匹配*/
for (i=1;i<m;i++)
for (int j=i+1;j<=m;j++)
{
if (data[i].Cal(data[j]))
map[i][j]=true;
}
for (sum=0,i=1;i<=m;i++)
{
memset(vis,false,sizeof(vis));
if (Dfs(i))
sum++;
}
printf("%d\n",m-sum);
}
return 0;
}
Poj 1466 Girls and Boys
题意：一些人开始研究一种浪漫的关系，这种浪漫的关系被定义在一个男孩和一个女孩之间。
这项研究给出了，每个学生的该种关系列表已经给出，但他们想知道满足下面条件集合元素的最大个数是多少：该集合中任意两个人都没有上述关系。
思路：如果将有这种关系的两个人用边连起来，那么最终要求的集合中两两无边，对应图论中最大独立集。
最大独立集= n - 最小点覆盖。 最小点覆盖 = 二分图最大匹配。
将每个人拆成两个点，a,b 有关系，就连一条a ->b的有向边。由于在寻找最大匹配时不是枚举其中一边的点，而是枚举两边的所有点，所以得到的ans为最大匹配数的两倍，因为每条匹配的边都算了两遍。
也就是说最终的匹配数应该是该图最大匹配的1/2.那么答案就出来了。
#include <cstdio>
#include <cstring>
const int N=505;
bool map[N][N];
bool vis[N];
int match[N];
int n,num;
bool Dfs (int u)
{
for (int v=0;v<n;v++)
if (vis[v] == false && map[u][v])
{
vis[v]=true;
if (match[v]==-1 || Dfs(match[v]))
{
match[v]=u;
return true;
}
}
return false;
}
void Input ()
{
int i,T,u,v;
num=0;
memset(map,false,sizeof(map));
memset(match,-1,sizeof(match));
for (i=0;i<n;i++)
{
scanf("%d: (%d)",&u,&T);
while (T--)
{
scanf("%d",&v);
map[u][v]=true;
}
}
}
int main ()
{
while (~scanf("%d",&n))
{
Input ();
for (int i=0;i<n;i++)
{
memset(vis,false,sizeof(vis));
if (Dfs(i))
num++;
}
printf("%d\n",n-num/2);
}
return 0;
}
Poj 2771 Guardian of Decency
题意：人和人之间如果满足4个条件的任意一条就不会成为夫妻，给定一些人，问从中最多能选多少人且保证任意两人不可能成为夫妻。
分析：由于条件之一是性别相同则不能成为夫妻。我们根据性别把人划分为两个集合，每个人是一个结点构成二分图，若两个人可能成为夫妻则连一条边。（同性之间不能成为夫妻，所以同集合内无边，此图必定为二分图）。题目要求是选出最多的人，且任意两人之间无边。这就是求二分图的最大独立集。只要用总人数－最大匹配数即可。
#include <cmath>
#include <cstdio>
#include <cstring>
const int N=505;
bool map[N][N];
bool vis[N];
int match[N];
int n,num,m,f;
struct Point
{
int h;
char m[105],s[105];
}male[N],female[N];
bool Dfs (int u)
{
for (int v=1;v<=f;v++)
if (vis[v] == false && map[u][v])
{
vis[v]=true;
if (match[v]==-1 || Dfs(match[v]))
{
match[v]=u;
return true;
}
}
return false;
}
bool Judge (Point a,Point b)
{
if (fabs(a.h-b.h)>40)
return false;
if (strcmp(a.m,b.m))
return false;
if (strcmp(a.s,b.s)==0)
return false;
return true;
}
void Input ()
{
int i,a;
char s[5];
memset(map,false,sizeof(map));
memset(match,-1,sizeof(match));
for (i=1;i<=n;i++)
{
scanf("%d%s",&a,s);
if (s[0]=='M')
{
male[++m].h=a;
scanf("%s%s",male[m].m,male[m].s);
}
else
{
female[++f].h=a;
scanf("%s%s",female[f].m,female[f].s);
}
}
for (i=1;i<=m;i++)
for (int j=1;j<=f;j++)
{
if (Judge(male[i],female[j]))
map[i][j]=true;
}
}
int main ()
{
#ifdef ONLINE_JUDGE
#else
freopen("read.txt","r",stdin);
#endif
int T;
scanf("%d",&T);
for (int Cas=1;Cas<=T;Cas++)
{
scanf("%d",&n);
num=m=f=0;
Input ();
for (int i=1;i<=m;i++)
{
memset(vis,false,sizeof(vis));
if (Dfs(i))
num++;
}
printf("%d\n",n-num);
}
return 0;
}
hdu 1150 Machine Schedule
题意：机器调度问题，有两台机器，分别有n和m种工作状态，现有k个任务，需要用这两种机器来完成，由于每更换一次机器的工作状态都需重启，怎样安排这些任务，使得机器的重启次数最少
思路：由于每个任务都可以用A或B机器的某种工作状态来完成，因此，对于每个任务，
可以把A，B的工作状态作为顶点，在对应的Ａ和Ｂ的工作状态间连线，则对于每条边的两个顶点，
因为每个任务都要完成，故至少要有一个顶点（某个机器的一种状态）存在，
这样这个问题就转化成了在这些顶点中选取尽量少的顶点（尽量少的工作状态，尽量少的重启次数），
使得每一条边都至少和其中一个点相关联，即最小点覆盖问题。二分图的最小点覆盖数=最大匹配数
#include <iostream>
using namespace std;
const int N=105;
bool map[N][N];
bool vis[N];
int match[N];
int n,m,k;
bool Dfs (int u)
{
for (int v=1;v<=m;v++)
if (vis[v] == false && map[u][v])
{
vis[v]=true;
if (match[v]==0 || Dfs(match[v]))
{
match[v]=u;
return true;
}
}
return false;
}
int main ()
{
while (scanf("%d",&n),n)
{
scanf("%d%d",&m,&k);
memset(map,false,sizeof(map));
memset(match,0,sizeof(match));
int i,a,b,sum;
for (i=1;i<=k;i++)
{
scanf("%*d%d%d",&a,&b);
if (a==0 || b==0) //初始状态为0,不用记录在改变次数中
continue;
map[a+1][b+1]=true;
}
/*求最大匹配*/
for (sum=0,i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
if (Dfs(i))
sum++;
}
printf("%d\n",sum);
}
return 0;
}
Hdu 1151 Air Raid
最小边覆盖=N-二分图最大匹配
#include <stdio.h>
#include <string.h>
const int N=125;
bool map[N][N];
bool vis[N];
int match[N];
int ni,ns;
bool DFS (int u)
{
for (int v=1;v<=ni;v++)
if (vis[v] == false && map[u][v])
{
vis[v]=true;
if (match[v]==0 || DFS(match[v]))
{
match[v]=u;
return true;
}
}
return false;
}
int main()
{
int T,i,temp1,temp2,ans;
scanf("%d",&T);
while (T--)
{
ans=0;
memset(map,false,sizeof(map));
memset(match,0,sizeof(match));
scanf("%d%d",&ni,&ns);
for (i=1;i<=ns;i++)
{
scanf("%d%d",&temp1,&temp2);
map[temp1][temp2]=true;
}
for (i=1;i<=ni;i++)
{
memset(vis,false,sizeof(vis));
if (DFS(i))
ans++;
}
printf("%d\n",ni-ans);
}
return 0;
}