Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3216 Repairing Company---多源最短路+二分图匹配

Posted on 2010-08-02 18:53 Uriel 阅读(315) 评论(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;
}
            

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理