XMU 1040 Schedule 【拓扑排序】

1040: Schedule
Time Limit: 500 MS Memory Limit: 64 MB
Submit: 12 Solved: 2
[Submit][Status][Web Board]
Description

　　Resently, loneknight is doing research on job shop schedule problem(JSP for short). Let us take a look at JSP, there are n jobs and m machines, and every job must be processed in every machines, with a process time t[i,j] for job i being processed in machines j. One restrain is that the order for each job processed in machines is fixed, which means that for every job i, there is a process oder (a[i,1], a[i,2], ..., a[i,m]), job i must processed in machine a[i,1] first then a[i,2], ..., a[i,m]. Another restrain is every machine can process amost one job at any time, and every job can be process in amost one machine at any time. The problem is to find a schedule fit this restrains, that make the end time for all jobs, namely the makespan is minimum. Because of the fact that JSP is a NP-Complete problem, loneknight try using simulated anealing and gene algorithm to construct a heuristics algorithm for it. In developing such algorithm for JSP, he confront with a problem that if a schedule is already given, what is the makespan of this schedule, now this your task to solve this problem.

Input

　　There are mutiple test cases in the input. The beginning of each case is n, the number of jobs, m, the number of machines. (0 < n,m <= 300) Each follow three components. First is a nxm matrix, the value in the ith row and jth column is t[i,j]. (0 <= t[i,j] < 100) Second is a nxm matrix, the jobs process order, the value in the ith row and jth column is a[i,j]. Third is a mxn matrix the machines process order, the value in the ith row and jth column is b[i,j], (b[i,1], b[i,2], ..., b[i,n]) is the jobs process order in machine i, which means machine i process b[i,1] first, then b[i,2], ..., b[i,n]. (jobs and machines are indexed from 1) The input end with EOF

Output

　　For each test case, you should output a single integer, which is the makespan for that schedule in a single line.

Sample Input

3 3
83 86 77
15 93 35
86 92 49

3 1 2
3 1 2
1 3 2

1 2 3
1 3 2
1 2 3

Sample Output

495

HINT

Source

厦门大学第四届程序设计竞赛现场决赛 by Loneknight @ btALT

[Submit][Status][Web Board]

题目链接：

　　http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1040

题目大意：

　　有N个任务，M台机器，每个任务都必须在M台机器上运行一次才行。

　　任务i在机器j上的运行时间为T[i][j]

　　任务i必须满足先在机器A[i][1]上运行完才能在A[i][2]上,A[i][3]...A[i][m]上（按A[i]的顺序运行）

　　机器j必须满足先运行任务B[j][1]才能再运行B[j][2],...,B[j][n]（按B[j]顺序运行）

　　问所有任务完成的时间。

题目思路：

　　【拓扑排序】

　　首先可以知道，如果一个任务在某一个机器上做需要之前的步骤都已经完成，每一个机器做当前任务也需要之前的任务均完成

　　所以按照这个建图，按照第i个任务第j个机器设为节点A[i][j]。由于每个任务都有机器的先后顺序，每个机器也有任务的先后顺序

　　所以A[i][j]往它的下一个任务，下一个机器连一条边。

　　（一开始用SPFA写T了。。）　　

　　之后拓扑排序，每次更新最长路径的值。最后的答案即为解。

　　d[xx][yy]=max{ d[x][y]+t[xx][yy] }

  1 /****************************************************
  2     
  3     Author : Coolxxx
  4     Copyright 2017 by Coolxxx. All rights reserved.
  5     BLOG : http://blog.csdn.net/u010568270
  6     
  7 ****************************************************/
  8 #include<bits/stdc++.h>
  9 #pragma comment(linker,"/STACK:1024000000,1024000000")
 10 #define abs(a) ((a)>0?(a):(-(a)))
 11 #define lowbit(a) (a&(-a))
 12 #define sqr(a) ((a)*(a))
 13 #define mem(a,b) memset(a,b,sizeof(a))
 14 const double EPS=1e-8;
 15 const int J=10000;
 16 const int MOD=100000007;
 17 const int MAX=0x7f7f7f7f;
 18 const double PI=3.14159265358979323;
 19 const int N=304;
 20 using namespace std;
 21 typedef long long LL;
 22 double anss;
 23 LL aans;
 24 int cas,cass;
 25 int n,m,lll,ans;
 26 int t[N][N],a[N][N],b[N][N],d[N][N],in[N][N];
 27 int nex[N][N][2][2];
 28 void tuopu()
 29 {
 30     int i,j,x,y,xx,yy;
 31     mem(d,0);
 32     queue<int>qx,qy;
 33     for(i=1;i<=n;i++)
 34     {
 35         if(!in[i][a[i][1]])
 36         {
 37             d[i][a[i][1]]=t[i][a[i][1]];
 38             qx.push(i);
 39             qy.push(a[i][1]);
 40         }
 41     }
 42     while(!qx.empty())
 43     {
 44         x=qx.front();qx.pop();
 45         y=qy.front();qy.pop();
 46         for(i=0;i<2;i++)
 47         {
 48             xx=nex[x][y][i][0];
 49             yy=nex[x][y][i][1];
 50             if(!x || !y)continue;
 51             d[xx][yy]=max(d[xx][yy],d[x][y]+t[xx][yy]);
 52             if(!--in[xx][yy])
 53             {
 54                 qx.push(xx);
 55                 qy.push(yy);
 56             }
 57         }
 58         ans=max(ans,d[x][y]);
 59     }
 60 }
 61 int main()
 62 {
 63     #ifndef ONLINE_JUDGE
 64     freopen("1.txt","r",stdin);
 65 //    freopen("2.txt","w",stdout);
 66     #endif
 67     int i,j,k,l;
 68     int x,y,z;
 69 //    for(scanf("%d",&cass);cass;cass--)
 70 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
 71 //    while(~scanf("%s",s))
 72     while(~scanf("%d",&n))
 73     {
 74         ans=0;
 75         mem(nex,0);mem(in,0);
 76         scanf("%d",&m);
 77         for(i=1;i<=n;i++)
 78             for(j=1;j<=m;j++)
 79                 scanf("%d",&t[i][j]);
 80         for(i=1;i<=n;i++)
 81             for(j=1;j<=m;j++)
 82                 scanf("%d",&a[i][j]);
 83         for(i=1;i<=m;i++)
 84             for(j=1;j<=n;j++)
 85                 scanf("%d",&b[i][j]);
 86         for(i=1;i<=n;i++)
 87         {
 88             for(j=1;j<m;j++)
 89             {
 90                 nex[i][a[i][j]][0][0]=i,
 91                 nex[i][a[i][j]][0][1]=a[i][j+1];
 92                 in[i][a[i][j+1]]++;
 93             }
 94         }
 95         for(i=1;i<=m;i++)
 96         {
 97             for(j=1;j<n;j++)
 98             {
 99                 nex[b[i][j]][i][1][0]=b[i][j+1],
100                 nex[b[i][j]][i][1][1]=i;
101                 in[b[i][j+1]][i]++;
102             }
103         }
104         tuopu();
105         printf("%d
",ans);
106     }
107     return 0;
108 }
109 /*
110 //
111 
112 //
113 */

View Code