|
Posted on 2010-10-07 18:57 成幸毅 阅读(361) 评论(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;
}


|