首页 > ACM题库 > HDU-杭电 > HDU 3230-Assembling Services[解题报告]HOJ
2014
03-09

HDU 3230-Assembling Services[解题报告]HOJ

Assembling Services

问题描述 :

In this problem, you need to simulate the execution of n service programs P1, P2, …, Pn. Each program is described with sequence of integers: T I in1 in2 … inI O out1 out2 … outO, that means it takes T unit time to execute, needs I input variables (i.e. in1 in2 … inI), and sets O output variables (i.e. out1 out2 … outO) when it finishes running. A program can be started if and only if all these T input variables are ready (initially available, or set by some other programs).

Imagine you have a super-computer which can execute as many programs in parallel as you like, and every variable can be read and written simultaneously by multiple programs. Your task is to calculate a particular "target" variable, as soon as possible.

Assume there are 4 programs, shown in the table below:

Jinyuetuan Puzzle

The quickest time to get X5 is 7, if only X1 is available at startup.

You also need to construct an expression that shows how to execute the programs to achieve the minimal time. The grammar of the expression is recursive:

  • Single Program: Px, where 1 <= x <= n. (i.e. P2, P499, etc). Meaning: execute the program immediately. Then end of this program marks the end of this expression.
  • Execute in serial: (S1S2…Sk), where every Si is an expression. Note that the outermost pair of parentheses is mandatory. Meaning: execute expression S1, then S2 immediately after S1 ends, then S3 immediately after S2 ends, …, and finally Sk immediately after Sk-1 ends. Then end of expression Sk marks the end of the whole expression.
  • Execute in parallel: (S1|S2|…|Sk), where every Si is an expression. Note that the outermost pair of parentheses is mandatory. Meaning: execute expressions S1, S2, …, and Sk simultaneously. The end of last finished expression marks the end of the whole expression.

One of the possible expressions for the example above is (((P1P3)|P2)P4). (P1P2P3P4)is not acceptable, since X5 is available at time 10 in that expression, later than the optimal time 7.

输入:

There will be at most 100 test cases. Each case begins with three integers n, m, o(1 <= n,m <= 500, 1 <= o <= m). The number of programs is n, the number of variables is m, and the target variable is Xo. Variables are numbered 1 to m, programs are numbered 1 to n. The next line contains a 01 string of m characters. The i-th character is 1 if and only if the i-th variable is initially available. The target variable is guaranteed to be unavailable at startup. The following n lines describe the programs. Each line begins with an integer T(1 <= T <= 100), the execution time, and an integer I followed by I integers in1, in2, …, inI, as stated above, then an integer O followed by O integers out1, out2, …, outO. 1 <= ini,outi <= m, 1 <= I,O <= 10. The last test case is followed by n=m=o=0, which should not be processed.

输出:

There will be at most 100 test cases. Each case begins with three integers n, m, o(1 <= n,m <= 500, 1 <= o <= m). The number of programs is n, the number of variables is m, and the target variable is Xo. Variables are numbered 1 to m, programs are numbered 1 to n. The next line contains a 01 string of m characters. The i-th character is 1 if and only if the i-th variable is initially available. The target variable is guaranteed to be unavailable at startup. The following n lines describe the programs. Each line begins with an integer T(1 <= T <= 100), the execution time, and an integer I followed by I integers in1, in2, …, inI, as stated above, then an integer O followed by O integers out1, out2, …, outO. 1 <= ini,outi <= m, 1 <= I,O <= 10. The last test case is followed by n=m=o=0, which should not be processed.

样例输入:

4 5 5
10000
2 1 1 1 2
3 1 1 1 3
4 1 2 1 4
1 2 3 4 1 5
1 2 1
01
31 1 2 1 1
3 5 5
10100
3 1 1 1 2
1 1 3 1 4
3 2 4 2 1 5
1 3 3
100
1 1 1 1 2
0 0 0

样例输出:

Case 1: 7 (((P1P3)|P2)P4)

Case 2: 31 P1

Case 3: 6 ((P1P3)|P2)

Case 4: -1

Hint
Explanation After a variable is set, it'll keep available forever. That's why P3 can be executed, in the third example. Also note that there are some other correct expressions for the first sample, e.g.((P1P3P4)|P2). You can even print (((P1P3)P4)|P2) or ((P1(P3P4))|P2). Any one of them is acceptable in this problem.

//#pragma comment(linker,"/STACK:65536000")
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<string>
#include<list>
#include<set>
#include<map>
#include<queue>
#include <math.h>
#define clr(x,y) memset(x,y,sizeof(x))
#define forn(i,n) for(int i=0;i<n;i++)
#define ll long long
#define mpr(x,y) make_pair(x,y)
#define pii pair<int,int>
#define MID ((l+r)>>1)
#define lson rt<<1,l,MID
#define rson rt<<1|1,MID+1,r
#define D(a) ((a)>0?(a):-(a))
#define sqr(a) ((a)*(a))
#define lowb(i) ((i)&(-i))
using namespace std;
const int inf=1<<30;

int n,m,o;
char a[10000];
int T[1000];
vector <int> in[1000],out[1000];
int num[1000];
int first[1000],next[1000],v[1000],ed;
void addedge(int u,int v){
    ::v[ed]=v;
    next[ed]=first[u];
    first[u]=ed++;
}
struct my{
    int x,d,s;
    my(int x=0,int d=0,int s=0):x(x),d(d),s(s){}
    bool operator <(const my &u)const{
        return s>u.s;
    }
};
int ti=1;

string dfs(int u){
    string ans="(";
    if(u!=0){
        char b[10]="P";
        sprintf(b+1,"%d",u);
        ans+=b;
    }
    if(first[u]!=-1){
        ans+="(";
        int f=1;
        for(int i=first[u];~i;i=next[i]){
            if(f)f=0;
            else ans+="|";
            ans+=dfs(v[i]);
        }
        ans+=")";
    }
    ans+=")";
    if(ans.length()>10000)while(1);
    return ans;
}
void gao(){
    priority_queue <my> que;
    bool vis[1000]={0};
    int dis[1000];
    for(int i=1;i<=n;i++)dis[i]=inf;
    dis[0]=0;
    for(int i=1;i<=n;i++){
        int flag=1;
        for(int j=0;j<(int)in[i].size();j++)if(a[in[i][j]]=='0'){
            flag=0;break;
        }
        if(flag){
            vis[i]=1;
            addedge(0,i);
            dis[i]=min(dis[i],T[i]);
            que.push(my(i,T[i],dis[i]));
        }
    }
    int ans=-1;
    while(!que.empty()){
        my now=que.top();que.pop();
        int x=now.x;
        for(int i=0;i<(int)out[x].size();i++){
            if(a[out[x][i]]!='1'){
                a[out[x][i]]='1';
                num[out[x][i]]=x;
            }
        }
        if(a[o]=='1'){
            ans=dis[x];
            break;
        }
        for(int i=1;i<=n;i++)if(!vis[i]){
            int flag=1;
            for(int j=0;j<(int)in[i].size();j++)if(a[in[i][j]]=='0'){
                flag=0;break;
            }
            if(flag){
                vis[i]=1;
                int p=0;
//                addedge(x,i);
                int ret=0;
                for(int j=0;j<(int)in[i].size();j++)if(dis[num[in[i][j]]]>ret)ret=dis[num[in[i][j]]],p=num[in[i][j]];
                addedge(p,i);
                dis[i]=min(dis[i],ret+T[i]);
                que.push(my(i,T[i],dis[i]));
            }
        }
    }
//    for(int i=0;i<=n;i++){
//        printf("%d : ",i);
//        for(int j=first[i];~j;j=next[j])printf("%d ",v[j]);
//        puts("");
//    }
    if(ans!=-1){
        printf("Case %d: %d ",ti++,ans);
        cout<<dfs(0)<<endl;

    }
    else printf("Case %d: %d\n",ti++,ans);
    puts("");
}
int main(){
//    freopen("/home/axorb/in","r",stdin);
    while(scanf("%d%d%d",&n,&m,&o),n+m+o){
        scanf("%s",a+1);
        ed=0;
        clr(first,-1);
        clr(num,0);
        for(int i=1;i<=m;i++)if(a[i]=='1')num[i]=0;
        for(int i=1;i<=n;i++){
            scanf("%d",T+i);
            in[i].clear();
            out[i].clear();
            int p;
            scanf("%d",&p);
            for(int j=0;j<p;j++){
                int q;
                scanf("%d",&q);
                in[i].push_back(q);
            }
            scanf("%d",&p);
            for(int j=0;j<p;j++){
                int q;
                scanf("%d",&q);
                out[i].push_back(q);
            }
        }
        gao();
    }
}

  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。