欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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.很抱歉,费用流也还没学,待填坑