当前位置：首页 > news >正文

POJ3216 最小路径覆盖

news 来源：原创 2024/5/19 19:36:53

首先说一下题意，Q个区域，M个任务，每个区域任务可能有多个，然后给你个到各地所需时间的矩阵，每个任务都有开始和持续时间，问最少需要多少工人？每个工人只能同时执行一个任务。

通过题意，我的瞬间反应就是先把点拆开再说，因为每个区域可能有多个任务，所以把每个任务都当做一点处理，之后就需要考虑一件事情，一个工人在Qi区域做完之后是不是应该去一个离他最近且正好有任务的地方Qj，那么他从Qi到Qj是不是应该走最近的路线？下一步就出来了，求出所有区域之间的最短距离，用floyd一键搞定。然后就可以建图（有向的）了，把能衔接起来的任务统统连上，按照上一个任务的开始时间+持续时间+到下一点的时间<=下一点的开始时间来连边（不用换区域的到下一点的时间为零），那么此时的问题就变成了多少个工人能把图走完？即最小路径覆盖，直接匈牙利算法搞定。

好了上代码

  1 #include<cstdio>            
  2 #include<cstring>
  3 #include<iostream>
  4 #include<vector>
  5 #define maxn 500
  6 #define inf 0xfffffff
  7 using namespace std;
  8 
  9 struct edge
 10 {
 11     int pos,realpos,start,need;
 12 }rela[maxn];
 13 vector<int> q[maxn];
 14 int mize[maxn][maxn],point[maxn];
 15 int vis[maxn],link[maxn];
 16 int n,m,sum;
 17 void init()
 18 {
 19     for(int i=0;i<=maxn;i++)
 20         q[i].clear();
 21     memset(rela,0,sizeof(rela));
 22     memset(mize,0,sizeof(mize));
 23     memset(point,0,sizeof(point));
 24     for(int a=1;a<=n;a++)
 25         for(int b=1;b<=n;b++)
 26         {
 27             scanf("%d",&mize[a][b]);
 28             if(mize[a][b]==-1) mize[a][b]=inf;
 29         }
 30 
 31     for(int c=1;c<=m;c++)
 32     {
 33         scanf("%d %d %d",&rela[c].pos,&rela[c].start,&rela[c].need);
 34         int p=0;
 35         for(int d=1;d<c;d++)
 36         {
 37             if(rela[d].pos==rela[c].pos) p++;
 38         }
 39         rela[c].realpos=rela[c].pos+n*p;
 40         point[rela[c].realpos]=1;
 41         if(sum<rela[c].realpos) sum=rela[c].realpos;
 42     }
 43 }
 44 void floyd()
 45 {
 46     for(int i=1;i<=n;i++)
 47     {
 48         for(int j=1;j<=n;j++)
 49         {
 50            for(int k=1;k<=n;k++)
 51            {
 52                mize[j][k]=mize[j][k]<mize[i][k]+mize[j][i]?mize[j][k]:mize[i][k]+mize[j][i];
 53            }
 54         }
 55     }
 56 
 57 
 58 }
 59 void set_map()
 60 {
 61     for(int i=1;i<=m;i++)
 62     {
 63         int realpos=rela[i].realpos,pos=rela[i].pos,time=rela[i].need+rela[i].start;
 64         for(int j=1;j<=m;j++)
 65         {
 66             if(j==i) continue;
 67             int a=rela[j].realpos,b=rela[j].pos,t=rela[j].start;
 68      //       if(mize[pos][b]==-1||mize[b][pos]==-1) continue;
 69             if(time+mize[pos][b]<=t)     // 矩阵式对称的  怎么写都无所谓
 70             {
 71                 q[realpos].push_back(a);
 72            //     q[a].push_back(realpos);
 73             }
 74         }
 75     }
 76  /*   for(int i=1;i<=8;i++)
 77     {
 78         if(q[i].size()==0) continue;
 79         cout<<i<<": "<<endl;
 80         for(int j=0;j<q[i].size();j++)
 81         {
 82             cout<<q[i][j]<<" ";
 83         }
 84         cout<<endl;
 85     }*/
 86 }
 87 int dfs(int x)
 88 {
 89     for(int i=0;i<q[x].size();i++)
 90     {
 91           int y=q[x][i];
 92           if(!vis[y])
 93           {
 94               vis[y] = true;
 95              if(link[y]== -1||dfs(link[y]))
 96              {
 97                   link[y] = x;
 98                   return true;
 99              }
100           }
101     }
102     return false;
103 }
104 void solve()
105 {
106     int s=0;
107     memset(link,-1,sizeof(link));
108     for(int i=1;i<=sum;i++)
109     {
110         if(point[i]==0) continue;
111         memset(vis,0,sizeof(vis));
112         if(dfs(i)) s++;
113     }
114     printf("%d\n",m-s);
115 }
116 int main()
117 {
118     while(scanf("%d%d",&n,&m)!=EOF)
119     {
120         if(n==0&&m==0) break;
121         sum=0;
122         init();
123         floyd();
124         set_map();
125         solve();
126     }
127     return 0;
128 }