transaction transaction transaction HDU - 6201
程序员文章站
2024-02-24 17:47:40
...
是一道有很多种解法的题目,但我在场上是用DFS做的,交了两遍,第一遍ME,第二遍TE。今天补题时看了大佬的博客发现这道题目是有很多种解法,自己一种也没想不出来,有点弱啊。总结来说有三种一种是转化成最短路,第二种是树形DP,第三种是费用流。
1.最短路。以前做过一种自己加起点的题,场上想过是最短路,但无奈自己不会转化。
<1>加一个超级起点 0 和一个超级终点 n+1,0与每个城市相连,他们之间的边权值为0,n+1与每个城市相连,边权值也是0,然后把相连的城市的边权值改成 买卖所得利润 - 路费,因为会有负值,所以用Bellman-Ford算法跑一下最长路就可以了
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <cmath>
#include <stack>
#include <map>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define mod 1000000007;
using namespace std;
const int maxn = 100000 + 10;
struct Edge
{
int from,to,dist;
Edge(int f,int t,int d):from(f),to(t),dist(d){}
};
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];
int d[maxn];
int p[maxn];
int cnt[maxn];
int price[maxn];
void init()
{
for(int i=0;i<=n+1;i++) G[i].clear();
edges.clear();
}
void addedge(int from,int to,int dist)
{
edges.push_back(Edge(from,to,dist));
int p = edges.size();
G[from].push_back(p - 1);
}
bool negativecycle(int s)
{
queue<int> q;
memset(inq,0,sizeof(inq));
memset(cnt,0,sizeof(cnt));
for(int i=0;i<=n+1;i++) d[i] = -INF;
inq[s] = true,d[s] = 0,q.push(s);
while(!q.empty())
{
int u = q.front(); q.pop();
inq[u] = false;
for(int i=0;i<(int)G[u].size();i++)
{
Edge &e = edges[G[u][i]];
//printf("%d %d %d\n",e.to,d[e.to],d[u] + e.dist);
if(d[e.to] < d[u] + e.dist)
{
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
if(!inq[e.to])
{
q.push(e.to);
inq[e.to] = true;
if(++cnt[e.to] > n) return true;
}
}
}
}
return true;
}
int main()
{
int k;
scanf("%d",&k);
while(k--)
{
scanf("%d",&n);
m = n - 1;
init();
for(int i=1;i<=n;i++)
{
scanf("%d",&price[i]);
addedge(0,i,0);
//addedge(i,0,0);
addedge(i,n+1,0);
//addedge(n+1,i,0);
}
int a,b,c;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
//printf("%d %d\n",price[b] - price[a] - c,price[a] - price[b] - c);
addedge(a,b,price[b] - price[a] - c);
addedge(b,a,price[a] - price[b] - c);
}
negativecycle(0);
printf("%d\n",d[n+1]);
}
return 0;
}
<2>加一个超级起点 0 和一个超级终点 n+1,0与每个城市 i 相连,他们之间的边权值为 -price[i],代表买书的成本,n+1与每个城市 i 相连,边权值是price[i],代表卖书的钱,然后把相连的城市的边权值改成两城市距离的负值,同样因为会有负值,所以用Bellman-Ford算法跑一下最长路。
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <cmath>
#include <stack>
#include <map>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define mod 1000000007;
using namespace std;
const int maxn = 100000 + 10;
struct Edge
{
int from,to,dist;
Edge(int f,int t,int d):from(f),to(t),dist(d){}
};
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];
int d[maxn];
int p[maxn];
int cnt[maxn];
int price[maxn];
void init()
{
for(int i=0;i<=n+1;i++) G[i].clear();
edges.clear();
}
void addedge(int from,int to,int dist)
{
edges.push_back(Edge(from,to,dist));
int p = edges.size();
G[from].push_back(p - 1);
}
bool negativecycle(int s)
{
queue<int> q;
memset(inq,0,sizeof(inq));
memset(cnt,0,sizeof(cnt));
for(int i=0;i<=n+1;i++) d[i] = -INF;
inq[s] = true,d[s] = 0,q.push(s);
while(!q.empty())
{
int u = q.front(); q.pop();
inq[u] = false;
for(int i=0;i<(int)G[u].size();i++)
{
Edge &e = edges[G[u][i]];
//printf("%d %d %d\n",e.to,d[e.to],d[u] + e.dist);
if(d[e.to] < d[u] + e.dist)
{
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
if(!inq[e.to])
{
q.push(e.to);
inq[e.to] = true;
if(++cnt[e.to] > n) return true;
}
}
}
}
return true;
}
int main()
{
int k;
scanf("%d",&k);
while(k--)
{
scanf("%d",&n);
m = n - 1;
init();
for(int i=1;i<=n;i++)
{
scanf("%d",&price[i]);
addedge(0,i,-price[i]);
//addedge(i,0,0);
addedge(i,n+1,price[i]);
//addedge(n+1,i,0);
}
int a,b,c;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
//printf("%d %d\n",price[b] - price[a] - c,price[a] - price[b] - c);
addedge(a,b,-c);
addedge(b,a,-c);
}
negativecycle(0);
printf("%d\n",d[n+1]);
}
return 0;
}
<1><2>均需注意0与城市以及n+1与城市是单向路,城市与城市之间是双向路
2.树形DP还没学,学了以后来填坑
3.很抱歉,费用流也还没学,待填坑
上一篇: hdu 6119 小小粉丝度度熊
推荐阅读
-
浅谈Android app开发中Fragment的Transaction操作
-
python django事务transaction源码分析详解
-
maven构建项目引用spring找不到org.springframework.transaction 博客分类: java transactionspringframeworkmaven
-
transaction transaction transaction HDU - 6201
-
hdu 6201 transaction transaction transaction(最长路)
-
浅谈Android app开发中Fragment的Transaction操作
-
python django事务transaction源码分析详解
-
C#事务处理(Execute Transaction)实例解析
-
闪回事务查询Flashback Transaction Query
-
PHP Mysql Transaction