拓扑排序复习(处女座的比赛资格)

拓扑排序复习(处女座的比赛资格)

xzc 2019/4/2

拓扑排序：
  对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

拓扑排序算法：

(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。
 (来自百度百科)

算法实现：

利用拓扑排序一边排，一边dp

//自己写的伪代码，看得懂就行...
def topo(st,n): //st is the start Node, n is the numOfNode(1,2,...,n)
    queue<int> Q //init queue
    for i from 1 to n:
        dis[i] = INF  //init the nodes' distance to INF
    dis[st] = 0  //the start's distance to itself
    for i from 1 to n: //push the node whose indegree is zero
        if degree[n]==0:
            Q.push(i)
    while !Q.empty():  //like BFS
        u = Q.pop()
        for v in edge[u]: //u -> v: d 
            dis[v] = min(dis[v],dis[u]+edge[u].d)
            indegree[v]--
            if indegree[v]==0:
                Q.push(v)

算法应用：

可以用来求有向无环图(<mark>DAG</mark>)的最短路

• 时间复杂度为O(n)
• 可以处理负权的问题

(还可以求关键路径…)

一道题：

B.处女座的比赛资格 (牛客寒假算法基础集训营3)

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

  由于处女座是万人迷，所以他在中间途径的每一条线路上都会发生一些故事，也许是粉丝给他发了一个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<=10
2<=N<=100,000
1<=M<=200,000
1<=u,v<=n
0<=c<=10^9
-10^9<=cnz,jffzr<=10^9

PS:这道题卡spfa,而且如果没有花钱反而赚钱了，要按0算

我的AC代码

/* 提交时间：2019-01-28 12:20:56 语言：C++ 代码长度：1359 运行时间： 279 ms 占用内存：18080K 运行状态：答案正确 */
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
const int maxm = 2e5+10;
struct DAG
{
	int n,tot;
	int head[maxn];
	int du[maxn]; //入度 
	long long dis[maxn];
	struct Node
	{
		int to,next;
		long long d;
	}edge[maxm];
	void init(int nn)
	{
		n = nn;
		memset(head,0,sizeof(head)); //可以不要吧
		memset(du,0,sizeof(du));
		memset(dis,0x3f,sizeof(dis)); 
		tot = 0; 
	}
	void addedge(int u,int v,long long dd)
	{
		edge[++tot].to = v;
		edge[tot].d = dd;
		edge[tot].next = head[u];
		head[u] = tot;
		du[v]++; 
	}
	long long solve()
	{
		queue<int> Q;
		dis[1] = 0;
		for(int i=1;i<=n;i++) if(du[i]==0) Q.push(i);
		while(!Q.empty())
		{
			int now = Q.front();Q.pop();
			for(int i=head[now];i;i=edge[i].next)
			{
				int to = edge[i].to;
				long long d = edge[i].d;
				dis[to] = min(dis[to],dis[now]+d);
				if(--du[to]==0) Q.push(to);	
			}	
		} 
		return max(0ll,dis[n]);
	}
}A,B;
int main()
{
	int T,m,n,u,v;
	long long c,d,e;
	cin>>T;
	while(T--)
	{
		scanf("%d%d",&n,&m);
		A.init(n); B.init(n); 
		while(m--)
		{
			scanf("%d%d%lld%lld%lld",&u,&v,&c,&d,&e);
			A.addedge(u,v,c-d);
			B.addedge(u,v,c-e); 
		} 
		long long ans1 = A.solve();
		long long ans2 = B.solve();
		if(ans2==ans1) printf("oof!!!\n");
		else if(ans2>ans1) printf("cnznb!!!\n%lld\n",ans2-ans1);
		else printf("rip!!!\n%lld\n",ans1-ans2);
	}
	return 0;
}

再挂一个spfa超时的

/* 提交时间：2019-01-26 15:34:17 语言：C++ 代码长度：1525 运行时间： 1001 ms 占用内存：1248K 运行状态：运行超时 */
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
const int maxm = 1e6+10;
const long long INF = 100000000000000000;
struct Node
{
    int to,next;
    long long d;
}node[maxm],node1[maxm];
int tot,tot1,head[maxn],head1[maxn],n;
void init()
{
    memset(head1,0,sizeof(head1));
    memset(head,0,sizeof(head));
    tot = tot1 = 0;
}
void addedge(Node * node,int * head,int &tot,int u,int v,long long d)
{
    node[++tot].to = v;
    node[tot].d = d;
    node[tot].next = head[u];
    head[u] = tot;
}
long long dis[maxn];
bool vis[maxn];
long long SPFA(Node * node)
{
    for(int i=0;i<=n;i++)
        vis[i] = false,dis[i] = INF;
    queue<int> Q;
    dis[1] = 0;
    Q.push(1);
    vis[1] = true;
    while(!Q.empty())
    {
        int now = Q.front();Q.pop();
        for(int i=head[now];i;i=node[i].next)
        {
            int to = node[i].to;
            if(dis[to]==INF||dis[to]>dis[now]+node[i].d)
            {
                dis[to] = dis[now]+node[i].d;
                if(!vis[to]) vis[to]=true,Q.push(to);
            }
        }
        vis[now] = false;
    }
    return max(dis[n],0);
}
int main()
{
    int u,v,T,m;
    long long c,d,e;
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        init();
        while(m--)
        {
            scanf("%d%d%lld%lld%lld",&u,&v,&c,&d,&e);
            addedge(node,head,tot,u,v,c-d);
            addedge(node1,head1,tot1,u,v,c-e);
        }
        long long ans1 = SPFA(node);
        long long ans2 = SPFA(node1);
        long long ans = ans2-ans1;
        //cout<<ans2<<" "<<ans1<<endl;
        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;
}