hdu 6201 transaction transaction transaction(最长路)
程序员文章站
2024-02-24 17:38:49
...
transaction transaction transaction
题目链接:transaction transaction transaction
题意:给你一棵树,每个点都有点权,每条边也有边权,要求选择起点S和终点T,使得
思路:建立源点和汇点,源点到树上所有点的权值为
代码:
#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;
}