本文主要是介绍poj 3216 Repairing Company,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
//可重复的最小路径覆盖
//先用floyd求传递闭包,最小覆盖数=N-最大匹配数
//若不可重复覆盖,则省去floyd过程
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n, m, ans;
const int INF=0xfffffff;
int match[205], linked[205][205], visited[205], a[205][205], p[205], t[205], d[205];
void init(){
int i, j, x, t1, t2, tmp;
memset(match, -1, sizeof(match));
ans=0;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++){
scanf("%d", &a[i][j]);
if(a[i][j]==-1)a[i][j]=INF;
}
for(i=1; i<=m; i++){
scanf("%d%d%d", &p[i], &t[i], &d[i]);
}
}
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(a[i][k]+a[k][j]<a[i][j])
a[i][j]=a[i][k]+a[k][j];
}
}
bool find(int x){
int i;
for(i=1; i<=m; i++){
if(t[x]+d[x]+a[p[x]][p[i]]<=t[i]&&!visited[i]){
visited[i]=1;
if(match[i]==-1||find(match[i])){
match[i]=x;
return 1;
}
}
}
return 0;
}
int main(){
//freopen("1.txt", "r", stdin);
int i, tmp;
while(scanf("%d%d", &n, &m)&&n){
init();
floyd();
for(i=1; i<=m; i++){
memset(visited, 0, sizeof(visited));
if(find(i))
ans++;
}
printf("%d\n", m-ans);
}
return 0;
}
这篇关于poj 3216 Repairing Company的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!