poj 3189 Steady Cow Assignment(二分+最大流)

题意：N头牛(1000)，B个农场(20)，每个农场可以容纳一定数量的牛。

每头牛对每个农场都有一个排名(排名从1~B)。每头牛都会在B个农场中的某一个，这头牛的高兴程度是它对这个农场的排名。为了使每头牛都尽量同等高兴，希望所有牛中最高兴的和最不高兴的程度差值最小，求这个差值。

构图：二分最小差，对每一个最小差，枚举起点、终点。最大流判可行性。

#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std;const int maxn = 1500; const int INF = 0x3f3f3f3f; struct Edge {int to,next,flow; }edge[maxn*150]; int n,m,Rank[maxn][25]; int cnt,head[maxn],num[maxn]; int level[maxn],st,ed;void addedge(int u,int v,int flow) {edge[cnt].to = v;edge[cnt].flow = flow;edge[cnt].next = head[u];head[u] = cnt++;swap(u,v);edge[cnt].to = v;edge[cnt].flow = 0;edge[cnt].next = head[u];head[u] = cnt++; }void build(int l,int r) //rank[l]~rank[r]之间 {cnt = 0;memset(head,-1,sizeof(head));for(int i = 1; i <= n; i++) addedge(st,i,1);for(int i = 1; i <= n; i++)for(int j = l; j <= r; j++)addedge(i,n + Rank[i][j],1);for(int i = n + 1; i <= n + m; i++) addedge(i,ed,num[i-n]); }int BFS(int src,int des){queue<int >q;memset(level,0,sizeof(level));level[src]=1;q.push(src);while(!q.empty()){int u = q.front();q.pop();if(u==des) return 1;for(int k = head[u];k!=-1;k=edge[k].next){int v = edge[k].to,w=edge[k].flow;if(level[v]==0&&w!=0){level[v]=level[u]+1;q.push(v);}}}return -1; }int dfs(int u,int des,int increaseRoad){if(u==des) return increaseRoad;int ret=0;for(int k=head[u];k!=-1;k=edge[k].next){int v = edge[k].to,w=edge[k].flow;if(level[v]==level[u]+1&&w!=0){int MIN = min(increaseRoad-ret,w);w = dfs(v,des,MIN);if(w > 0){edge[k].flow -= w;edge[k^1].flow += w;ret+=w;if(ret==increaseRoad) return ret;}else level[v] = -1; }}return ret; } int Dinic(int src,int des){int ans = 0;while(BFS(src,des)!=-1) ans+=dfs(src,des,INF);return ans; }bool check(int len) {for(int i = 1; i + len - 1 <= m; i++){build(i,i+len-1);int tmp = Dinic(st,ed);if(tmp == n) return true;}return false; }int main() {while(scanf("%d%d",&n,&m)!=EOF){st = 0, ed = n + m + 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",&num[i]);int l = 1,r = m,mid,ans;while(l <= r){mid = (l + r) >> 1;if(check(mid)){ans = mid;r = mid - 1;}else l = mid + 1;}printf("%d\n",ans);}return 0; }

总结

以上是生活随笔为你收集整理的poj 3189 Steady Cow Assignment(二分+最大流)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。