transaction transaction transaction 最大费用最大流转化到SPFA最长路
2024-08-30 19:51:10
//当时比赛的时候没有想到可以用SPFA做,TLE!
Problem Description
Kelukin is a businessman. Every day, he travels around cities to do some business. On August 17th, in memory of a great man, citizens will read a book named "the Man Who Changed China". Of course, Kelukin wouldn't miss this chance to make money, but he doesn't have this book. So he has to choose two city to buy and sell.
As we know, the price of this book was different in each city. It is ai yuan in it city. Kelukin will take taxi, whose price is 1yuan per km and this fare cannot be ignored.
There are n−1 roads connecting n cities. Kelukin can choose any city to start his travel. He want to know the maximum money he can get.
As we know, the price of this book was different in each city. It is ai yuan in it city. Kelukin will take taxi, whose price is 1yuan per km and this fare cannot be ignored.
There are n−1 roads connecting n cities. Kelukin can choose any city to start his travel. He want to know the maximum money he can get.
Input
The first line contains an integer T (1≤T≤10) , the number of test cases.
For each test case:
first line contains an integer n (2≤n≤100000) means the number of cities;
second line contains n numbers, the ith number means the prices in ith city; (1≤Price≤10000)
then follows n−1 lines, each contains three numbers x, y and z which means there exists a road between x and y, the distance is zkm (1≤z≤1000).
For each test case:
first line contains an integer n (2≤n≤100000) means the number of cities;
second line contains n numbers, the ith number means the prices in ith city; (1≤Price≤10000)
then follows n−1 lines, each contains three numbers x, y and z which means there exists a road between x and y, the distance is zkm (1≤z≤1000).
Output
For each test case, output a single number in a line: the maximum money he can get.
Sample Input
1
4
10 40 15 30
1 2 30
1 3 2
3 4 10
4
10 40 15 30
1 2 30
1 3 2
3 4 10
Sample Output
8
Source
Recommend
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<queue>
#include<deque>
#include<iomanip>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<functional>
#include<fstream>
#include<memory>
#include<list>
#include<string>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL; //最大费用最大流 简化到SPFA上特例
const int MAXN = + ;
struct edge
{
int to, next, cost;
}E[MAXN << ];
int head[MAXN], tot, n;
int val[MAXN];
bool vis[MAXN];
int lowcost[MAXN];
void init()
{
memset(head, -, sizeof(head));
tot = ;
}
void addedge(int u, int v, int d)
{
E[tot].to = v;
E[tot].cost = d;
E[tot].next = head[u];
head[u] = tot++;
}
int spfa(int st, int ed)
{
memset(vis, false, sizeof(vis));
memset(lowcost, , sizeof(lowcost));
queue<int> q;
q.push(st);
vis[st] = true;
lowcost[st] = ;
while (!q.empty())
{
int f = q.front();
q.pop();
vis[f] = false;
for (int i = head[f]; i != -; i = E[i].next)
{
int v = E[i].to, d = E[i].cost;
if (lowcost[v] < lowcost[f] + d)
{
lowcost[v] = lowcost[f] + d;
if (!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
return lowcost[ed];
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
init();
scanf("%d", &n);
for (int i = ; i <= n; i++)
{
scanf("%d", &val[i]);
addedge(, i, val[i]);
addedge(i, n + , -val[i]);
}
int u, v, d;
for (int i = ; i < n - ; i++)
{
scanf("%d%d%d", &u, &v, &d);
addedge(u, v, -d);
addedge(v, u, -d);
}
printf("%d\n", spfa(, n + ));
}
}
最新文章
- 10年C#历程的MVP之路与MVP项目介绍
- css引入方式
- 在VMware的虚拟机平台上如何进行网络设置
- Swift 1.2 正式发布 - 带来很多重大改进
- 转JSONObject put,accumulate,element的区别
- python文件_写入
- div+css+javascript 走马灯图片轮换显示
- HBA简介及原理
- XMPP 服务器 Openfire 的 Emoji 支持问题(进行部分修改)
- Socket通信之Java学习(一)
- MySQL一对一:一对多:多对多: 实例!!!!
- Python自动化中的键盘事件
- Gin 路由解析树详解
- Linux查看实时网卡流量的几种方式
- Multidex(二)之Dex预加载优化
- linux运维之分析系统负载及运行状况
- php的反射
- 第12章—使用NoSQL数据库—使用MongoDB+Jpa操作数据库
- (转)Mysql数据库主从心得整理
- [19/04/17-星期三] Java的动态性_反射(Reflection)机制