POJ 3189 Steady Cow Assignment

POJ_3189

? ? 一開始題意各種理解錯，首先輸入的那個矩陣第i行第j列的值表示的是奶牛i會第j個中意的牛棚，最后求的range就相當于j的range，至于range是變化的范圍，比如j在1、2變化，那么range就應該是2，也就是MAX-MIN+1。

? ? 因此我們可以枚舉range的下界和上屆，然后用二分圖多重匹配判斷是否有解，當然用網絡流判斷也可以，不過好像比較慢。在枚舉range的時候可以做到O(N)，比如現在range是[x,y]，如果當前無解那么就擴大上屆令y=y+1，如果有解就縮小下屆令x=x+1。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 1010
#define MAXB 30
#define INF 0x3f3f3f3f
int N, B, yM[MAXB][MAXN], visy[MAXB], num[MAXB], limit[MAXB];
int g[MAXN][MAXB], LOW, HIGH;
void init()
{int i, j, k;for(i = 0; i < N; i ++)for(j = 0; j < B; j ++)scanf("%d", &g[i][j]), -- g[i][j];for(i = 0; i < B; i ++) scanf("%d", &limit[i]);
}
int searchpath(int cur)
{int i, y, j;for(i = LOW; i <= HIGH; i ++)if(!visy[g[cur][i]]){y = g[cur][i], visy[y] = 1;if(num[y] < limit[y]){yM[y][num[y] ++] = cur;    return 1;}for(j = 0; j < num[y]; j ++)if(searchpath(yM[y][j])){yM[y][j] = cur;return 1;    }}return 0;
}
int match()
{int i;memset(num, 0, sizeof(num[0]) * B);for(i = 0; i < N; i ++){memset(visy, 0, sizeof(visy[0]) * B);if(!searchpath(i)) return 0;}return 1;
}
void solve()
{int ans = INF;LOW = HIGH = 0;while(HIGH < B){if(!match())++ HIGH;elseans = std::min(ans, HIGH - LOW + 1), ++ LOW;}printf("%d\n", ans);
}
int main()
{while(scanf("%d%d", &N, &B) == 2){init();solve();    }return 0;    
}