您的位置: 首页  >  文章  >  C.处女座的比赛资格 拓扑排序实现有向无环最短路

C.处女座的比赛资格 拓扑排序实现有向无环最短路

分类: 文章 • 2025-01-22 19:38:16

链接：https://ac.nowcoder.com/acm/contest/329/B
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

C.处女座的比赛资格 拓扑排序实现有向无环最短路C.处女座的比赛资格 拓扑排序实现有向无环最短路

处女座想出去比赛，但是又不知道学校能不能给到足够的经费。然而处女座是大众粉丝，有着很好的人缘，于是他找了一个在学校管经费的地方勤工俭学偷来了一份报销标准。


由于处女座是万人迷，所以他在中间途径的每一条线路上都会发生一些故事，也许是粉丝给他发了一个200元的微信红包，也许是和他的迷妹一起吃饭花了500元。


而经费负责人也实地考察了每一条路线，在每一条路上，也许是天降红包雨，也许是地生劫匪。每一条路上都有属于自己的奇遇。


而经费负责人也只能根据他的故事决定这一路批下来多少经费。他会找出从宁波到比赛地的最小花费，并以此作为标准给处女座打比赛。而处女座也会选择对他来说最小花费的路线，来节省使用。
处女座想知道，最终的经费是否够用，如果够还会剩下来多少钱。如果不够，他自己要自费掏出多少钱。（当然处女座和经费管理人都具有旅途中无限信贷额度，所有收入支出会在旅行结束后一起结算。）
 

输入描述:

输入文件第一行包含一个整数T，表示处女座要参加的比赛场数。

对于每一场比赛，第一行包含两个整数N,M，分别表示旅行中的站点数（其中宁波的编号为1，比赛地的编号为N）和线路数。

接下来M行，每一行包含5个整数u,v,c,cnz,jffzr，分别表示从u到v有一条单向的线路，这条线路的票价为c。处女座搭乘这条线路的时候，会得到cnz元（如果为负即为失去-cnz元）；经费负责人搭乘这条线路的时候，会得到jffzr元（如果为负即为失去-jffzr元）。

行程保证不会形成环，并保证一定能从宁波到达比赛地。

输出描述:

对于每一场比赛，如果经费负责人给出的经费绰绰有余，则先在一行输出"cnznb!!!"，并在下一行输出他可以余下的经费；如果处女座的经费不够用，则先在一行输出"rip!!!"，并在下一行输出他需要自费的金额；如果经费负责人给出的经费正好够处女座用，则输出一行"oof!!!"。（所有输出不含引号）

示例1

输入

复制

1
3 3
1 2 300 600 -600
2 3 100 -300 1
1 3 200 0 0

输出

复制

cnznb!!!
100

说明

处女座先走第一条路再走第二条路到达，总花费100元，经费负责人走第三条路，花费200元，处女座经费剩余100元

备注:

 

T≤10T≤10

2≤N≤1052≤N≤105

1≤M≤2⋅1051≤M≤2⋅105
1≤u,v≤N1≤u,v≤N
0≤c≤1090≤c≤109
−109≤cnz,jffzr≤109

分析:

官方题解:

有向无环图（DAG）上的最短路。
注意：负权值边的存在使得 Dijkstra 算法不适用，特殊 DAG 的性质使得 SPFA 算法无法在规定的时间限内求解出答案。 考虑到 DAG 的特殊性，按照原图节点的拓扑顺序依次递推距离即可求解。

令????????表示节点1到i的最短路，????????????????_????表示节点的先驱集合。则有：

di=min(dj+cost(j,i))其中????∈????????????????_????，其中????????????????(????,????)表示从节点j到节点i的有向边的边权。

按照节点拓扑顺序计算d即可。

时间复杂度：????(????+????)

 

其实主要的思想就是在有向无环图（DAG）,入度为0就为起点,然后我们用拓扑排序一直删点,减少度数,这样便能实现扫一遍最短路.

代码参考:https://www.cnblogs.com/2018zxy/p/10324978.html

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
const int INF = 0x3f;
int u[maxn],v[maxn],c[maxn],ai[maxn],bi[maxn];
int head[maxn],rd[maxn],tot,m,n;
ll dis[maxn];
struct Node{
    int to,nxt;
    ll data;
}edge[maxn];
void Init()
{
    tot=1;
    memset(rd,0,sizeof(rd));
    memset(head,-1,sizeof(head));
    memset(dis,INF,sizeof(dis));
}
Node tmp;
void addedge(int x,int y,ll dd)
{
    tmp.to=y;
    tmp.data=dd;
    tmp.nxt=head[x];
    edge[tot]=tmp;
    head[x]=tot++;
    rd[y]++;
} 
ll bfs()
{
    queue<int>q;
    int i,j;
    dis[1]=0;
    
    for(i=1;i<=n;i++)
    if(rd[i]==0)
		q.push(i);///入读为0的点压入
	
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(i=head[u];i!=-1;i=edge[i].nxt)
        {
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].data)
			    dis[v]=dis[u]+edge[i].data;
            rd[v]--;
            if(rd[v]==0) q.push(v);
        }
    }
    return dis[n];
}
ll MAX(ll x,ll y)
{
    return x>y?x:y;
}
int main(void)
{
    int T,i,j;
    ll ans;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++) 
        	scanf("%d%d%d%d%d",&u[i],&v[i],&c[i],&ai[i],&bi[i]);
        ans=0;
        Init();
        for(i=0;i<m;i++) 
        	addedge(u[i],v[i],(ll)(c[i]-bi[i]));
        ans+=MAX(0ll,bfs());
        
        Init();
        for(i=0;i<m;i++)   
			addedge(u[i],v[i],(ll)(c[i]-ai[i]));
        ans-=MAX(0ll,bfs());
        if(ans>0) 
            printf("cnznb!!!\n%lld\n",ans);
        else if(ans==0) 
            printf("oof!!!\n");
        else 
            printf("rip!!!\n%lld\n",-ans);
    }
    return 0;
}

 

相关推荐