uva 259 - Software Allocation

Software Allocation

A computing center has ten different computers (numbered 0 to 9) on which applications can run. The computers are not multi-tasking, so each machine can run only one application at any time. There are 26 applications, named A to Z. Whether an application can run on a particular computer can be found in a job description (see below).

Every morning, the users bring in their applications for that day. It is possible that two users bring in the same application; in that case two different, independent computers will be allocated for that application.

A clerk collects the applications, and for each different application he makes a list of computers on which the application could run. Then, he assigns each application to a computer. Remember: the computers are not multi-tasking, so each computer must handle at most one application in total. (An application takes a day to complete, so that sequencing i.e. one application after another on the same machine is not possible.)
A job description consists of

1. one upper case letter A...Z, indicating the application.
2. one digit 1...9, indicating the number of users who brought in the application.
3. a blank (space character.)
4. one or more different digits 0...9, indicating the computers on which the application can run.
5. a terminating semicolon `;'.
6. an end-of-line.

Input

The input for your program is a textfile. For each day it contains one or more job descriptions, separated by a line containing only the end-of-line marker. The input file ends with the standard end-of-file marker. For each day your program determines whether an allocation of applications to computers can be done, and if so, generates a possible allocation.

Output

The output is also a textfile. For each day it consists of one of the following:

• ten characters from the set {`A'...`Z' , `_'}, indicating the applications allocated to computers 0 to 9 respectively if an allocation was possible. An underscore `_' means that no application is allocated to the corresponding computer.
• a single character `!', if no allocation was possible.

Sample Input

A4 01234;
Q1 5;
P4 56789;

A4 01234;
Q1 5;
P5 56789;

Sample Output

AAAA_QPPPP
!


Maximum Network Flow 
#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i,n) REP(i, 0, n)
#define DBG 0
using namespace std;

int N,TSN;
vector<int>egs[50];
int wgt[50][50],p[50],pf[50],gap[50],h[50],PI[50];
int isap(int s,int t){
    int i,b,c=s,f=int(1e9),res=0;
    memset(gap,0,sizeof(gap));
    memset(h,0,sizeof(h));
    memset(p,0,sizeof(p));
    pf[s]=int(1e9), p[s]=s;
    if(DBG)printf("N %d\n",N);
    while(1){
        if(DBG)printf("isap %d f %d h %d\n",c,f,h[c]);
        b=-1;
        rep(i,egs[c].size()){
            int d=egs[c][i];
            //if(DBG)printf("wgt[%d][%d]=%d\n",c,b,wgt[c][b]);
            if(wgt[c][d]>0&&h[c]==h[d]+1){b=egs[c][i];break;}
        }
        if(b==t){
            f=min(f,wgt[c][b]);
            res+=f;
            if(DBG)printf("t: computer %d res %d\n",c-27,res);
            for(;b!=s;PI[b]=c,b=c,c=p[c]){
                wgt[c][b]-=f,wgt[b][c]+=f;
                if(DBG)printf("f %d wgt[%d][%d]=%d\n",f,c,b,wgt[c][b]);
            }
            c=s,f=int(1e9);
        }
        else if(b>=0){
            if(DBG)printf("move to %d, ",b);
            pf[b]=f;
            f=min(f,wgt[c][b]);
            if(DBG)printf("f %d\n",f);
            p[b]=c;
            c=b;
        }
        else{
            if(DBG)printf("raise %d: %d\n",c, h[c]+1);
            if(--gap[h[c]]==0)break;
            ++gap[++h[c]];
            f=pf[c];
            c=p[c];
        }
    }
    return res;
}
void ans(){
    memset(PI,0,sizeof(PI));
   int res=isap(0,49);
   if(res==TSN){rep(i,10)if(PI[i+27])printf("%c",PI[i+27]+'@');else printf("_");printf("\n");}
   else printf("!\n");
}
int main(){
    int cn,tn;
    char chs[100];
    N=12;
    while(fgets(chs,100,stdin)){
        if(chs[0]=='\n'){
            ans();
            TSN=0,N=12,memset(wgt,0,sizeof(wgt));rep(i,50)egs[i].clear();
            scanf(" ");
            continue;
        }
        N++;
        if(chs[strlen(chs)-1]=='\n')chs[strlen(chs)-1]='\0';
        tn=chs[0]-'@';
        egs[0].push_back(tn);
        wgt[0][tn]=chs[1]-'0';
        TSN+=wgt[0][tn];                //all tasks
        if(DBG)printf("task %d\n",tn);
        rep(i,10)egs[i+27].push_back(49);
        REP(i,3,strlen(chs)-1){
            cn=chs[i]-'0'+27;
            if(DBG)printf("  com %d\n",cn);
            egs[tn].push_back(cn),egs[cn].push_back(tn);
            wgt[tn][cn]=1,wgt[cn][49]=1;
        }
    }
    if(egs[0].size())ans();
}