Posted on 2010-08-02 18:53
Uriel 閱讀(325)
評論(0) 編輯 收藏 引用 所屬分類:
POJ 、
圖論
繼續(xù)糾結(jié)各種建圖...
題意：Q個(gè)blocks，M個(gè)tasks
Q*Q的矩陣，給出每個(gè)邊的情況
對于每個(gè)task，已知pi(位于哪個(gè)block)，ti(最遲開始時(shí)間)，di(每個(gè)人完成它所需時(shí)間)
思路：建圖還是很糾結(jié)，看了大牛們的思路...
先用floyd求兩點(diǎn)之間的最短路，然后建圖。
建圖方法是如果task i 的開始時(shí)間+task i 需要的時(shí)間+從task i 所在地到task j 所在地所需時(shí)間<=task j的開始時(shí)間，則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;
}