bzoj4349: 最小树形图
2024-10-15 12:00:35
最小树形图模板题……
这种\(O(nm)\)的东西真的能考到么……
#include <bits/stdc++.h>
#define N 60
#define INF 1000000000
using namespace std;
int n, m, nn;
double ai[N], an[N], ci[][N][N], ans;
int bc[N];
int ini[N], vis[N], inc[N], inl[N];
int dfn;
int dfs(int t)
{
vis[t] = dfn;
if (vis[ini[t]] == vis[t])
return ini[t];
else if (vis[ini[t]])
return ;
else return dfs(ini[t]);
} int main()
{
scanf("%d", &n);
for (int i = ; i <= n; ++ i)
for (int j = ; j <= n; ++ j)
ci[][i][j] = INF;
for (int i = ; i <= n; ++ i)
scanf("%lf%d", &ai[i], &bc[i]), an[i] = ai[i], ci[][][i] = ai[i];
scanf("%d", &m);
for (int i = ; i <= m; ++ i)
{
int a, b; double c;
scanf("%d%d%lf", &a, &b, &c);
if (a != b) ci[][a][b] = min(ci[][a][b], c);
an[b] = min(an[b], c);
}
for (int i = ; i <= n; ++ i) ans += an[i] * (bc[i] - );
int tmp = , wh = ; nn = n;
while (wh)
{
wh = ;
for (int i = ; i <= nn; ++ i)
{
double mn = INF;
for (int j = ; j <= nn; ++ j)
if (ci[tmp][j][i] < mn)
mn = ci[tmp][j][i], ini[i] = j;
}
for (int i = ; i <= nn; ++ i) vis[i] = ; vis[] = -;
for (int i = ; i <= nn; ++ i)
if (!vis[i])
{
dfn ++;
int x = dfs(i);
if (x)
{
int tot = ;
wh = ;
for (int j = ; j <= nn; ++ j) inc[j] = ;
for (int j = ini[x]; j != x; j = ini[j]) inc[j] = ; inc[x] = ;
for (int j = ; j <= nn; ++ j) if (!inc[j]) inl[j] = tot ++; else ans += ci[tmp][ini[j]][j];
for (int j = ; j <= nn; ++ j)
for (int k = ; k <= nn; ++ k)
ci[!tmp][j][k] = INF;
for (int j = ; j <= nn; ++ j)
for (int k = ; k <= nn; ++ k)
{
if (!inc[j])
{
if (!inc[k])
ci[!tmp][inl[j]][inl[k]] = min(ci[!tmp][inl[j]][inl[k]], ci[tmp][j][k]);
else
ci[!tmp][inl[j]][tot] = min(ci[!tmp][inl[j]][tot], ci[tmp][j][k] - ci[tmp][ini[k]][k]);
}
else if (!inc[k])
ci[!tmp][tot][inl[k]] = min(ci[!tmp][tot][inl[k]], ci[tmp][j][k]);
}
nn = tot;
break;
}
}
if (!wh)
for (int i = ; i <= nn; ++ i) ans += ci[tmp][ini[i]][i];
else tmp ^= ;
}
printf("%.2lf", ans);
}
最新文章
- 如何设计一门语言(七)——闭包、lambda和interface
- canvas.drawBitmap()频繁调用导致应用崩溃问题
- FAST特征点检测features2D
- C语言再学习之内存对齐
- [转]jQuery EasyUI自定义DataGrid的Editor
- Python 函数式编程 &; Python中的高阶函数map reduce filter 和sorted
- 决策树算法实现(train+test,matlab) 转
- WCF如何在浏览器访问
- 关于我们-成功人士西装定制服务第一品牌派斯特PAISTETAILOR绅士礼服
- Windows Phone开发(3):棋子未动,先观全局
- xtraReprot 动态绑定数据 数据列动态
- RabbitMQ 消息队列 配置
- Valgrind 快速入门
- JavaScript Html页面加载完成三种写法
- 记录1-更换mac pro内存,硬盘及恢复系统
- &ldquo;耐撕&rdquo;团队 2016.03.31 站立会议
- nginx关闭全局access.log,error.log
- ReactiveX 学习笔记(13)基础类型
- 检出商品详情中的图片并替换url
- jQuery $ 的作用
热门文章
- 使用Bandwagon的VPS第一件事《FQ》
- elasticsearch按照配置时遇到的一些坑 [Failed to load settings from [elasticsearch.yml]]
- LISA介绍及其使用方法
- ICP算法(Iterative Closest Point迭代最近点算法)
- redis 命令
- IO流-----写到输出流
- Wpf usercontrol dispose
- matlab中pcolorh函数作用
- [Reproduced works]MongoDB Unauthorized Access Vulnerability
- Python 【第七章】:Html 和 CSS