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
!

---

題目描述：
現在只有 10 台電腦, 而每個軟件都有其限定的電腦上才可以執行, 而在同一時間有一些人要用這些軟件, 問能不能符合需求, 有符合的解輸出其中一組即可。

題目解法：

很明顯地是一題匹配問題, source - 軟件 - 電腦 - sink

這樣拉最大流的模型即可。以點的個數有點大材小用就是了。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
struct Node {
    int x, y, v;// x->y, v
    int next;
} edge[30005];
int e, head[105], dis[105], prev[105], record[105];
void addEdge(int x, int y, int v) {
    edge[e].x = x, edge[e].y = y, edge[e].v = v;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].v = 0;
    edge[e].next = head[y], head[y] = e++;
}
int maxflow(int s, int t) {
    int flow = 0;
    int i, j, x, y;
    while(1) {
        memset(dis, 0, sizeof(dis));
        dis[s] =  0xffff; // oo
        queue<int> Q;
        Q.push(s);
        while(!Q.empty()) {
            x = Q.front();
            Q.pop();
            for(i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                if(dis[y] == 0 && edge[i].v > 0) {
                    prev[y] = x, record[y] = i;
                    dis[y] = min(dis[x], edge[i].v);
                    Q.push(y);
                }
            }
            if(dis[t])  break;
        }
        if(dis[t] == 0) break;
        flow += dis[t];
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            edge[ri].v -= dis[t];
            edge[ri^1].v += dis[t];
        }
    }
    return flow;
}
int parseInput(char s[]) {
    int x = s[0]-'A'+1, m, y;
    int i = 0;
    sscanf(s+1, "%d", &m);
    while(s[i] != ' ')  i++;
    while(s[i] != ';') {
        if(s[i] >= '0' & s[i] <= '9')
            y = s[i]-'0', addEdge(x, y+27, 1);
        i++;
    }
    addEdge(0, x, m);
    return m;
}
int main() {
    char cmd[105];
    int i, j;
    while(gets(cmd)) {
        e = 0;
        memset(head, -1, sizeof(head));
        // source 0, 'A'-'Z' 1-26, computer0-9 27-36, sink 37
        for(i = 0; i < 10; i++)
            addEdge(i+27, 37, 1);
        int totflow = 0;
        totflow += parseInput(cmd);
        while(gets(cmd)) {
            if(cmd[0] == '\0')  break;
            totflow += parseInput(cmd);
        }
        int mxflow = maxflow(0, 37);
        if(mxflow != totflow)
            puts("!");
        else {
            int ret[10] = {};
            for(i = 1; i <= 26; i++) {
                for(j = head[i]; j != -1; j = edge[j].next) {
                    if(edge[j].v == 0) {
                        ret[edge[j].y-27] = i;
                    }
                }
            }
            for(i = 0; i < 10; i++) {
                if(ret[i] == 0)
                    printf("_");
                else
                    printf("%c", ret[i]-1+'A');
            }
            puts("");
        }
    }
    return 0;
}