S5來襲4/11旗艦上市三星平板★瘋殺5290起攝影界美人正妹指定相機款老伯送飲料 遭學生糾察...
2012-09-29 10:58:28 人氣(488) | 回應(3) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][匈牙利二分匹配] 11138 - Nuts and Bolts

0
收藏
0
推薦

Problem J

Nuts 'n' Bolts

One afternoon your cell phone rings; it's your cousin Jimmy.
"Hi Cuz," he says, "I need your help and I need it fast. I'm in the middle of a programming contest and however hard I try, I can't get one problem to finish within the two second time limit."
"Hmm... well..., isn't that a bit illegal?", you try to say to him. But he rattles on.
"I just snook out of the contest room and managed to send you my code and the sample I/O by email", he continues without pausing. "I will check my mail again in an hour, so please make it work for me."
"What about the problem description?", you ask.
"Can't do", he says, "Zoroman the Head Judge is already on my tail, so I got to go. Bye, ... and, eh, thanks."

Are you going to help him?

Jimmy's Code

#include <stdio.h>
 
#define MAX_BOLTS 500
#define MAX_NUTS  500
 
/* global copy of the input data */
int nuts,bolts;
int fits[MAX_BOLTS][MAX_NUTS];

void read_input_data(void){

   int n,b;
   
   scanf("%d%d",&bolts,&nuts);
   for(b=0;b<bolts;b++){
      for(n=0;n<nuts;n++){
         scanf("%d",&fits[b][n]);
         }
      }
   }

/* data used to match nuts with bolts */

int nut_used[MAX_NUTS];
int bestmatched;

void init_match(void){

   int n;
   
   bestmatched=0;
   for(n=0;n<nuts;n++) nut_used[n]=0;
   }
   
void match_bolt(int boltno, int matched){
   int n;
   
   if(boltno==bolts){
      if(matched>bestmatched) bestmatched=matched;
      return;
      }
      
   /* don't match this bolt */
   match_bolt(boltno+1,matched);
   
   /* match with all unused nuts that fit this bolt */
   for(n=0;n<nuts;n++) if(!nut_used[n] && fits[boltno][n]){
      nut_used[n]=1;
      match_bolt(boltno+1,matched+1);
      nut_used[n]=0;
      }
   }
   
int main(){
   int cases,caseno;
   
   scanf("%d",&cases);
   for(caseno=1;caseno<=cases;caseno++){
      read_input_data();
      init_match();
      match_bolt(0,0);
      printf("Case %d: ",caseno);
      printf("a maximum of %d nuts and bolts ",bestmatched);
      printf("can be fitted together\n");
      }
      
   return 0;
   }


This is the code that Jimmy sent you by email.
A plain-text version can be found here.

Sample Input

2
3 4
0 0 1 0
1 1 0 1
0 0 1 0
5 5
1 0 0 1 1
1 1 0 0 0
1 0 0 0 0
0 1 1 0 0
0 0 0 0 1 

Sample Output

Case 1: a maximum of 2 nuts and bolts can be fitted together
Case 2: a maximum of 5 nuts and bolts can be fitted together


#include <stdio.h>
#include <string.h>
int g[1005][1005], gt[1005];
int mx[1005], my[1005], used[1005];
int dfs(int now) {
    int i, x;
    for(i = 0; i < gt[now]; i++) {
        x = g[now][i];
        if(!used[x]) {
            used[x] = 1;
            if(my[x] == 0 || dfs(my[x])) {
                mx[now] = x, my[x] = now;
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    int n, m, i, j, x;
    int t, cases = 0;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        memset(gt, 0, sizeof(gt));
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= m; j++) {
                scanf("%d", &x);
                if(x)
                    g[i][gt[i]++] = j+n;
            }
        }
        memset(mx, 0, sizeof(mx));
        memset(my, 0, sizeof(my));
        int ans = 0;
        for(i = 1; i <= n; i++) {
            if(!mx[i]) {
                memset(used, 0, sizeof(used));
                if(dfs(i))
                    ans++;
            }
        }
        printf("Case %d: a maximum of %d nuts and bolts can be fitted together\n", ++cases, ans);
    }
    return 0;
}

11138Nuts and Bolts匈牙利
台長:Morris
人氣(488) | 回應(3)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][幾何、交集] 11639 - Guard the Land
此分類上一篇:[UVA] 10050 - Hartals

iLevis
Hi you, i have a question.
What name of algorithm you use in your code ?
2013-05-05 07:43:22
版主回應
2013-05-05 08:06:24
iLevis
Thanks.
hm!
i don't understand it.
i have a graph.

1 connected 4
1 connected 5
2 connected 4

and i run flow you, but it not work.
Output is 1 -> 4

So output
1 --> 5
2 --> 4
expansion for me please
2013-05-05 08:37:57
版主回應
first loop for main() call dfs(1)
we match 1->4, so mx[1] = 4, my[4] = 1
back main()

second loop for main() call dfs(2)
we try find alternating path: if(... || dfs(my[4]))
2->4->1->5 (path)
2->4 not matched pair, 1->4 matched pair, 1->5 not matched pair.
=> 2->4, 1->5 matched
After try, we add 1 matched pair.

in my code, I used node label x.size()+y.label,
In fact, using y.label still solved.

my write ability is not good in English.
2013-05-05 09:20:52
iLevis
Ok thanks very much. i am understand!
good luck to you
xD
2013-05-05 09:52:31
我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文