竹園論壇

標題: 259 - Software Allocation [打印本頁]

作者: jd3 時間: 2014-5-3 22:38
標題: 259 - Software Allocation
本帖最後由 jd3 於 2014-5-4 16:30 編輯

題目：有一些程式類型為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好像沒用到)

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

歡迎光臨竹園論壇 (http://forum.tfcis.org/)