本文共 2577 字，大约阅读时间需要 8 分钟。

【题目描述】

Jzabc更是一个狂热的“驴友”，这次他想去一个诡异的地方。这个地方有n个村庄，编号为1到n。此刻他在1号村，他想到n号村。这n个村子之间有m条单向道路。通过某些道路时，可能需要花费一些钱作为“买路钱”，可是通过一些道路时不仅不用交钱反而会得到某些奖励。当然两个村庄之间可能有多条直接相连的道路，但是每条道路只能通过一次。这些村庄有这样的特性，从任何一个村庄出发，沿着任一条路径走都不会回到出发点。找到一条路径从1号到n号，他需要计算一共得到多少奖励，一共交了多少过路钱。如果奖励的钱数大于交的过路钱数，那么称这样一套路径可以得到奖励，反之吐过前者小雨后者，那么这样的路径需要花费，如果二者相等，那么Jzabc不会选择。不会出现所有的路径两者都相等，现在请你帮忙找到一条路径，使得到的奖励最小（为什么不是奖励最大？或花费最少？花费最大？），并输出最小奖励。如果找不到一条路径使其得到奖励，那么就找一条路径使其得到的花费最大（为何不是最小花费？），并输出最大花费。

【输入格式】

第一行，两个用空格隔开的正整数n和m；

以下m行，每行三个正整数x,y,w，描述一条路的信息，中间用空格隔开，其中x表示道路的起点，y表示终点；若w为负，则是通过磁条道路交的买路钱数目，若w为正，则表示这条路奖励的钱数；w不为零，且其绝对值不大于10。

【输出格式】

一个整数，若有最小奖励则输出，否则输出最大花费；

【输入样例】

3 4

1 2 2

2 3 -1

2 3 3

1 3 -1

【输出样例】

1

【输入样例】

3 4

1 2 2

2 3 -3

2 3 -5

1 3 -2

【输出样例】

3

【数据规模】

对于20%的数据，满足n<=20,   m<=200

对于50%的数据，满足n<=50,   m<=2000

对于100%的数据，满足n<=100,   m<=20000

相当于有两问

1.能否得到奖励

2.如果能 求最小奖励

   如果不能 求最大花费

第一问 可以spfa求最长路 得到length[m]

若m>0 不好处理了就。。。

关于m>0 一开始是把每一个可能的与1的距离扔到set里

然后取出这些元素 更新与这个点相连的其他点的距离

这样可以过5个点 卡时可以全过

题解说可以拓扑排序+递推

后来加上拓扑排序+set 还是超5个点 1.5s左右

后来去掉set 用bool数组存可能的距离 就不超时了= =

其实由于数据太弱 直接spfa利用正权边求最短路就可以过了 (-.-)丧心病狂

附上拓扑排序代码 其中拓扑排序是我自己yy的 也不知道对不对...

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int inf=999999999;const int lim=108;const int len=20011;struct self{int x,y,w;}s[len];int first[len],nxt[len];bool inq[lim];queue
        
         q;int longth[lim],d[lim];int m,n,a,b,c;void maxspfa(){ int a; memset(inq,0,sizeof(inq)); for(a=1;a<=m;a++)longth[a]=-inf; longth[1]=0; q.push(1); while(!q.empty()) { int u=q.front(); q.pop(); inq[u]=0; for(int e=first[u];e!=-1;e=nxt[e]) if(longth[s[e].y]
         
          d[u]+s[e].w) { d[s[e].y]=d[u]+s[e].w; if(!inq[s[e].y]) { inq[s[e].y]=1; q.push(s[e].y); } } }}int rank[lim],into[lim];void tsort(){ int i=0; q.push(1); while(!q.empty()) { int u=q.front();q.pop(); i++;rank[i]=u; for(int e=first[u];e!=-1;e=nxt[e]) { into[s[e].y]--; if(into[s[e].y]==0) q.push(s[e].y); } }}bool g[lim][len];void work(){ int a,i; for(a=1;a<=m;a++)q.push(rank[a]); g[1][10000]=1; while(!q.empty()) { int u=q.front();q.pop(); for(int e=first[u];e!=-1;e=nxt[e]) { for(i=0;i<=20000;i++) if(g[u][i])g[s[e].y][i+s[e].w]=1; } } for(i=10001;i<=20000;i++) if(g[m][i]) { printf("%d\n",i-10000); return; }} int main(){ freopen("minaw.in","r",stdin);freopen("minaw.out","w",stdout); memset(first,-1,sizeof(first));memset(nxt,-1,sizeof(nxt)); scanf("%d%d",&m,&n); for(a=1;a<=n;a++) { scanf("%d%d%d",&s[a].x,&s[a].y,&s[a].w); into[s[a].y]++; nxt[a]=first[s[a].x]; first[s[a].x]=a; } maxspfa(); if(longth[m]<=0) { minspfa(); cout<<-d[m]<
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/li412302070/article/details/12849231 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！