[CQOI2009]DANCE跳舞(ISAP写法)
2024-09-21 14:02:29
https://daniu.luogu.org/problemnew/show/3153
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream> using namespace std; #define N 2501
#define M 3001
#define inf 2e9 int n,k;
char s[];
bool mp[][]; int tot;
int front[N],to[M<<],nxt[M<<],val[M<<],from[M<<]; int src,decc; int cur[N]; int path[N],num[N],lev[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w; from[tot]=u;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; val[tot]=; from[tot]=v;
//cout<<u<<' '<<v<<'\n';
} void rebuild(int mid)
{
tot=;
memset(front,,sizeof(front));
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
if(mp[i][j]) add(i,n*+j,);
else add(n+i,n*+j,);
for(int i=;i<=n;++i) add(src,i,mid);
for(int i=;i<=n;++i) add(n*+i,decc,mid);
for(int i=;i<=n;++i) add(i,n+i,k);
for(int i=;i<=n;++i) add(n*+i,n*+i,k);
} bool bfs()
{
queue<int>q;
for(int i=src;i<=decc;++i) lev[i]=decc;
q.push(decc);
lev[decc]=;
int now,t;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=front[now];i;i=nxt[i])
{
t=to[i];
if(lev[t]==decc && val[i^])
{
lev[t]=lev[now]+;
q.push(t);
}
}
}
return lev[src]!=decc;
} int augment()
{
int now=decc,flow=inf;
int i;
while(now!=src)
{
i=path[now];
flow=min(flow,val[i]);
now=from[i];
}
now=decc;
while(now!=src)
{
val[path[now]]-=flow;
val[path[now]^]+=flow;
now=from[path[now]];
}
return flow;
} int max_flow(int mid)
{
int flow=;
if(!bfs()) return ;
memset(num,,sizeof(num));
for(int i=src;i<=decc;++i) num[lev[i]]++,cur[i]=front[i];
int now=src; int t;
while(lev[src]<=decc)
{
if(now==decc)
{
flow+=augment();
now=src;
}
int advanced=false;
for(int i=cur[now];i;i=nxt[i])
{
t=to[i];
if(val[i]> && lev[t]==lev[now]-)
{
advanced=true;
path[t]=i;
cur[now]=i;
now=t;
break;
}
}
if(!advanced)
{
int m=decc-;
for(int i=front[now];i;i=nxt[i])
if(val[i]>) m=min(m,lev[to[i]]);
if(!--num[lev[now]]) break;
num[lev[now]=m+]++;
cur[now]=front[now];
if(now!=src) now=from[path[now]];
}
}
return flow;
} bool check(int mid)
{
rebuild(mid);
return max_flow(mid)==n*mid;
} int main()
{
read(n); read(k);
decc=n*+;
for(int i=;i<=n;++i)
{
scanf("%s",s+);
for(int j=;j<=n;++j) mp[i][j]=s[j]=='Y' ? true : false;
}
int l=,r=n,mid,ans;
while(l<=r)
{
mid=l+r>>;
if(check(mid)) ans=mid,l=mid+;
else r=mid-;
}
cout<<ans;
}
最新文章
- 【WP8.1】WebView笔记
- Cesium应用篇:2影像服务(上)
- [CareerCup] 17.9 Word Frequency in a Book 书中单词频率
- HDFS中的checkpoint( 检查点 )的问题
- StackExchange.Redis.Extensions.Core 源码解读之 Configuration用法
- web工程中URL地址的推荐写法
- Java并发编程:Java ConcurrentModificationException异常原因和解决方法
- USACO1.4.1 Packing Rectangles
- hdu 3849 (双联通求桥)
- js、jQuery操作input大全 不断完善
- memcache运维整理
- Codecs是以plugin的形式被调用的(显示中文的codec plugin文件是qcncodecs4.dll),可静态载入和动态载入
- POJ 1861 Network (模版kruskal算法)
- 【Python3爬虫】教你怎么利用免费代理搭建代理池
- spreadJs 自动换行功能和自动增高行高
- Alpha冲刺! Day6 - 砍柴
- web.xml中 /和/*的区别
- xgboost的sklearn接口和原生接口参数详细说明及调参指点
- 关于Unity中水和雾的使用
- [转]html 下拉框级联
热门文章
- 第二次作业<;1>;
- HDU 4123 Bob’s Race 树形dp+单调队列
- 08_Java基础语法_第8天(Eclipse)_讲义
- CefSharp,Winform程序中加载web网页
- [转帖] JVM虚拟机的历史
- android之layer-list
- python自动化之图像
- 锁对象-Lock: 同步问题更完美的处理方式 (ReentrantReadWriteLock读写锁的使用/源码分析)
- 理解Restful api的意义
- hbase 跳转过滤器skipfilter