[CQOI2009]跳舞 网络流
2024-08-28 06:03:47
题解：
首先最大时间不好求，而且数据范围很小，所以我们可以先二分一个最大时间，然后就只需要判断是否可行即可。
因此我们每二分一个mid，对于每个女生，连s ---> x : mid , x ---> x' : k.对于每个男生，连x ---> t : mid, x' ---> x : k.
对于每条边，如果为Y，连x ---> y.否则连x' ---> y'.
其中x和x'分别表示一个人和这个人拆分出来的点。
为什么这么连？
对于每个女生，连s ---> x : mid , x ---> x' : k。 其中s ---> x : mid 表示一共要进行mid次，x ---> x' : k表示这mid次中最多可以选k个和不喜欢的人相连。
对于每个男生，连x ---> t : mid, x' ---> x : k. 同上。
对于每条边，如果为Y，连x ---> y.否则连x' ---> y'. 如果是Y，说明互相喜欢，所以用原本的点相连，否则说明互相不喜欢，就用拆分出的点相连。因为拆分出的点最多只有k次机会，因此表示的是连向不喜欢的点。
我一开始是这么想的，但是为了看上去简单一点，对于每个女生，我连了s --- > x : lim - k, s --- > x' : k.
这样是不对的，因为这样就固定了喜欢的人也最多选lim - k个，而实际上是没有这个限制的。因此我们用x ---> x' : k的方法就可以去掉这个限制，并且可以让它相对动态的分配每次机会，而不是每次固定的只能选lim - k次喜欢的，和强制选k次不喜欢的。
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 400
#define ac 40000
#define inf 1000000000 int n, m, ans, all, sum, s, t, head, tail, x, addflow, k;
int Head[AC], Next[ac], date[ac], haveflow[ac], tot = ;
int have[AC], c[AC], good[AC], last[AC], q[ac];
char f[AC][AC]; inline int read()
{
int x = ;char c = getchar();
while(c > '' || c < '') c = getchar();
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x;
} void init()
{
memset(Head, , sizeof(Head));
memset(have, , sizeof(have));
memset(c, , sizeof(c));
ans = , tot = ;
} inline void add(int f, int w, int S)
{
date[++ tot] = w, Next[tot] = Head[f], Head[f] = tot, haveflow[tot] = S;
date[++ tot] = f, Next[tot] = Head[w], Head[w] = tot, haveflow[tot] = ;
//printf("%d %d : %d\n", f, w, S);
} inline void upmin(int &a, int b){
if(b < a) a = b;
} void build(int lim)
{
sum = lim * m;
for(R i = ; i <= n; i ++) add(s, i, lim), add(i, n + i, k);
for(R i = ; i <= n; i ++)
for(R j = ; j <= m; j ++)
{
if(f[i][j] == 'Y') add(i, n + n + j, );
else add(n + i, n + n + m + j, );
}
for(R i = ; i <= m; i ++) add(n + n + i, t, lim), add(n + n + m + i, n + n + i, k);
} void bfs()
{
head = tail = ;
q[++ tail] = t, c[t] = , have[] = ;
while(head < tail)
{
int x = q[++ head];
for(R i = Head[x]; i; i = Next[i])
{
int now = date[i];
if(!c[now] && haveflow[i ^ ])
++ have[c[now] = c[x] + ], q[++ tail] = now;
}
}
memcpy(good, Head, sizeof(Head));
} void aru()
{
while(x != s)
{
haveflow[last[x]] -= addflow;
haveflow[last[x] ^ ] += addflow;
x = date[last[x] ^ ];
}
ans += addflow;
} void isap()
{
bool done = false;
x = s, addflow = inf;
while(c[s] != all)
{
if(x == t) aru(), addflow = inf;
done = false;
for(R i = good[x]; i; i = Next[i])
{
int now = date[i];
good[x] = i;
if(c[now] == c[x] - && haveflow[i])
{
done = true, x = now, last[now] = i;
upmin(addflow, haveflow[i]);
break;
}
}
if(!done)
{
int go = all - ;
for(R i = Head[x]; i; i = Next[i])
if(c[date[i]] && haveflow[i]) upmin(go, c[date[i]]);
if(!(-- have[c[x]])) break;
++ have[c[x] = go + ], good[x] = Head[x];
if(x != s) x = date[last[x] ^ ];
}
}
} bool check(int lim)
{
init(), build(lim), bfs(), isap();
if(ans == sum) return true;
else return false;
} void half()
{
int l = , r = n, mid;
while(l < r)
{
mid = (l + r + ) >> ;
if(check(mid)) l = mid;
else r = mid - ;
}
printf("%d\n", l);
} void pre()
{
n = read(), m = n, k = read();
s = n + n + m + m + , t = s + , all = t + ;
for(R i = ; i <= n; i ++) scanf("%s", f[i] + );
} int main()
{
freopen("in.in", "r", stdin);
pre();
half();
fclose(stdin);
return ;
}
最新文章
- SVN修改已提交版本的注释
- javascript中String的fromCharCode()方法
- poj 2653 线段相交
- 基于Selenium的模拟浏览器采集
- yafphp框架
- hdu 1202 The calculation of GPA
- python_way day6 反射，正则 模块（进度条，hash）
- uva 242
- int型长度
- js代码 设为首页 加入收藏
- Semaphore — Windows API
- left join 连表时，on后多条件无效问题
- api-ms-win-crt-process-l1-1-0.dll 丢失的处理，遇到问题和完美解决
- python 小练习4
- python 回溯法 子集树模板 系列 —— 4、数字组合问题
- Qt下libusb-win32的使用(一)打印设备描述符
- list<T>集合中的Remove()、RemoveAt()、RemoveRange()、RemoveAll()的用法
- 【JVM】JVM参数说明和分析
- Redis高可用复制集群实现
- LTE中基于S1的切换