Luogu1993小K的农场

r囧r小猫 2021-12-24 19:17 229阅读 0赞

#include<cstdio>
    #include<queue>
    #include<cstring>
    using namespace std;
    
    int n,m,cnt,head[100005],vis[100005],dis[100005];
    
    struct edge{
        int v,w,next;
    }e[1000005];
    
    inline void add(int u,int v,int w){
        e[++cnt].v=v;
        e[cnt].w=w;
        e[cnt].next=head[u];
        head[u]=cnt;
    }
    
    inline bool spfa(int u){
        vis[u]=1;
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].v;
            if(dis[v]<dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(vis[v])return 0;
                if(!spfa(v))return 0;
            }
        }
        vis[u]=0;
        return 1;
    }
    
    int main(){
        memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int flag,a,b,c;
            scanf("%d",&flag);
            if(flag==1){
                scanf("%d%d%d",&a,&b,&c);
                add(a,b,-c);
            }
            else if(flag==2){
                scanf("%d%d%d",&a,&b,&c);
                add(b,a,c);
            }
            else{
                scanf("%d%d",&a,&b);
                add(a,b,0);add(b,a,0);
            }
        }
        for(int i=1;i<=n;i++){
            add(0,i,0);
            dis[i]=-2147483647;
        }
        if(spfa(0))printf("Yes\n");
        else printf("No\n");
    }

转载于:https://www.cnblogs.com/Y15BeTa/p/10992728.html

发表评论取消回复

表情：

评论列表（有 0 条评论，229人围观）

还没有评论，来说两句吧...

相关阅读

相关 csam(csa模式农场)

什么是超声显微镜超声显微镜是利用超声作为工具来显示物体的微小结构的新型显微工具。人眼见不到声波，但我们可以利用声音的各种效应来间接地看到它。声波与物体相互作用，声波里便

朱雀/ 2023年09月26日 13:08/ 0 赞/ 6 阅读

相关渲染农场

渲染农场（Renderfarm）其实是一种通俗的叫法，实际上我们应该叫他“分布式并行 [集群计算][Link 1]系统”，这是一种利用现成的CPU、 [以太网][Link 2]

灰太狼/ 2022年08月20日 05:10/ 0 赞/ 222 阅读

相关 ACM John的农场（最小生成树） C++实现

John的农场 Description John是一个农场主，他有几个牧场，为了好好照顾他的牛，他必须在几个牧场之间来回，可糟糕的天气往往使得道路非常泥泞，为此Joh

╰+哭是因爲堅強的太久メ/ 2022年06月18日 10:56/ 0 赞/ 144 阅读

相关逃离农场--动态规划

题目：牛牛在农场饲养了n只奶牛,依次编号为0到n-1, 牛牛的好朋友羊羊帮牛牛照看着农场.有一天羊羊看到农场中逃走了k只奶牛,但是他只会告诉牛牛逃走的k只奶牛的编号之和能被

偏执的太偏执、/ 2022年06月13日 09:07/ 0 赞/ 164 阅读

相关 ACM John的农场（最小生成树） C++实现

John的农场 Description John是一个农场主，他有几个牧场，为了好好照顾他的牛，他必须在几个牧场之间来回，可糟糕的天气往往使得道路非常泥泞，为此Joh

末蓝、/ 2022年05月15日 13:14/ 0 赞/ 184 阅读

相关 ACM John的农场（最小生成树） C++实现

John的农场 Description John是一个农场主，他有几个牧场，为了好好照顾他的牛，他必须在几个牧场之间来回，可糟糕的天气往往使得道路非常泥泞，为此Joh

╰+攻爆jí腚メ/ 2022年05月15日 13:13/ 0 赞/ 168 阅读

相关【最大流】【CODEVS】1993 草地排水

【算法】网络流-最大流(dinic) 【题解】http://www.cnblogs.com/onioncyc/p/6496532.html ![ContractedBloc

不念不忘少年蓝@/ 2022年01月12日 01:19/ 0 赞/ 158 阅读

相关 Luogu1993小K的农场

include<cstdio> include<queue> include<cstring> using namespace std;

r囧r小猫/ 2021年12月24日 19:17/ 0 赞/ 230 阅读

相关 Luogu 1164 小A点菜

终于在任重而道不远的形势的逼迫下，拾起了自己畏惧的动态规划。于是开始从最简单的题做起。题目链接：[https://www.luogu.org/problemnew/sh

电玩女神/ 2021年12月10日 05:47/ 0 赞/ 219 阅读

相关有个农场

基于智慧农业的农产品销售创新的有个农场摘要：提出在大数据逐渐普及的时代基础上，将大数据与实体农场相结合。采用标准电话线、网络、移动宽带及ISDN 数据线或直接连接，可

谁借莪１个温暖的怀抱￠/ 2021年11月05日 23:04/ 0 赞/ 282 阅读