POJ3189二分最大流(枚举下界,二分宽度,最大流判断可行性)
题意:
有n头猪,m个猪圈,每个猪圈都有一定的容量(就是最多能装多少只猪),然后每只猪对每个猪圈的喜好度不同(就是所有猪圈在每个猪心中都有一个排名),然后要求所有的猪都进猪圈,但是要求所有的喜好度排名最低的和最高的差值的绝对值最小,输出这个最小的差值,就是是每个猪进猪圈后都会产生一个范围,就是最喜欢和最不喜欢(用排名的名次表示),然后把所有的范围放在一起,最小的端点个最大的端点的差的绝对值最小是多少?
思路:
做了将近两个小时才搞定,一直是超时,先说下我的做法,就是枚举下界,二分答案,然后DINIC判断是否可行,用G++交跑100+ms,用C++交超时,还有一个目测比较快的方法,就是把上面的DINIC换成多重匹配,多重匹配处理二分图的时候比DINIC快,所以理论上更优,可惜我没写过多重匹配,这个会的可以试试,最后我用匈牙利,然后暴力拆点去模拟多重匹配,超时了,呵呵,下面是我一开始最笨的方法,枚举下界+二分答案+DINIC判断可行性的代码,还有就是提醒下,输入的时候那个排名什么的要看清楚,就是读懂输入,嘿嘿别的没啥。
用G++提交
枚举起点,二分长度,最大流判断可行。
#include<queue>
#include<stdio.h>
#include<string.h>
#define N_node 1000 + 20 + 5
#define N_edge (1000 * 20 + 1000 + 20) * 2 + 5000
#define INF 1000000000
using namespace std;
typedef struct
{
int to ,cost ,next;
}STAR;
typedef struct
{
int x ,t;
}DEP;
STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,listt[N_node] ,tot;
int deep[N_node];
int Sort[1005][22];
int Cow[22];
int ANS ,N;
void add(int a ,int b ,int c)
{
E[++tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
E[++tot].to = a;
E[tot].cost = 0;
E[tot].next = list[b];
list[b] = tot;
}
int minn(int x ,int y)
{
return x < y ? x : y;
}
bool BFS_Deep(int s ,int t ,int n)
{
memset(deep ,255 ,sizeof(deep));
xin.x = s ,xin.t = 0;
deep[xin.x] = xin.t;
queue<DEP>q;
q.push(xin);
while(!q.empty())
{
tou = q.front();
q.pop();
for(int k = list[tou.x] ;k ;k = E[k].next)
{
xin.x = E[k].to;
xin.t = tou.t + 1;
if(deep[xin.x] != -1 || !E[k].cost)
continue;
deep[xin.x] = xin.t;
q.push(xin);
}
}
for(int i = 0 ;i <= n ;i ++)
listt[i] = list[i];
return deep[t] != -1;
}
int DFS_Flow(int s ,int t ,int flow)
{
if(s == t) return flow;
int nowflow = 0;
for(int k = listt[s] ;k ;k = E[k].next)
{
listt[s] = k;
int to = E[k].to;
int c = E[k].cost;
if(deep[to] != deep[s] + 1 || !c)
continue;
int tmp = DFS_Flow(to ,t, minn(c ,flow - nowflow));
nowflow += tmp;
E[k].cost -= tmp;
E[k^1].cost += tmp;
if(flow == nowflow)
break;
}
if(!nowflow) deep[s] = 0;
return nowflow;
}
int DINIC(int s ,int t ,int n)
{
int Ans = 0;
while(BFS_Deep(s ,t ,n))
{
Ans += DFS_Flow(s ,t ,INF);
if(Ans == N) break;
}
return Ans;
}
void Buid(int n ,int m ,int a ,int b)
{
memset(list ,0 ,sizeof(list));
tot = 1;
for(int i = 1 ;i <= n ;i ++)
add(0 ,i ,1);
for(int i = 1 ;i <= m ;i ++)
add(i + n ,m + n + 1 ,Cow[i]);
for(int i = 1 ;i <= n ;i ++)
for(int j = 1 ;j <= m ;j ++)
if(Sort[i][j] >= a && Sort[i][j] <= b)
add(i ,j + n ,1);
}
int solve(int n ,int m ,int ii)
{
int low = 0 ,up = m - ii ,mid ,Ans = INF;
if(up > ANS) up = ANS;
while(low <= up)
{
mid = (low + up) >> 1;
Buid(n ,m ,ii ,ii + mid);
if(DINIC(0 ,n + m + 1 ,n + m + 1) == n)
{
Ans = mid;
up = mid - 1;
}
else low = mid + 1;
}
return Ans;
}
int main ()
{
int n ,m ,i ,j ,a;
while(~scanf("%d %d" ,&n ,&m))
{
N = n;
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= m ;j ++)
{
scanf("%d" ,&a);
Sort[i][a] = j;
}
for(i = 1 ;i <= m ;i ++)
scanf("%d" ,&Cow[i]);
ANS = INF;
for(i = 1 ;i <= m ;i ++)
{
ANS = minn(ANS ,solve(n ,m ,i));
}
printf("%d\n" ,ANS + 1);
}
return 0;
}
最新文章
- C#开发微信门户及应用(25)-微信企业号的客户端管理功能
- iOS 开发之路(WKWebView内嵌HTML5之图片上传) 五
- Android 图文数据JSON解析,金山词霸每日一句API的调用
- Spark External Datasets
- Oracle监听器启动出错:本地计算机上的OracleOraDb11g_home1TNSListener服务启动后又停止了解决方案
- LCT裸题泛做
- iMacros 教程
- Hibernate4 执行存储过程
- cocos2d ccmenulabel
- Struts2_搭建环境及HelloWorld
- NSString NSMutableString copy mutableCopy retain weak strong整合
- Oracle extent
- AxisFault另外一个问题
- OpenCV——分水岭算法
- struts2的<;constant/>;标签使用
- How Many Answers Are Wrong
- 归并排序-JAVA实现
- POJ 1015 Jury Compromise (算竞进阶习题)
- express + restful
- JAVA分布式架构的演进
热门文章
- pip命令安装python包到指定目录
- MVC模式从Controller返回内容协商格式(Json或者Xml)
- 【python+selenium的web自动化】- 8种元素定位方式详解
- java 各种类型转换
- 用 Go + WebSocket 快速实现一个 chat 服务
- 力扣 - 剑指 Offer 37. 序列化二叉树
- 前端学习 node 快速入门 系列 —— 报名系统 - [express]
- EfficientNet &; EfficientDet 论文解读
- [图论]最优布线问题:kruskal
- 【Azure 微服务】Service Fabric中微服务在升级时,遇见Warning - System.Collections.Generic.KeyNotFoundException 服务无法正常运行