POJ 3216 最短路径匹配+floyd

题意：

给出Q的街道和M个任务

然后给出i*j的矩阵..表示第i个街道到第j个街道的距离其中-1表示不可到达

然后接下来M行有 p t d 表示任务在p街道开始时间是t 完成工作花费时间是d

问最少派出多少人可以完成M个任务

思路：

用floyd求出街道之间的最短距离

根据两个任务距离花费时间+完成工作花费时间+工作开始时间<=第二个工作开始时间

确定两个任务是否可以由一个人完成..

然后得到一个二分图..

然后用n-最大匹配求出最短路径匹配

Tips：

※ 因为建图是从0开始建的..而输入给的街道是从1开始算的..所以不对..

※ floyd求最短路时候直接在G的基础上算就好了~不用另开一个dis..!!!!

Code：

View Code

  1 #include <stdio.h>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 const int INF = 0X1f1f1f1f;
  6 #define clr(x) memset(x, 0, sizeof(x))
  7 
  8 struct Task
  9 {
 10     int p;
 11     int t;
 12     int d;
 13 }task[210];
 14 
 15 struct Edge
 16 {
 17     int next;
 18     int to;
 19 }edge[1000000];
 20 int tot;
 21 int head[210];
 22 
 23 int link[210];
 24 int vis[210];
 25 int G[25][25], dis[25][25];
 26 int sum, n;
 27 int Q, M;
 28 
 29 void floyd()
 30 {
 31     for(int k = 0; k < Q; ++k)
 32     for(int i = 0; i < Q; ++i) {
 33         for(int j = 0; j < Q; ++j)
 34           G[i][j] = G[i][j] < G[i][k]+G[k][j]?G[i][j]:G[i][k]+G[k][j];
 35     }
 36   }
 37 
 38 void add(int s, int u)
 39 {
 40     edge[tot].to = u;
 41     edge[tot].next = head[s];
 42     head[s] = tot++;
 43 }
 44 
 45 
 46 int dfs(int x)
 47 {
 48     for(int i = head[x]; i != 0; i = edge[i].next){
 49         int y = edge[i].to;
 50         if(!vis[y]){
 51             vis[y] = true;
 52             if(link[y] == 0 || dfs(link[y])){
 53                 link[y] = x;
 54                 return true;
 55             }
 56         }
 57     }
 58     return false;
 59 }
 60 
 61 void solve()
 62 {
 63     clr(link);
 64     sum = 0;
 65     for(int i = 1; i <= n; ++i){
 66         clr(vis);
 67         if(dfs(i))
 68             sum++;
 69     }
 70 }
 71 
 72 
 73 int main()
 74 {
 75     int i, j, k;
 76     while(scanf("%d %d", &Q, &M) != EOF)
 77     {
 78         if(Q == 0 || M == 0) break;
 79         clr(G), clr(dis), clr(head);
 80         n = M;
 81         tot = 1;
 82 
 83         for(i = 0; i < Q; ++i)
 84         for(j = 0; j < Q; ++j) {
 85             scanf("%d", &G[i][j]);
 86             if(G[i][j] == -1) G[i][j] = INF;
 87         }
 88         for(i = 1; i <= n; ++i)
 89             scanf("%d %d %d", &task[i].p, &task[i].t, &task[i].d);
 90 
 91         floyd();
 92         for(i = 1; i <= n; ++i)
 93         for(j = 1; j <= n; ++j)
 94         if(i != j) {
 95             if(task[i].d + task[i].t + G[task[i].p-1][task[j].p-1] <= task[j].t)
 96             add(i, j);
 97         }
 98         solve();
 99 
100         printf("%d\n", n-sum);
101     }
102     return 0;
103 }