图论入门（2

A ：TT的魔法猫

题目

众所周知，TT 有一只魔法猫。

这一天，TT 正在专心致志地玩《猫和老鼠》游戏，然而比赛还没开始，聪明的魔法猫便告诉了 TT 比赛的最终结果。TT 非常诧异，不仅诧异于他的小猫咪居然会说话，更诧异于这可爱的小不点为何有如此魔力？

魔法猫告诉 TT，它其实拥有一张游戏胜负表，上面有 N 个人以及 M 个胜负关系，每个胜负关系为 A B，表示 A 能胜过 B，且胜负关系具有传递性。即 A 胜过 B，B 胜过 C，则 A 也能胜过 C。

TT 不相信他的小猫咪什么比赛都能预测，因此他想知道有多少对选手的胜负无法预先得知，你能帮帮他吗？

输入

第一行给出数据组数。

每组数据第一行给出 N 和 M（N , M <= 500）。

接下来 M 行，每行给出 A B，表示 A 可以胜过 B

输出

对于每一组数据，判断有多少场比赛的胜负不能预先得知。注意 (a, b) 与 (b, a) 等价，即每一个二元组只被计算一次。

输入样例：

3
3 3
1 2
1 3
2 3
3 2
1 2
2 3
4 2
1 2
3 4

输出样例：

0
0
4

这题简单来说也是一个最短路的变化问题，把Floyd的条件改成dis[i][j]=dis[i][k]&dis[k][j]，但是直接上Floyd会超时。需要各种玄学剪枝。

#include<iostream>
using namespace std;
int ds[600][600];
const int ww=1000000;
void floyd(int n)
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            if(i==k) continue;//发现无效直接过滤
            if(!ds[i][k]) continue;//及时终止
            for(int j=1;j<=n;j++)
            {
                if(i==j) continue;//无效直接过滤
                //ds[i][j]=min(ds[i][j],ds[i][k]+ds[k][j]);
                if(ds[i][k]&&ds[k][j]) ds[i][j]=1;
            }
        }
    }
}
int main()
{
    int n1;
    cin>>n1;
    while(n1--)
    {
        int n,m;
        cin>>n>>m;
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                /*if(i==j)
                {
                    ds[i][j]=0;
                }
                else ds[i][j]=ww;*/
                ds[i][j]=0;
            }
        }
        int k,l;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&k,&l);
            ds[k][l]=1;
        }
        floyd(n);
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                if(i==j) continue;
                //if(ds[i][j]==0) sum++;
                if(ds[i][j]||ds[j][i]) continue;
                sum++;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

B ：TT的旅行日记

题目

众所周知，TT 有一只魔法猫。

今天他在 B 站上开启了一次旅行直播，记录他与魔法猫在喵星旅游时的奇遇。 TT 从家里出发，准备乘坐猫猫快线前往喵星机场。猫猫快线分为经济线和商业线两种，它们的速度与价钱都不同。当然啦，商业线要比经济线贵，TT 平常只能坐经济线，但是今天 TT 的魔法猫变出了一张商业线车票，可以坐一站商业线。假设 TT 换乘的时间忽略不计，请你帮 TT 找到一条去喵星机场最快的线路，不然就要误机了！

输入

输入包含多组数据。每组数据第一行为 3 个整数 N, S 和 E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ 100)，即猫猫快线中的车站总数，起点和终点（即喵星机场所在站）编号。

下一行包含一个整数 M (1 ≤ M ≤ 1000)，即经济线的路段条数。

接下来有 M 行，每行 3 个整数 X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100)，表示 TT 可以乘坐经济线在车站 X 和车站 Y 之间往返，其中单程需要 Z 分钟。

下一行为商业线的路段条数 K (1 ≤ K ≤ 1000)。

接下来 K 行是商业线路段的描述，格式同经济线。

所有路段都是双向的，但有可能必须使用商业车票才能到达机场。保证最优解唯一。

输出

对于每组数据，输出3行。第一行按访问顺序给出 TT 经过的各个车站（包括起点和终点），第二行是 TT 换乘商业线的车站编号（如果没有使用商业线车票，输出"Ticket Not Used"，不含引号），第三行是 TT 前往喵星机场花费的总时间。

本题不忽略多余的空格和制表符，且每一组答案间要输出一个换行

输入样例：

4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3

输出样例：

1 2 4
2
5
假如不考虑商业线的情况，这就是一个单源最短路+路径回溯的题目，直接用dijsktra算法解决，但题目偏偏又加上了商业线，我们就需要对每条商业线进行遍历了orz，看看用这条商业线会不会好一点（比较商业线车票只有一张，直接遍历就好。

当然路径记忆的时候会出现问题。因为假如不用商业线不通路，这条路径只靠单向的dij是解不出来的。所以我们开始就要从起点终点两个方向跑dij，记录路径和最短路。
dij板子：

void dijkstra(int s,int *dis,int n,int *path)   //pair 从小到大 
{
    while(q.size()) q.pop();
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)   {
        dis[i]=-inf;
        path[i]=-1;
    }
    dis[s]=0;
    path[s]=-1; 
    q.push(make_pair(0,s));
    while(q.size()){
        int x=q.top().second;
        q.pop();
        if(vis[x])  continue;
        vis[x]=1;
        for(int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].v,w=edge[i].w;
            if(dis[y]<dis[x]+w){
                dis[y]=dis[x]+w;
                path[y]=x;//路径回溯
                q.push(make_pair(dis[y],y));
            }
        }   
    } 
     
}

路径回溯就是加一个path数组，递归找路径

#include<iostream>
#include<queue>
#include<string.h>
#include<cstdio>
#include<utility>
using namespace std;
const int max1=1e9;
int n;
int head[1001]/*,vis1[1001]*/,vis[1001],dis1[1001],dis2[1001];
int father1[1001],father2[1001];
int min1(int a,int b)
{
    if(a>b) return b;
    else return a;
}
struct edge
{
    int to;
    int next;
    int w;
};
int tot;
edge a[1000000];
void add(int x,int y,int w)
{
    a[++tot].to=y;
    a[tot].next=head[x];
    a[tot].w=w;
    head[x]=tot; 
}
priority_queue<pair<int,int> > q;
void djisktra(int s/*,int *vis*/,int *dis,int *father)
{
    while(!q.empty()) q.pop();
        
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        dis[i]=max1;
    }
    dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
    //  cout<<"hello"<<endl;
        int t=q.top().second; q.pop();
        if(vis[t]) continue;
        vis[t]=1;
        for(int i=head[t];i;i=a[i].next)
        {
            int y=a[i].to,w=a[i].w;
            if(!vis[y]&&dis[y]>dis[t]+w)
            {
                father[y]=t;
                dis[y]=dis[t]+w;
                q.push(make_pair(-dis[y],y));
            //  cout<<"hello"<<endl;
            }
        }
    }
}
int kl[1000001];
void display1(int k,int l,int *father)
{
    //cout<<"helo"<<k<<endl;
    int tlp=0;
    while(k!=l)
    {
        kl[tlp]=k;
        k=father[k];
        tlp++;
    }
    kl[tlp]=l;
    for(int pp=tlp;pp>=0;pp--)
    {
        printf("%d",kl[pp]);
        if(pp!=0) printf(" ");
    }
//  printf("\n");
//  cout<<k<<" "<<l<<"hello"<<endl;
/*  if(k==l)
    {
        cout<<l<<" ";
    }
    else
    {
        display1(father[k],l,father);
        cout<<k<<" ";
    }
    return;*/
}
void display2(int k,int l,int *father)
{
    if(k==l)
    {
        cout<<l;
        return;
    }
    else
    {
        cout<<k<<" ";
        display2(father[k],l,father);
        
    }
    return;
}
int main()
{
    int s,e;
    //cin>>n>>s>>e;
    bool kl=0;
    while(cin>>n)
    {
        if(kl)
        {
            cout<<endl;
        }
        else kl=1;
        scanf("%d%d",&s,&e);
        int m;
        scanf("%d",&m);
        int x,y,z;
        memset(head,0,sizeof(head));
        for(int i=0;i<=n;i++)
        {
            father1[i]=i;
            father2[i]=i;
        }
        tot=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
            //head[i]=0;
        }
    //  head[m]=0;
        djisktra(s,dis1,/*vis1,*/father1);
        djisktra(e,dis2,/*vis2,*/father2);
/*      for(int tl=0;tl<10;tl++)
        {
            cout<<"1"<<dis1[tl]<<" "<<endl;
            cout<<"2"<<dis2[tl]<<" "<<endl;
        }*/
        int min=max1;
        int k;scanf("%d",&k);
        int begin,last,ww,lu1=5000000,lu;
        for(int i=0;i<k;i++)
        {
        //  cout<<"pl"<<endl;
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            int begin1,last1;
        //  cout<<"gugugu"<<dis1[u]<<" "<<dis2[v]<<endl;
        //  cout<<"gugugu1"<<dis1[v]<<" "<<dis2[u]<<endl;
            if(dis1[u]+dis2[v]+w>dis1[v]+dis2[u]+w)
            {
        //      cout<<"1"<<endl;
                begin1=v;
                last1=u;
                lu=dis1[v]+dis2[u]+w;
            }
            else
            {
        //      cout<<"2"<<endl;
                begin1=u;
                last1=v;
                lu=dis1[u]+dis2[v]+w;
        //      cout<<"ko"<<lu<<endl;
            }
            if(lu<lu1)
            {
        //      cout<<" ll"<<lu1<<endl; 
                lu1=lu;
                begin=begin1;last=last1;
            }
        //  int dl=min1(dis1[u]+dis2[v]+w,dis1[v]+dis2[u]+w);
            //cout<<" "<<dl<<endl;
        //  min=min1(min,dl);
        }
        if(lu1<dis1[e])
        {
            display1(begin,s,father1);
            cout<<" ";
            display2(last,e,father2);
            //
        //  cout<<begin<<" "<<last<<endl;
            cout<<endl; 
            cout<<begin<<endl;
            cout<<lu1<<endl;
        }
        else
        {
            display1(e,s,father1);
            cout<<endl; 
            cout<<"Ticket Not Used"<<endl;
            cout<<dis1[e]<<endl;
        }
    //  display(e,s);
    //cout<<dis1[e]<<endl; 
        //min=min1(min,dis1[e]);
        //cout<<min<<endl;
        //cout<<endl;
    }
    return 0;
}

注意两次路径回溯输出方向

C ：TT的美梦

题目

这一晚，TT 做了个美梦！

在梦中，TT 的愿望成真了，他成为了喵星的统领！喵星上有 N 个商业城市，编号 1 ～ N，其中 1 号城市是 TT 所在的城市，即首都。

喵星上共有 M 条有向道路供商业城市相互往来。但是随着喵星商业的日渐繁荣，有些道路变得非常拥挤。正在 TT 为之苦恼之时，他的魔法小猫咪提出了一个解决方案！TT 欣然接受并针对该方案颁布了一项新的政策。

具体政策如下：对每一个商业城市标记一个正整数，表示其繁荣程度，当每一只喵沿道路从一个商业城市走到另一个商业城市时，TT 都会收取它们（目的地繁荣程度 - 出发地繁荣程度）^ 3 的税。

TT 打算测试一下这项政策是否合理，因此他想知道从首都出发，走到其他城市至少要交多少的税，如果总金额小于 3 或者无法到达请悄咪咪地打出 ‘?’。

输入

第一行输入 T，表明共有 T 组数据。（1 <= T <= 50）

对于每一组数据，第一行输入 N，表示点的个数。（1 <= N <= 200）

第二行输入 N 个整数，表示 1 ～ N 点的权值 a[i]。（0 <= a[i] <= 20）

第三行输入 M，表示有向道路的条数。（0 <= M <= 100000）

接下来 M 行，每行有两个整数 A B，表示存在一条 A 到 B 的有向道路。

接下来给出一个整数 Q，表示询问个数。（0 <= Q <= 100000）

每一次询问给出一个 P，表示求 1 号点到 P 号点的最少税费。

输出

每个询问输出一行，如果不可达或税费小于 3 则输出 ‘?’。

输入样例：

2
5
6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5
10
1 2 4 4 5 6 7 8 9 10
10
1 2
2 3
3 1
1 4
4 5
5 6
6 7
7 8
8 9
9 10
2
3 10

输出样例：

Case 1:
3
4
Case 2:
?
?
其实这也是单源最短路径，但是可能会出现负环（因为边权是两个点差的3次方），所以改用spfa算法解决负环的问题。spfa 选取松弛成功的边加入队列，一条边可能被弹出多次，但是由于只有n 个点，当弹出次数大于n 次的时候就出现了负环。据此来判断负环。
当出现一个负环点的时候将这点做一次dfs ,标记， 加入队列的条件改为队列中没有且没有在负环上。

#include<iostream>
#include<queue>
#include<string.h>
#include<utility>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int max1=1e8*5;
int m;
int head[1000000],dis[1000000],cnt[10001];
bool vis[1001],bl[10001];
int al[1000000];
int min1(int a,int b)
{
    if(a>b) return b;
    else return a;
}
struct edge
{
    int to;
    int next;
    int w;
};
int tot;
edge a[1000000];
void add(int x,int y,int w)
{
    a[++tot].to=y;
    a[tot].next=head[x];
    a[tot].w=w;
    head[x]=tot; 
}
queue<int> q;
void biaoji(int t)
{
    vis[t]=true;
    for(int i=head[t];i;i=a[i].next)
    {
        int y=a[i].to;
        if(vis[y]) continue;
        biaoji(y);
    }
}
void SPFA()
{
    while(!q.empty()) q.pop();
        
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    memset(bl,0,sizeof(bl));
    for(int i=0;i<=m;i++)
    {
        //dis1[i]=max1;
        dis[i]=max1;
    }
    dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
    //  cout<<"hello"<<endl;
        int t=q.front(); 
        q.pop();
        bl[t]=0;
        for(int i=head[t];i;i=a[i].next)
        {
            int y=a[i].to,w=a[i].w;
            if(dis[y]>dis[t]+w&&!vis[y])
            {
                dis[y]=dis[t]+w;
                cnt[y]++;
                if(cnt[y]>m)
                {
                    biaoji(y);
                    continue;
                }
                if(!bl[y]) q.push(y),bl[y]=1;
            //  cout<<"hello"<<endl;
            }
        }
    }
}
int main()
{
    int t;cin>>t;
    for(int qt=0;qt<t;qt++)
    {
    
        cin>>m;
        tot=0;
        memset(head,0,sizeof(head));
        for(int mt=1;mt<=m;mt++)
        {
            cin>>al[mt];
        }
        int n;
        cin>>n;
        for(int nt=0;nt<n;nt++)
        {
            int x,y;cin>>x>>y;
            add(x,y,pow((al[y]-al[x]),3));
        }
        SPFA();
        int l;cin>>l;
        cout<<"Case "<<(qt+1)<<":"<<endl;
        for(int lt=0;lt<l;lt++)
        {
            int x;
            cin>>x;
            if(dis[x]<3||vis[x]||dis[x]==max1)
            {
                cout<<"?"<<endl;
            }
            else
            {
                cout<<dis[x]<<endl;
            }
        }
    }
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 217,734评论 6赞 505
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,931评论 3赞 394
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 164,133评论 0赞 354
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,532评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,585评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,462评论 1赞 302
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,262评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,153评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,587评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,792评论 3赞 336
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,919评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,635评论 5赞 345
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,237评论 3赞 329
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,855评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,983评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,048评论 3赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,864评论 2赞 354

推荐阅读更多精彩内容

  • 2018-06-14
    在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,342评论 0赞 2
  • 2020-04-05 SDU程序设计 第七周
    TT 的魔法猫 现有数据大小是N的数据，然后他们之间进行M场比赛，如果A胜过B，B胜过C，那么A胜过C，也就是说有...
    _fallen阅读 304评论 0赞 0
  • 声律启蒙
    sì 支zhī茶chá 对duì 酒jiǔ，赋fù 对duì 诗shī，燕yàn子zi 对duì 莺yīng 儿é...
    每个人的孟母堂阅读 1,209评论 0赞 6
  • 语文生字表
    一年级语文上册生字表 生字表一（共400字） 啊(ā)爱(ài)安(ān)岸(àn)爸(bà)八(bā)巴(bā)...
    meychang阅读 2,796评论 0赞 6
  • 天若
    天若 乱舞途中喧闹人群添落寞 偷眼忘情举手投足似若狂 无心倾诉留恋迷茫声色所 曲已了断人未散尽虚空藏
    字母Reddish阅读 258评论 0赞 1