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