|
|
Posted on 2010-10-07 18:57 成幸毅 阅读(334) 评论(0) 编辑 收藏 引用
此题可以要求的是在满足每头牛能找到窝的情况下（也就最大流能满足等于n的时候），使得每头牛的对窝的排名中最大减去最小的值最小，听上去很拗口，但是明白了意思了就跟很多题都差不多的。就那么回事，这里采用二分枚举，但是每次删边的时候用两个参数，最大和最小的rank值，尽量让他们靠近，靠得越近就越小。条件就是最大流 == n；
 #include <iostream>
using namespace std;
const int INF = 0x7fffffff;
const int MAXN = 1100;
int n,m;
int rank[MAXN][MAXN],ran,cap[MAXN],sps,s,t,head[MAXN],
e[MAXN],NN;
  struct node  {
 int w,u,v,next;
 }edge[50010];
void addedge(int u,int v,int val) {
edge[sps].v = v;
edge[sps].w = val;
edge[sps].next = head[u];
head[u] = sps++;
edge[sps].v = u;
edge[sps].w = 0;
edge[sps].next = head[v];
head[v] = sps++;
}
int sap()
{
memset(e,0,sizeof(e));
int pre[MAXN],d[MAXN],gap[MAXN];
int u,delta = INF,flow = 0;
bool flag;
for(int i = 0; i <= NN; i++)
d[i] = gap[i] = 0;
u = pre[s] = s;
gap[s] = NN;
  while(d[s] < NN) {
flag = false;
for(int addr = head[u]; addr != -1; addr = edge[addr].next) {
int v = edge[addr].v;
if(edge[addr].w > 0 && d[u] == d[v] + 1) {
flag = true;
if(edge[addr].w < delta) delta = edge[addr].w;
e[u] = addr;
pre[v] = u;
u = v;
if(u == t) {
flow += delta;
while(u != s) {
u = pre[u];
edge[e[u]].w -= delta;
edge[e[u]^1].w += delta;
 }
delta = INF;
}
break;
}
}
if(flag == true) continue;
int mm = NN;
for(int addr = head[u]; addr != -1; addr = edge[addr].next) {
int v = edge[addr].v;
if(edge[addr].w > 0 && d[v] < mm) {
mm = d[v];
e[u] = addr;
}
}
if((--gap[d[u]]) == 0) break;
gap[d[u] = (mm + 1)]++;
u = pre[u];
}
return flow;
}
void build_graph(int l,int r) {
memset(head,-1,sizeof(head));
sps = 0;
for(int i = 1; i <= n; i++) {
for(int j = l; j <= r; j++) {
addedge(i,n+rank[i][j],INF);
}
}
for(int i = 1; i <= n;i++) {
addedge(s,i,1);
}
for(int i = 1; i <= m; i++) {
addedge(i+n,t,cap[i]);
}
}
void search() {
int l = 1,r = 1;
int mid;
int ans = m;
build_graph(l,r);
while(l <= r && r <= m) {
mid = sap();
if(mid == n) {
if(r - l + 1 < ans) ans = r - l + 1;
l++;
}
else
r++;
build_graph(l,r);
}
printf("%d\n",ans);
}
int main() {
while(scanf("%d%d",&n,&m) != EOF) {
s = 0,t = n + m + 1;
NN = t + 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m;j++) {
scanf("%d",&rank[i][j]);
}
for(int i = 1; i <= m; i++) {
scanf("%d",&cap[i]);
}
search();
}
// system("pause");
return 0;
}
|