hdu 3189(网络流+二分枚举)
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 6422 | Accepted: 2202 |
Description
FJ would like to rearrange the cows such that the cows are as
equally happy as possible, even if that means all the cows hate their
assigned barn.
Each cow gives FJ the order in which she prefers the barns. A cow's
happiness with a particular assignment is her ranking of her barn. Your
job is to find an assignment of cows to barns such that no barn's
capacity is exceeded and the size of the range (i.e., one more than the
positive difference between the the highest-ranked barn chosen and that
lowest-ranked barn chosen) of barn rankings the cows give their assigned
barns is as small as possible.
Input
Lines 2..N+1: Each line contains B space-separated integers which
are exactly 1..B sorted into some order. The first integer on line i+1
is the number of the cow i's top-choice barn, the second integer on that
line is the number of the i'th cow's second-choice barn, and so on.
Line N+2: B space-separated integers, respectively the capacity of
the first barn, then the capacity of the second, and so on. The sum of
these numbers is guaranteed to be at least N.
Output
Sample Input
6 4
1 2 3 4
2 3 1 4
4 2 3 1
3 1 2 4
1 3 4 2
1 4 2 3
2 1 3 2
Sample Output
2
Hint
Each cow can be assigned to her first or second choice: barn 1 gets
cows 1 and 5, barn 2 gets cow 2, barn 3 gets cow 4, and barn 4 gets cows
3 and 6.
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <math.h>
#include <iostream>
#include <math.h>
using namespace std;
const int N = ;
const int INF = ;
struct Edge{
int v,next;
int w;
}edge[N*N];
struct Cow{
int love[];
}cow[N];
int head[N];
int level[N];
int graph[N][N],dis[N][N],cap[N];
int tot;
void init(){
memset(head,-,sizeof(head));
tot=;
}
void addEdge(int u,int v,int w,int &k){
edge[k].v = v,edge[k].w=w,edge[k].next=head[u],head[u]=k++;
edge[k].v = u,edge[k].w=,edge[k].next=head[v],head[v]=k++;
}
int BFS(int src,int des){
queue<int >q;
memset(level,,sizeof(level));
level[src]=;
q.push(src);
while(!q.empty()){
int u = q.front();
q.pop();
if(u==des) return ;
for(int k = head[u];k!=-;k=edge[k].next){
int v = edge[k].v;
int w = edge[k].w;
if(level[v]==&&w!=){
level[v]=level[u]+;
q.push(v);
}
}
}
return -;
}
int dfs(int u,int des,int increaseRoad){
if(u==des) return increaseRoad;
int ret=;
for(int k=head[u];k!=-;k=edge[k].next){
int v = edge[k].v;
int w = edge[k].w;
if(level[v]==level[u]+&&w!=){
int MIN = min(increaseRoad-ret,w);
w = dfs(v,des,MIN);
if(w>){
edge[k].w -=w;
edge[k^].w+=w;
ret+=w;
if(ret==increaseRoad) return ret;
}else level[v] = -;
}
}
return ret;
}
int Dinic(int src,int des){
int ans = ;
while(BFS(src,des)!=-) ans+=dfs(src,des,INF);
return ans;
}
int n,b,src,des;
int build(int t,int mid){
init();
for(int i=;i<=b;i++){
addEdge(src,i,cap[i],tot);
}
for(int i=;i<=n;i++){
addEdge(i+b,des,,tot);
}
for(int i=t;i<=t+mid-&&i<=b;i++){
for(int j=;j<=n;j++){
addEdge(cow[j].love[i],j+b,,tot);
}
}
return Dinic(src,des);
}
int main(){
scanf("%d%d",&n,&b);
src = ,des = n+b+;
for(int i=;i<=n;i++){
for(int j=;j<=b;j++){
scanf("%d",&cow[i].love[j]);
}
}
for(int i=;i<=b;i++) scanf("%d",&cap[i]);
int l =,r = b;
int ans = b;
while(l<=r){
int mid = (l+r)>>; ///差值
bool flag = false;
for(int i=;i<=b;i++){ ///枚举最小值
if(build(i,mid)==n) {
flag = ;
break;
}
}
if(flag) {
ans = mid;
r = mid-;
}else l = mid+;
}
printf("%d\n",ans);
}
最新文章
- 对Hibernate的理解
- Struts+Hibernate+Spring实现用户登录功能
- VS开发好用的扩展
- paip.不同目录结构哈的文件批量比较
- Html5实践之EventSource
- MySQL内核深度优化
- sqlserver函数大全
- iOS开发中使用Bmob RESTful API
- IIS实现301重定向
- unix 文件属性
- 实习之vim基本学习
- VMware 虚拟机的网络连接方式详解
- SSM之整合Redis
- IDEA-最简单的struts2项目 关于lib项目的默认位置
- linux无法联网使用yum提示cannot find a valid baseurl for repobase7x86_64
- sku回忆笔记
- .NET 序列化成XML, 并且格式化
- go标准库的学习-io/ioutil
- python 全栈开发,Day125(HTML5+ 初识,HBuilder,夜神模拟器,Webview)
- spring oxm入门(包含demo)
热门文章
- CF-1143D. The Beatles
- IIS7.0/8.0的错误HTTP Error 500.19 - Internal Server Error ,错误代码为0x80070021
- 8.Yii2.0框架控制器接收get.post数据
- pyecharts用法,本人亲测,陆续更新
- POJ 1791 Parallelogram Counting(求平行四边形数量)
- Kubernetes(k8s)底层网络原理刨析
- mysql查询的语法
- 编程哲学之 C# 篇:007——如何创造万物
- [转] 在vue中使用SockJS实现webSocket通信
- 大数据学习——akka自定义RPC