首页 > 代码库 > POJ 3216 Repairing Company【Floyd + 最小路径覆盖】

POJ 3216 Repairing Company【Floyd + 最小路径覆盖】

2024-07-18 08:27:00   222人阅读

大意：

有n个任务，每个任务有三个属性：所在街区，最晚开始时间，执行需要时间

告诉你一个矩阵代表街区间到达时间

告诉你每个任务的三个属性

问最少需要多少人去完成所有任务

 

分析：

floyd处理处任意两个街区的到达时间

拆点   左边集合为n个任务    右边集合跟左边相同

i任务能够到达j任务就从左集合引一条边到右集合

求最小路径覆盖   

最小路径覆盖 = n - 最大匹配

 

代码：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6  7 const int maxn = 25; 8 const int INF = 1000000000; 9 int mat[maxn][maxn];10 struct Task {11     int block, start, time;12 }task[205];13 14 void Floyd(int n) {15     for(int k = 1; k <= n; k++) {16         for(int i = 1; i <= n; i++) {17             for(int j = 1; j <= n; j++) {18                 if(mat[i][k] + mat[k][j] < mat[i][j]) {19                     mat[i][j] = mat[i][k] + mat[k][j];20                 }21             }22         }23     }24 }25 26 vector<int> G[205];27 int vis[205];28 int Link[205];29 bool Find(int u) {30     for(int i = 0; i < G[u].size(); i++) {31         int v = G[u][i];32         if(!vis[v]) {33             vis[v] = 1;34             if(Link[v] == -1 || Find(Link[v]) ) {35                 Link[v] = u;36                 return true;37             }38         }39     }40     return false;41 }42 43 int solve(int m) {44     int cnt = 0;45     memset(Link, -1, sizeof(Link));46     for(int i = 0; i < m; i++) {47         if(G[i].size()) {48             memset(vis, 0, sizeof(vis));49             if(Find(i)) cnt++;50         }51     }52     return cnt;53 }54 55 bool check(int i, int j) {56     int need_time = mat[task[i].block][task[j].block];57     if(need_time < INF) {58         if(task[i].start + task[i].time + need_time <= task[j].start) {59             return true;60         }61     }62     return false;63 }64 65 int main() {66     int n, m;67     while(scanf("%d %d",&n, &m) && n + m) {68         for(int i = 1; i <= n; i++) {69             for(int j = 1; j <= n; j++) {70                 scanf("%d",&mat[i][j]);71                 if(mat[i][j] == -1) mat[i][j] = INF;72             }73         }74         Floyd(n);75         for(int i = 0; i < m; i++) {76             G[i].clear();77             scanf("%d %d %d",&task[i].block, &task[i].start, &task[i].time);78         }79         for(int i = 0; i < m; i++) {80             for(int j = 0; j < m; j++) {81                 if(i == j) continue;82                 if(check(i, j) ) G[i].push_back(j);83             }84         }85         printf("%d\n", m - solve(m));86     }87     return 0;88 }
View Code

 


联系
我们