最近使用开发的过程中出现了一个小问题，顺便记录一下原因和方法--最小匹配
最小径路盖覆，用floyd求最短路，注意匹配时定点不是n个而是Q个，每一个都会可能有多个人须要物礼
把每一个点根据间时排下序得免超时
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 1010
#define inf 0x3fffffff
int map[N][N],tch[N],link[N],match[N],n;
bool mp[N][N];
struct op
{
int x,t;
}p[1010];
int cmp(const void *a,const void *b)
{
struct op *c,*d;
c=(struct op *)a;
d=(struct op *)b;
if(c->t!=d->t)
return c->t-d->t;
return c->x-d->x;
}
int find(int u)
{
int i;
for(i=0;i<n;i++)
{
if(!link[i]&&mp[u][i])
{
link[i]=1;
if(match[i]==-1||find(match[i]))
{
match[i]=u;
tch[u]=i;
return 1;
}
}
}
return 0;
}
void floyd()
{
int i,j,k;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(map[i][j]>map[i][k]+map[k][j])
map[i][j]=map[i][k]+map[k][j];
}
int main()
{
int i,j,k,T,sum,m,Q,x,y,c,op=1;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&Q);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
map[i][j]=inf;
map[i][i]=0;
}
memset(mp,false,sizeof(mp));
for(i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&c);
if(map[x][y]>c)
map[x][y]=map[y][x]=c;
}
floyd();
for(i=0;i<Q;i++)
scanf("%d%d",&p[i].x,&p[i].t);
qsort(p,Q,sizeof(p[0]),cmp);
for(i=0;i<Q;i++)
for(j=i+1;j<Q;j++)
{
if(p[j].t-p[i].t>=map[p[i].x][p[j].x])
mp[i][j]=true;
}
sum=0;
n=Q;
memset(match,-1,sizeof(match));
memset(tch,-1,sizeof(tch));
for(i=0;i<Q;i++)
{
if(tch[i]!=-1)continue;
memset(link,0,sizeof(link));
sum+=find(i);
}
printf("Case %d: ",op++);
printf("%d\n",n-sum-1);
}
return 0;
}
文章结束给大家分享下程序员的一些笑话语录：
女人篇
有的女人就是Windows虽然很优秀，但是安全隐患太大。
有的女人就是MFC她条件很好，然而不是谁都能玩的起。
有的女人就是C#长的很漂亮，但是家务活不行。
有的女人就是C++,她会默默的为你做很多的事情。
有的女人就是汇编虽然很麻烦，但是有的时候还得求它。
有的女人就是SQL，她会为你的发展带来莫大的帮助。