题解 P1073 【最优贸易】
renxiaoyao36 · · 题解
题目解析：寻找一个起点，一个终点，使他们两个差价最大。其中要求：起点可以从1抵达，终点可以抵达N号点。
（望管理员通过，目前我似乎没看到我这样的解法qwq）
解法：贪心+剪枝优化
核心原理：（更新了一下原理，其实原理应该是这个）从价格最高的点为卖出点开始枚举，那么最有可能获得最高差价。
那么我的解法是：
1.先遍历所有点，确定这个点是否可以抵达终点。
2.再遍历一遍，确定这个点可否从起点抵达。
3.对所有点价格进行升序排序。间接排序下标数组：pai
4.计算出每个点最多可以获得的差价maxget数组=这个点的价格-最低价格。
5.将maxget下标数组Pai2降序排序。（间接排序）
6.接下来开始从pai2[0]开始，从这个点开始bfs遍历所有可以抵达这个点的点，然后计算出获得的差价。（注意，pai2数组存储的是下标（间接排序））
重点优化来了！（没优化前80分两个超时，一优化直接总时间消耗变成220ms）
在遍历的同时，这个点打上标记，接下来按照pai2向下继续找点的时候，如果这个点在此前的遍历中被打上了标记，直接跳过！这里说的向下找点指的是找pai2数组里的下一个下标点。
因为接下来以这个点为终点时，一定可以经过这个点找到更高的卖家！
7.目前的差价ans如果已经高过了下一个maxget[pai2[i+1]]的话，直接输出（因为接下来不可能有更高的差价了）(也是一个重要优化，这个容易想到qwq)
全部结束的时候也输出一下ans。
接下来放代码：
#include <cstdio>
#include <cstdlib>
using namespace std;
long long int n,m;
long long int ans=0;
long long int *p;
long long int * maxget;
int cmp1(const void *a,const void *b)
{
return(p[*(long long int*)a]-p[*(long long int*)b]);
}
int cmp2(const void *a,const void *b)
{
return(maxget[*(long long int*)b]-maxget[*(long long int*)a]);
}
int main(void)
{
//freopen("trade.in","r",stdin);
//freopen("trade.out","w",stdout);
scanf("%lld %lld",&n,&m);
p=(long long int*)calloc(n,sizeof(long long int ));
long long int **r=(long long int **)calloc(n,sizeof(long long int*));
bool* reachable=(bool*)calloc(n,sizeof(bool));
for(long long int i=0;i<n;i++)
{
r[i]=(long long int *)calloc(1,sizeof(long long int));
r[i][0]=0;
scanf("%lld",&p[i]);
}
reachable[0]=1;
for(long long int i=0;i<m;i++)
{
long long int a,b,c;
scanf("%lld %lld %lld",&a,&b,&c);
a--;b--;
if(c==1)
{
if(reachable[a])reachable[b]=1;
r[b][0]++;
r[b]=(long long int*)realloc(r[b],sizeof(long long int)*(r[b][0]+1));
r[b][r[b][0]]=a;
}
else if(c==2)
{
if(reachable[a])reachable[b]=1;
if(reachable[b])reachable[a]=1;
r[a][0]++;
r[a]=(long long int*)realloc(r[a],sizeof(long long int)*(r[a][0]+1));
r[a][r[a][0]]=b;
r[b][0]++;
r[b]=(long long int*)realloc(r[b],sizeof(long long int)*(r[b][0]+1));
r[b][r[b][0]]=a;
}
}
maxget=(long long int*)calloc(n,sizeof(long long int));
long long int * pai=(long long int*)calloc(n,sizeof(long long int));
for(long long int i=0;i<n;i++)
{
pai[i]=i;
}
qsort(pai,n,sizeof(long long int),cmp1);
for(long long int i=0;i<n;i++)
{
maxget[i]=p[i]-p[pai[0]];
}
long long int * pai2=(long long int*)calloc(n,sizeof(long long int));
for(long long int i=0;i<n;i++)
{
pai2[i]=i;
}
qsort(pai2,n,sizeof(long long int),cmp2);
long long int * dui=(long long int*)calloc(n,sizeof(long long int));
long long int head=0;
long long int tail=1;
bool* flag=(bool*)calloc(n,sizeof(bool));
dui[0]=n-1;
while(head!=tail)
{
for(long long int i=1;i<=r[dui[head]][0];i++)
{
if(!flag[r[dui[head]][i]])
{
dui[tail]=r[dui[head]][i];
tail++;
if(tail==n)tail=0;
flag[r[dui[head]][i]]=1;
}
}
head++;
if(head==n)head=0;
}
bool* found=(bool*)calloc(n,sizeof(bool));
bool* pflag=(bool*)calloc(n,sizeof(bool));
for(long long int i=0;i<n;i++)
{
if(flag[pai2[i]]&&reachable[pai2[i]]&&!found[pai2[i]])
{
head=0;tail=1;
dui[0]=pai2[i];
while(head!=tail)
{
for(long long int i2=1;i2<=r[dui[head]][0];i2++)
{
//printf("Searching%lld:%lld\n",i2,r[dui[head]][i2]);
if(!pflag[r[dui[head]][i2]]&&reachable[r[dui[head]][i2]])
{
dui[tail]=r[dui[head]][i2];
tail++;
if(tail==n)tail=0;
pflag[r[dui[head]][i2]]=1;
found[r[dui[head]][i2]]=1;
}
}
head++;
if(head==n)head=0;
}
for(long long int i2=0;i2<n;i2++)
{
if(pflag[pai[i2]])
{
ans=ans>p[pai2[i]]-p[pai[i2]]?ans:p[pai2[i]]-p[pai[i2]];
if(ans>=maxget[pai2[i+1]])
{
printf("%lld",ans);
return 0;
}
}
}
}
}
printf("%lld",ans);
for(long long int i=0;i<n;i++)
free(r[i]);
free(r);
free(p);
free(maxget);
free(pai);
free(dui);
free(flag);
free(pflag);
free(pai2);
free(reachable);
free(found);
//fclose(stdin);fclose(stdout);
return 0;
}