259 - Software Allocation

jd3

題目：有一些程式類型為A~Z，要再編號0~9的電腦上執行
.          每種程式只能在特定幾台電腦上執行，請試著找出使所有程式能同時執行的安排
.          同一台電腦無法同時執行多個程式


注意事項：
           1.測資間有空行，最後一筆測資後接的是EOF
           2.不要遺漏驚嘆號


解法：各種二分圖匹配



AC　Code :
/*
        AC
        472~475 ms
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;


vector<int> x[500],y[500];
int xp[500], yp[500];
int xcount, ycount;
int xtype[500];


int xvist[500], yvist[500];


bool dfs(int node, int step)
{
        bool found = false;
        if(step&1)        //Y side (com numbers)
        {
                yvist[node] = true;
                if(yp[node] == -1)
                        found = true;
                else
                        found = dfs(yp[node], step+1);
                yvist[node] = false;
        }
        else                //X side
        {
                xvist[node] = true;
                for(int i = 0 ; i < x[node].size() ; i++)
                {
                        int next = x[node][i];
                        if((!yvist[next]) && xp[node] != next)
                                if(dfs(next, step+1))
                                {
                                        found = true;
                                        xp[node] = next;
                                        yp[next] = node;
                                        break;
                                }
                }
                xvist[node] = false;
        }
        
        return found;
}



int main()
{
        char str[500];
        bool going = true;
         
        while(going)
        {
                //init
                xcount = 0;
                ycount = 0;
                for(int i = 0 ; i < 10 ; i++)
                        y[i].clear();
                for(int i = 0 ; i < 300 ; i++)
                        x[i].clear();
                memset(xp,-1,sizeof(xp));
                memset(yp,-1,sizeof(yp));
                memset(xvist,0,sizeof(xvist));
                memset(yvist,0,sizeof(yvist));
               
                //inputs
                while(1)
                {
                        if(!fgets(str,200,stdin))
                        {
                                going = false;
                                break;
                        }
                        if(str[0] == '\n')
                                break;
                        
                        
                        int a = str[0];
                        for(int i = 0 ; i < str[1]-'0' ; i++)
                        {
                                for(int i = 3 ; str[i] != ';' ; i++)
                                {
                                        xtype[xcount] = a;
                                        x[xcount].push_back(str[i]-'0');
                                        y[str[i]-'0'].push_back(xcount);
                                }
                                xcount++;
                        }
                }
               
               
               
                //process
                bool update = true;
                while(update)
                {
                        update = false;
                        for(int i = 0 ; i < xcount ; i++)
                                if(xp[i]==(-1) && dfs(i,0))
                                        update = true;
                }
               
               
                //ans
                bool solved = true;
                for(int i = 0 ; i < xcount ; i++)
                        if(xp[i] == -1)
                        {
                                puts("!");
                                solved = false;
                                break;
                        }
                if(!solved)
                        continue;
                for(int i = 0 ; i < 10 ; i++)
                        if(yp[i] != -1)
                                putchar(xtype[yp[i]]);
                        else
                                putchar('_');
               
                putchar('\n');
               
        }
        
        return 0;
}
程式說明：x,y儲存可連接的對面的結點編號 (自0)
xp存目前匹配對象
xtype記錄x邊的結點是哪種程式(大寫英文字母)
dfs尋找增廣路徑，此以使x邊全部匹配為目標
(我的yvist好像沒用到)

備註：可以先判斷程式數量是否超過電腦數量