BZOJ1305/Luogu3153 [CQOI2009]dance跳舞 (network flow)
2024-10-20 13:54:15
#define T 1001
#define S 0
struct Edge{
int nxt,pre,w;
}e[500007];
int cntEdge,head[N];
inline void add(int u,int v,int w){
e[++cntEdge] = (Edge){head[u], v, w}, head[u] = cntEdge;
}
inline void Add(int u,int v,int w){
add(u, v, w);
add(v, u, 0);
}
int q[N],h[N];
inline bool BFS(){
int t = 0, w = 1;
Fill(h, -1);
h[0] = 0, q[0] = 0;
while(t != w){
int u = q[t++];
for(register int i = head[u]; i; i =e[i].nxt){
int v = e[i].pre;
if(e[i].w && h[v] == -1){
h[v] = h[u] + 1;
q[w++] = e[i].pre;
}
}
}
return h[T] != -1;
}
inline int DFS(int u, int f){
if(u == T) return f;
int w, used = 0;
for(register int i = head[u]; i; i = e[i].nxt){
int v = e[i].pre;
if(h[v] == h[u] + 1){
w = DFS(v, Min(f - used, e[i].w));
e[i].w -= w, e[i^1].w += w;
used += w;
if(used == f) return f;
}
}
if(!used) h[u] = -1;
return used;
}
inline int Dinic(){
int sum = 0;
while(BFS()){
sum += DFS(0, 0x7fffffff);
}
return sum;
}
int n,k,mp[N][N];
inline void Build(int &mid){
cntEdge=1;
Fill(head, 0);
R(i,1,n) Add(S, i, mid);
R(i,1,n) Add(i, i + 500, k);
R(i,1,n) Add(i + n + 500, i + n, k);
R(i,1,n) Add(i + n, T, mid);
R(i,1,n){
R(j,1,n){
if(mp[i][j])
Add(i, n + j, 1);
else
Add(i + 500, n + j + 500, 1);
}
}
}
int main(){
io >> n >> k;
R(i,1,n){
char str[57];
scanf("%s", str + 1);
R(j,1,n)
mp[i][j] = (str[j] == 'Y');
}
int maxx = 0;
int l = 0, r = 50;
while(l<=r){
int mid = (l + r) >> 1;
Build(mid);
int ans = Dinic();
if(ans >= n * mid){
maxx = mid;
l = mid + 1;
}
else
r = mid - 1;
}
printf("%d", maxx);
return 0;
}
最新文章
- lua随机数函数
- The main difference between Java & C++（转载）
- LA 2038
- Django开发网站（四）
- js实现点击ul/li等改变背景颜色
- esxi5.5 安装，虚拟机复制
- μC/OS学习资料（附Ebook）
- Vue 单选框与单选框组 组件
- angular2 图片赋值的时候前面自动加 unsafe:xxx 导致图片信息不显示问题
- kafka性能调优(转)
- [转]How to log queries using Entity Framework 7?
- html5调用手机本地摄像头和相册识别二维码详细实现过程
- 重写 View 的 Touch 方法，实现一个酷炫的九宫格图片
- linux下perforce(p4)的使用方法和命令
- 卡在Initializing Spring root WebApplicationContext
- 14、SpringBoot-CRUD错误处理机制（1）
- iOS URL加解密
- Unity 游戏对象的组件列表
- HTML5中最看重的理念“语义化”相比HTML有什么区别？
- Windows平台下MySQL常用操作与命令