7-找了一上午的BUG

#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 1<<28;
using namespace std;
#define MAX 1<<28;
int lx[50], ly[50];
int map[50][50];
int visitx[50], visity[50];
int match[50], slack[50];
int n, m;

int hungary(int u){
   visitx[u] = 1;
   int temp = 0;
   for(int i = 1; i <= m; i++){
       if(visity[i])
           continue;
       temp = lx[u] + ly[i] - map[u][i];
       if(temp == 0){
           visity[i] = 1;
           if(match[i] == 0 || hungary(match[i])){
               match[i] = u;
               return 1;
           }
       }
       else
           slack[i] = min(slack[i], temp);
   }
   return 0;
}

int km(){
   int temp = 0;
   memset(lx, 0, sizeof(lx));
   memset(ly, 0, sizeof(ly));
   for(int i = 1; i <= n; i++)
       for(int j = 1; j <= m; j++)
           if(lx[i] < map[i][j])
               lx[i] = map[i][j];
   for(int i = 1; i <= n; i++){
       for(int j = 1; j <= m; j++)
           slack[j] = MAX;
       while(1){
           memset(visitx, 0, sizeof(visitx));
           memset(visity, 0, sizeof(visity));
           if(hungary(i))
               break;
           else{

           temp = MAX;
           for(int j = 1; j <= m; j++)
               if(!visity[j])
                      if(temp > slack[j])
                          temp = slack[j];

           if(temp == MAX)
               return 0;     // 无法匹配
           for(int j = 1; j <= n; j++)
               if(visitx[j])
                   lx[j] -= temp;
           for(int j = 1; j <= m; j++)
               if(visity[j])
                   ly[j] += temp;
               else
                   slack[j] -= temp;
           }
       }
   }
   return 1;
}

int main(){
   int rewu;
   while(cin >> n){
       cin >> m;
       int res = 0, ans = 0;
       memset(map, 0, sizeof(map));
       memset(match, 0, sizeof(match));
       for(int i = 1; i <= n; i++){
           for(int j = 1; j <= m; j++){
               cin >> map[i][j];
               map[i][j] *= (n+1);
           }
       }
       for(int i = 1; i <= n; i++){
           cin >> rewu;
           res += map[i][rewu];
           map[i][rewu]++;
       }
       km();
       for(int i = 1; i <= m; i++)
           if(match[i] != 0){
               cout << "match[i]: " << match[i] << endl;
               cout << i << "i: " << map[match[i]][i] << " ";
               ans += map[match[i]][i];
           }
       cout << n - res % (n+1) << " " << ans/(n+1) - res/(n+1) << endl;
       cout << res << " " << ans << endl;
   }
   return 0;
}

找BUG：

巴特西

7-找了一上午的BUG

最新文章

热门文章