poj 3216 (最小路径覆盖)
题意：有n个地方，m个任务，每个任务给出地点，开始的时间和完成需要的时间，问最少派多少工人去可以完成所有的任务。给出任意两点直接到达需要的时间，-1代表不能到达。
思路：很明显的最小路径覆盖问题，刚开始脑子抽了，没求最短路直接就做了，题目只给了两点间直接到达的时间，还可以间接到达，用floyd求出最短路。。。
#include<stdio.h>#include<string.h>const int N=300;const int inf=0x3fffffff;int head[N],num,match[N],link[N],map[30][30],n,m;struct edge{int st,ed,next;}e[N*N];struct node{int id,stime,etime;}P[N];void addedge(int x,int y){e[num].st=x;e[num].ed=y;e[num].next=head[x];head[x]=num++;}int find(int u)//二分匹配{int i,v;for(i=head[u];i!=-1;i=e[i].next){v=e[i].ed;if(link[v]==0){link[v]=1;if(match[v]==-1||find(match[v])==1){match[v]=u;return 1;}}}return 0;}void Floyd()//最短路{int i,j,k;for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;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;while(scanf("%d%d",&n,&m),n+m){memset(map,-1,sizeof(map));for(i=1;i<=n;i++)for(j=1;j<=n;j++){scanf("%d",&map[i][j]);if(map[i][j]==-1)map[i][j]=inf;}for(i=1;i<=m;i++){scanf("%d%d%d",&P[i].id,&P[i].stime,&P[i].etime);P[i].etime+=P[i].stime;}Floyd();memset(head,-1,sizeof(head));num=0;for(i=1;i<=m;i++){for(j=1;j<=m;j++){if(i==j||map[i][j]>=inf)continue;if(P[i].etime+map[P[i].id][P[j].id]<=P[j].stime)//完成i任务后可以赶到jaddedge(i,j);}}memset(match,-1,sizeof(match));int sum=0;for(i=1;i<=m;i++){memset(link,0,sizeof(link));sum+=find(i);}printf("%d\n",m-sum);}return 0;}