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

hdu 6201 transaction transaction transaction(最长路)

程序员文章站 2024-02-24 17:38:49
...

transaction transaction transaction

题目链接:transaction transaction transaction

题意:给你一棵树,每个点都有点权,每条边也有边权,要求选择起点S和终点T,使得valTvalSval最大

思路:建立源点和汇点,源点到树上所有点的权值为p[i],树上所有点到汇点的权值为p[i],然后直接建图,spfa跑最长路即可

代码:

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
struct edge
{
    int v,w,next;
} E[maxn<<2];
int inq[maxn],dis[maxn],first[maxn],p[maxn];
int n,len;

inline void scan_d(int &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
        ret = ret * 10 + (c - '0'), c = getchar();
}

int spfa(int st,int ed)
{
    memset(inq,0,sizeof(inq));
    memset(dis,0,sizeof(dis));
    queue<int>q;
    q.push(st),inq[st]=1;
    while(!q.empty())
    {
        st=q.front();
        q.pop(),inq[st]=0;
        for(int i=first[st]; ~i; i=E[i].next)
        {
            int v=E[i].v,w=E[i].w;
            if(dis[v]<dis[st]+w)
            {
                dis[v]=dis[st]+w;
                if(!inq[v])
                {
                    inq[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return dis[ed];
}

void add_edge(int u,int v,int w)
{
    E[len].v=v,E[len].w=w,E[len].next=first[u],first[u]=len++;
}

int main()
{
    int t;
    scan_d(t);
    while(t--)
    {
        memset(first,-1,sizeof(first));
        scan_d(n);
        for(int i=1; i<=n; ++i)
            scan_d(p[i]);
        len=0;
        for(int i=1; i<=n; ++i)
            add_edge(0,i,p[i]),add_edge(i,n+1,-p[i]);
        int u,v,w;
        for(int i=1; i<n; ++i)
        {
            scan_d(u),scan_d(v),scan_d(w);
            add_edge(u,v,-w),add_edge(v,u,-w);
        }
        printf("%d\n",spfa(0,n+1));
    }
    return 0;
}



直接跑n边spfa竟然没超时

代码:

#include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn=1e5+10;
struct edge
{
    int v,w,next;
} E[maxn<<1];
int p[maxn],d[maxn],first[maxn];
int n,len;

inline void scan_d(int &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
        ret = ret * 10 + (c - '0'), c = getchar();
}

void spfa(int u)
{
    queue<int>q;
    q.push(u);
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(int i=first[u]; ~i; i=E[i].next)
        {
            int v=E[i].v,w=E[i].w;
            if(d[v]<d[u]+w)
            {
                d[v]=d[u]+w;
                q.push(v);
            }
        }
    }
}

void add_edge(int u,int v,int w)
{
    E[len].v=v,E[len].w=w,E[len].next=first[u],first[u]=len++;
}

int main()
{
    int t;
    scan_d(t);
    while(t--)
    {
        scan_d(n);
        for(int i=1; i<=n; ++i)
            scan_d(p[i]);
        memset(first,-1,sizeof(first));
        len=0;
        int u,v,w;
        for(int i=1; i<n; ++i)
        {
            scan_d(u),scan_d(v),scan_d(w);
            add_edge(u,v,p[v]-p[u]-w);
            add_edge(v,u,p[u]-p[v]-w);
        }
        memset(d,0,sizeof(d));
        for(int i=1; i<=n; ++i)
            spfa(i);
        int maxx=0;
        for(int i=1; i<=n; ++i)
            maxx=max(maxx,d[i]);
        printf("%d\n",maxx);
    }
    return 0;
}
相关标签: hdu-6201 最长路