囤题 [补档]_dk810510的博客-程序员宅基地

图论

网络流相关

CF 653 D

题目大意

给定一张\(n\)个点, \(m\)条边的有向图(\(n \le 50\), \(m \le 500\)), 每条边都有容量限制. 你要找到至少\(x\)条路径, 使得每条路径点容量都为某个定值\(F\), 且经过任意一条边点所有路径的容量之和小于等于这条边的容量. 求\(F\)的最大值.

题解

我们令原图的边集为\(E = \{ \left< u, v, w \right> \}\)
二分\(F\)的值, 对于一个确定点\(F\), 我们有每条边的最大经过次数. 将这个最大经过次数作为边的容量重新建图, 得到\(E' = \{ \left< u, v, c = \frac w F \right> \}\). 跑一遍最大流, 得到的流量即为可以选出的路径最大数量. 判断若最大流大于等于\(x\), 则对于当前的\(F\), 有可行方案, 否则没有可行方案.

#include <cstdio>
#include <cctype>
#include <cstring>
#include <climits>
#include <deque>
#include <algorithm>

using namespace std;
inline int getInt()
{
    int a = 0, sgn = 1; char c;
    while (! isdigit(c = getchar())) if (c == '-') sgn *= -1;
    while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
    return a * sgn;
}
typedef double D;
typedef long long LL;
const D EPS = 1e-8;
const LL INF = (LL)1e18;
const int N = 50, M = 500;
int n, m, x;
struct Record
{
    int u, v, w;
}rec[M + 7];
struct edge
{
    int v, nxt;
    LL w;
}edg[M * 2 + 7];
int tot, hd[N + 7], dis[N + 7];
inline void addEdge(int u, int v, LL w) { edg[tot].v = v; edg[tot].w = w; edg[tot].nxt = hd[u]; hd[u] = tot ++; }
inline int BFS()
{
    memset(dis, -1, sizeof dis); dis[1] = 0;
    deque<int> que; que.push_back(1);
    while (! que.empty())
    {
        int u = que.front(); que.pop_front();
        if (u == n) return 1;
        for (int p = hd[u]; ~ p; p = edg[p].nxt) if (edg[p].w && dis[edg[p].v] == -1) dis[edg[p].v] = dis[u] + 1, que.push_back(edg[p].v);
    }
    return 0;
}
LL DFS(int u, LL flw)
{
    if (u == n) return flw;
    LL usd = 0;
    for (int p = hd[u]; ~ p; p = edg[p].nxt) if (edg[p].w && dis[edg[p].v] == dis[u] + 1)
    {
        int v = edg[p].v;
        LL cur = DFS(v, min(edg[p].w, flw - usd));
        edg[p].w -= cur; edg[p ^ 1].w += cur;
        usd += cur;
        if (usd == flw) return usd;
    }
    return usd;
}
inline LL flow()
{
    LL sum = 0;
    while (BFS()) sum += DFS(1, INF);
    return sum;
}
int main()
{

#ifndef ONLINE_JUDGE

    freopen("bear.in", "r", stdin);
    freopen("bear.out", "w", stdout);
    
#endif
    
    n = getInt(); m = getInt(); x = getInt();
    for (int i = 0; i < m; ++ i) rec[i]. u = getInt(), rec[i].v = getInt(), rec[i].w = getInt();
    D L = 1e-5, R = 1e6;
    while (R - L > EPS)
    {
        D mid = (L + R) / 2;
        memset(hd, -1, sizeof hd);
        tot = 0; for (int i = 0; i < m; ++ i) addEdge(rec[i].u, rec[i].v, (LL)rec[i].w / mid), addEdge(rec[i].v, rec[i].u, 0);
        if (flow() < x) R = mid; else L = mid;
    }
    printf("%.7lf", L * (D)x);
}

CF 884 F

题目大意

给定一个由小写字母组成的串\(S\)(\(|S| \le 100\)), 每个位置有一个权值\(b_i\), 你要找到一个原串的排列\(T\), 满足对于每个\(i\)都有\(T_i \ne T_{|S| - i + 1}\), 并且使得这个排列的权值最大. 一个排列的权值为\(\sum_k b_k \times [T_k = S_k]\). 求这个权值.

保证存在至少一组合法的排列.

题解

最大费用最大流.

建立\(26\)个节点分别代表\(26\)个字母. 统计每个字母的出现次数, 从源点向每个字母的节点连一条容量为出现次数, 费用为\(0\)的边.

接着我们再建立\(\frac{|S|}2\)个节点, 代表不能相互冲突的一对位置. 考虑从字母向位置连边, 容量显然为\(1\), 费用则比较麻烦: 首先假如当前字母不等于\(S_i\)\(S_{|S| - i + 1}\), 则费用为\(0\); 假如等于其中的一个, 则费用为\(b\); 假如和这两个位置都相等, 则费用为\(\max(b_i, b_{|S| - i + 1})\).

最后, 从每个位置向汇点连一条容量为\(2\), 费用为\(0\)的边.

跑一遍最大费用的最大流即可.

#include <cstdio>
#include <cstring>
#include <deque>
#include <climits>

using namespace std;
const int N = 100;
const int V = N / 2 + 107;
const int E = 31 * N + 107;
int n;
int cnt[27];
int str[N + 7], b[N + 7];
struct edge
{
    int v, w, c, nxt;
}edg[E];
int hd[V], tot;
int pre[V], rec[V], inQueue[V], dis[V];
inline void addEdge(int u, int v, int w, int c) 
{
    edg[tot].v = v; edg[tot].w = w; edg[tot].c = c; edg[tot].nxt = hd[u]; hd[u] = tot ++;
    edg[tot].v = u; edg[tot].w = 0; edg[tot].c = - c; edg[tot].nxt = hd[v]; hd[v] = tot ++;
}
inline int SPFA()
{
    int t = 26 + n / 2 + 1;
    memset(pre, -1, sizeof pre);
    deque<int> que; que.push_back(0);
    memset(inQueue, 0, sizeof inQueue); inQueue[0] = 1;
    memset(dis, -127, sizeof dis); dis[0] = 0;
    while (! que.empty())
    {
        int u = que.front(); que.pop_front(); inQueue[u] = 0;
        for (int p = hd[u]; ~ p; p = edg[p].nxt) if (edg[p].w && dis[u] + edg[p].c > dis[edg[p].v])
        {
            int v = edg[p].v;
            dis[v] = dis[u] + edg[p].c; pre[v] = u; rec[v] = p;
            if (! inQueue[v]) inQueue[v] = 1, que.push_back(v);
        }
    }
    int mn = INT_MAX;
    for (int p = t; ~ pre[p]; p = pre[p]) mn = min(mn, edg[rec[p]].w);
    for (int p = t; ~ pre[p]; p = pre[p]) 
        edg[rec[p]].w -= mn, edg[rec[p] ^ 1].w += mn;
    return dis[t];
}
inline int flow()
{
    int sum = 0;
    while (1) { int tmp = SPFA(); if (tmp < - (int)2e9) return sum; sum += tmp; }
}
int main()
{

#ifndef ONLINE_JUDGE

    freopen("anti.in", "r", stdin);
    freopen("anti.out", "w", stdout);
    
#endif

    scanf("%d\n", &n);
    for (int i = 1; i <= n; ++ i) ++ cnt[str[i] = (getchar() - 'a' + 1)];
    for (int i = 1; i <= n; ++ i) scanf("%d", b + i);
    memset(hd, -1, sizeof hd); tot = 0;
    for (int i = 1; i <= 26; ++ i) addEdge(0, i, cnt[i], 0);
    for (int i = 1; i <= 26; ++ i) for (int j = 1; j <= n >> 1; ++ j) 
        addEdge(i, 26 + j, 1, max((str[j] == i) * b[j], (str[n - j + 1] == i) * b[n - j + 1]));
    for (int i = 1; i <= n >> 1; ++ i) addEdge(26 + i, 26 + n / 2 + 1, 2, 0);
    printf("%d\n", flow());
}

转载于:https://www.cnblogs.com/ZeonfaiHo/p/8379698.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/dk810510/article/details/101321262

智能推荐

Matlab中fgets函数使用_jk_101的博客-程序员宅基地_matlab fgets

fgets函数读取文件中的行,并保留换行符。语法tline = fgets(fileID)tline = fgets(fileID,nchar)[tline,ltout] = fgets(___)说明tline= fgets(fileID)读取指定文件中的下一行内容,并包含换行符。 tline= fgets(fileID,nchar)返回下一行中的最多nchar个字符。 [tline,ltout] = fgets(___)还在ltout中返回行终止符(如果有)...

再探Linux下的TCP延迟确认机制--TCP_QUICKACK_蓝白天际线的博客-程序员宅基地_quick ack被激活次数

转载:http://pananq.com/index.php/2011/08/29/%E5%86%8D%E6%8E%A2linux%E4%B8%8B%E7%9A%84tcp%E5%BB%B6%E8%BF%9F%E7%A1%AE%E8%AE%A4%E6%9C%BA%E5%88%B6/案例一:某同事随手写个压力测试程序,其实现逻辑为:每秒钟先连续发N个132字节的包,然后连续收N个由后台服务回显回...

机器学习入门:最大期望算法-3_奔腾游子的博客-程序员宅基地

机器学习入门:最大期望算法1、实验描述本实验通过使用EM算法解决部分观测数据的参数估计的难题,利用scikit-learn提供的EM模块,实现EM算法,创建模型,训练模型,然后利用模型计算均值、方差着数据,并最终用3d图示可视化结果。实验时长:45分钟主要步骤:设定随机种子数给定均值和方差生成模拟样本建立混合高斯模型利用样本,训练模型模型评估结果可视化2、实验环境虚拟机数量:1系统版本:CentOS 7.5scikit-lear

网页常见错误~比较简单_丑八怪~的博客-程序员宅基地

每次出现错误很烦,简单整理一下,详细具体大家可以搜索查看400:客户端发送请求服务端接受不了401:未授权403:注解方法调不通,比如跨域,访问被拒绝405:请求方式406:客户端浏览器不接受所请求的页面500:代码写错了200:代码成功...

量化交易之指数增强策略_jomes_wang的博客-程序员宅基地

不断地学习,才能使我们变得更加强大指数增强策略概念:指数增强策略是以对标的股市基准指数(如沪深300、中证500、中证1000)作为参考,在追踪对标股市基准指数的前提下,利用量化投资的方式进行主动管理,以获得市场收益(Beta)的同时获取超越市场超额收益(Alpha)的一种资产组合策略。还是看不懂吧?那就认真看。指数增强的收益来源主要有两方面:1.通过量化选股模型构造追踪标的指数的股...

Windows下apache+php的安装和配置_weixin_34148340的博客-程序员宅基地

一、php安装和配置1.下载和安装PHP下载地址http://windows.php.net/download,下载最新线程安全版PHP zip压缩包,解压到本地安装目录:C:\develop\php注意:下载的PHP VC版本不能比前面安装的vc redist版高2.配置在php目录下找到php.ini-development文件,复制一份并重命名为php.ini更改自...

随便推点

【react】【antd】【tinymce】富文本编辑器tinymce插件的使用_jiujiujiujiu_的博客-程序员宅基地_react富文本编辑器插件

React项目中使用富文本编辑器,使用插件powerpaste(解决了粘贴内容没有格式的问题)、lineheight(行高)、indent2em(首行缩进)。官方文档中不需要引入,但我的项目中不引入无效!!import lineheight from 'tinymce/plugins/lineheight'import indent2em from 'tinymce/plugins/indent2em'init={{ plugins: ['lineheight', 'powerpaste'

程序员和上班族常用的在线工具网站_tiomg.org的博客-程序员宅基地

在日常的办公当中,虽然因为需要使用某些个工具,但是我并不想下载和安装软件来塞满我的电脑。这里我给大家推荐一个在线工具网站:www.tiomg.org ,在点开网站之前先看看这些工具是否需要。1. 图片压缩在办理社保、公司OA报销附近常常提示图片附件太大无法上传;网站或博客图片优化;数码相片压缩。2. PDF文件转图片OA长期报销,需要将增值税电子PDF发票转图片贴到报销流程。公司各...

DB2 中 MQT 的匹配原理及使用技巧_LarryHai6的博客-程序员宅基地

http://www.ibm.com/developerworks/cn/data/library/techarticles/dm-1003lihf/DB2 中 MQT 的匹配原理及使用技巧MQT(Materialized Query Table,物化查询表)物化了涉及一个或多个表或昵称的查询的预先计算结果。而后续的查询可以通过全部或部分匹配 MQT

ChannelOption.SO_KEEPALIVE, true->java socket参数详解:KeepAlive _iteye_14994的博客-程序员宅基地

 当设置为true的时候,TCP会实现监控连接是否有效,当连接处于空闲状态的时候,超过了2个小时,本地的TCP实现会发送一个数据包给远程的 socket,如果远程没有发回响应,TCP会持续尝试11分钟,知道响应为止,如果在12分钟的时候还没响应,TCP尝试关闭socket连接。 keepalive不是说TCP的常连接,当我们作为服务端,一个客户端连接上来,如果设置了keeplive...

springboot与rabbitMQ实现延迟加载_知乎-小拿的博客-程序员宅基地

参考:http://blog.csdn.net/u014308482/article/details/53036770http://blog.csdn.net/i_vic/article/details/72742277里面的例子参考自这两篇博客,记录下使用过程。为什么要延迟加载:制定一项任务,在某个时间之后去执行,这种场景比较适合使用延迟加载的模式。    延迟队

mysql sql优化_追寻北极的博客-程序员宅基地

第一阶段:1,一定要正确设计索引2,一定要避免SQL语句全表扫描,所以SQL一定要走索引(如:一切的 > < != 等等之类的写法都会导致全表扫描)3,一定要避免 limit 10000000,20 这样的查询4,一定要避免 LEFT JOIN 之类的查询,不把这样的逻辑处理交给数据库5,每个表索引不要建太多,大数据时会增加数据库的写入压力第二阶段:1,采用分表技术(大表分小表)

推荐文章

热门文章

相关标签