专栏首页wym[SCOI2011]糖果 差分约束+判环

[SCOI2011]糖果 差分约束+判环

 [SCOI2011]糖果

显然差分约束,根据条件建立所有边,注意相等建立双向边。

至于为什么跑最长路,我认为是只有式子  i - 0 >= 1才能建立0到 i (i从1到n)的边,这样才能把所有点连起来。

不过这里的题解没有建立0到 i 的所有边,因为从 0 开始直接spfa 判断 n 次 会TLE,就对每个点用dfs的spfa,这种处理对于负权环较快。ans开long long 。图不联通,对每个点spfa。

 在spfa里面,每次访问过book标记,若可以变长 dis【v】< w,且正在进行 dfs ,就说明存在环。

只要不只对0spfa就不会TLE

#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
#define ll long long
struct E{
    int w,v,nxt;
};
int cnt,head[2000000],book[100005],dis[100005];
int tot[100005],in[100005];
E edge[300005];
int n,m;
void add(int u,int v,int w){
    cnt++;
    edge[cnt].v = v; edge[cnt].w = w;
    edge[cnt].nxt = head[u]; head[u] = cnt;
}
bool spfa(int S){
    book[S] = 1;	
    for(int v,w,i=head[S];i;i=edge[i].nxt){
        v = edge[i].v; w = dis[S] +edge[i].w; 
        if(dis[v]<w){
            tot[v]++;if(tot[v]>=n)return false;
            if(book[v])return false; 
            dis[v]=w;
            if(!spfa(v))return false;
        }
    }
    book[S] = 0; 
    return true;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        int c,a,b;
        scanf("%d %d %d",&c,&a,&b);
        if(c==1){
            add(a,b,0);
            add(b,a,0);
            in[b]++; in[a]++;
        }else  if(c==2){
            add(a,b,1);
            in[b]++;
        }else  if(c==3){
            add(b,a,0);
            in[a]++;
        }else if(c==4){
            add(b,a,1);
            in[a]++;
        }else{
            add(a,b,0);
            in[b]++;
        }
        if(c%2==0 && a==b)    {
            printf("-1\n");
            return 0;
        }
    }
    //for(int i=1;i<=n;i++) add(i,0,1);
    for(int i=1;i<=n;i++)dis[i]=1;
    int f=0;
    for(int i=0;i<=n;i++){
            if(!spfa(i)){
                f = 1;break;
            }
    }
     
    if(f)printf("-1\n");
    else {
        ll sum=0; for(int i=0;i<=n;i++)sum+=dis[i];
        printf("%lld\n",sum);
    }
    return 0;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online(四题签到)

    用户2965768
  • HDU 6342

    用户2965768
  • Educational Codeforces Round 44 (Rated for Div. 2) B. Switches and Lamps

    You are given n switches and m lamps. The i-th switch turns on some subset of th...

    用户2965768
  • 你写的代码就是你的犯罪证据

    过程中,我发现一个特别有意思的东西,我重构了很多的 if 语句。从这些 if 语句里,大抵是映射出了业务的变化。于是,我便想写一篇文章来记录一下相关的心得。

    Phodal
  • iOS:JSON转OC属性小工具 原

          在iOS开发中,只要有网络模块,就需要数据模型的编写。在进行数据模型的解析和映射时,JSONModel是一个非常常用且优秀的第三方框架,之前有有过博...

    珲少
  • Java基础知识-if条件语句的使用介绍

    这章节给大家介绍一下Java中经常使用的if条件语句是如何使用的和在项目开发过程中if语句的注意事项。 1.首先就是最基础的写法if(boolean类型) 和i...

    用户1149268
  • R语言写2048游戏

           2048 是一款益智游戏,只需要用方向键让两两相同的数字碰撞就会诞生一个翻倍的数字,初始数字由 2 或者 4 构成,直到游戏界面全部被填满,游戏结...

    用户1680321
  • 有趣!10分钟用Python编写一个贪吃蛇小游戏

    贪吃蛇,大家应该都玩过。当初第一次接触贪吃蛇的时候 ,还是能砸核桃的诺基亚上,当时玩的不亦乐乎。今天,我们用Python编程一个贪吃蛇游戏,下面我们先看看效果:...

    叫我龙总
  • Python基础05 缩进和选择

    缩进 Python最具特色的是用缩进来标明成块的代码。我下面以if选择结构来举例。if后面跟随条件,如果条件成立,则执行归属于if的一个代码块。 先看C语言的表...

    Vamei
  • CountDownLatch的原理

    上次大概说了CountDownLatch的使用,今天说下实现的原理,CountDownLatch的使用效果和Join差不多,实现起来也比较简单。

    付威

扫码关注云+社区

领取腾讯云代金券