Posted on 2010-08-02 18:53
Uriel 阅读(317)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
图论
继续纠结各种建图...
题意：Q个blocks，M个tasks
Q*Q的矩阵，给出每个边的情况
对于每个task，已知pi(位于哪个block)，ti(最迟开始时间)，di(每个人完成它所需时间)
思路：建图还是很纠结，看了大牛们的思路...
先用floyd求两点之间的最短路，然后建图。
建图方法是如果task i 的开始时间+task i 需要的时间+从task i 所在地到task j 所在地所需时间<=task j的开始时间，则i，j连一条边
然后就是求最小路径覆盖
代码如下：
//Problem: 3216 User: Uriel
//Memory: 552K Time: 63MS
//Language: G++ Result: Accepted
//floyd+Bipartite Graph
//2010.08.02
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define INF 1000000000
struct work
{
int p,t,d;
}b[210];
int Q,M;
int d[210][210],use[210],link[210],adj[210][210],n[210];
void floyd(){
for(int k=1;k<=Q;++k)
for(int i=1;i<=Q;++i)
for(int j=1;j<=Q;++j)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
bool ok(int i,int j){
if(b[i].t+b[i].d+d[b[i].p][b[j].p]<=b[j].t)return true;
return false;
}
void Build_Graph(){
int i,j,k;
memset(adj,0,sizeof(adj));
for(i=1;i<=M;i++){
for(j=1;j<=M;j++){
if(i==j)continue;
if(ok(i,j))adj[i][++n[i]]=j;
}
}
}
int can(int t){
int i,j;
for(i=1;i<=n[t];++i){
j=adj[t][i];
if(!use[j]){
use[j]=1;
if(link[j]==-1 || can(link[j])){
link[j]=t;
return 1;
}
}
}
return 0;
}
int maxMatch(){
int i,num=0;
memset(link,-1,sizeof(link));
for(i=1;i<=M;++i){
memset(use,0,sizeof(use));
if(can(i))num++;
}
return num;
}
int main(){
int i,j,k;
while(scanf("%d %d",&Q,&M),Q|M){
for(i=1;i<=Q;++i){
for(j=1;j<=Q;++j){
scanf("%d",&d[i][j]);
if(d[i][j]==-1)d[i][j]=INF;
}
}
floyd();
for(i=1;i<=M;++i){
scanf("%d %d %d",&b[i].p,&b[i].t,&b[i].d);
n[i]=0;
}
Build_Graph();
printf("%d\n",M-maxMatch());
}
return 0;
}