POJ 1364 King 差分約束 找負環

嘛,虽然是一道水题+模板题,不过还是学到了很多东西的,记录一下。

首先题目给出的不等式是小于,但是差分约束系统只能处理小于等于的情况,所以要转化成小于等于的进行处理。对于整数处理方法非常简单= =

然后是找负环的情况,其实不需要考虑图连不连通,只要一开始就把所有的点的d置成0,然后都push进队列里面就好了。

PS:这种方法同样可以用在处理多源点最短路问题上。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <string>
#include <iostream>
#include <map>
#include <cstdlib>
#include <list>
#include <set>
#include <queue>
#include <stack>

using namespace std;

typedef long long LL;
const int maxn = 105;
const int maxm = 5005;
int first[maxn],nxt[maxm],v[maxm],w[maxm];
int d[maxn],n,m,ecnt,cnt[maxn];
bool inq[maxn];

void adde(int _u,int _v,int _w) {
    v[ecnt] = _v; w[ecnt] = _w;
    nxt[ecnt] = first[_u];
    first[_u] = ecnt;
    ecnt++;
}

void solve() {
    bool bad = false;
    queue<int> q;
    for(int i = 0;i <= n;i++) {
        d[i] = 0;
        cnt[i] = 1;
        inq[i] = true;
        q.push(i);
    }
    while(!q.empty() && !bad) {
        int x = q.front(); q.pop();
        inq[x] = false;
        for(int i = first[x];i != -1;i = nxt[i]) {
            if(d[v[i]] > d[x] + w[i]) {
                if(!inq[v[i]]) {
                    inq[v[i]] = true;
                    cnt[v[i]]++;
                    q.push(v[i]);
                    if(cnt[v[i]] > n + 2) {
                        bad = true;
                        break;
                    }
                }
                d[v[i]] = d[x] + w[i];
            }
        }
    }
    if(bad) puts("successful conspiracy");
    else puts("lamentable kingdom");
}

int main() {
    while(scanf("%d",&n),n) {
        ecnt = 0;
        char sig[16];
        scanf("%d",&m);
        memset(first,-1,sizeof(first));
        memset(nxt,-1,sizeof(nxt));
        for(int i = 0;i < m;i++) {
            int a,b,c;
            scanf("%d %d %s %d",&a,&b,sig,&c);
            if(sig[0] == 'g') adde(b + a,a - 1,-c - 1);
            else adde(a - 1,b + a,c - 1);
        }
        /*
        for(int i = 1;i <= n;i++) {
            adde(i,i - 1,0);
        }
        */
        solve();
    }
    return 0;
}

  

  

更多相关文章
  • UVALive 5532 King(差分約束,spfa)
            题意:假设一个序列S有n个元素,现在有一堆约束,限制在某些连续子序列之和上,分别有符号>和<.问序列S是否存在?(看题意都看了半小时了!) 注意所给的形式是(a,b,c,d),表示:区间之和:sum[a,a+b]<d或者sum[a,a+b]>d.而c是两个字符 ...
  • 好吧终于知道什么是“高大上”的差分约束了.嗷嗷 题意: 小朋友们分糖果,某个小朋友不想另外一个小朋友分到的糖果数比自己多N块以上. 求编号为N的小朋友最多比编号为1的小朋友多分多少块糖果. 思路: 差分约束,用最短路
  • POJ 3159 Candies 解題報告(差分約束 Dijkstra+優先隊列 SPFA+棧)
        原题地址:http://poj.org/problem?id=3159     题意大概是班长发糖果,班里面有不良风气,A希望B的糖果不比自己多C个.班长要满足小朋友的需求,而且要让自己的糖果比snoopy的尽量多.            比如现在ABCD四个小朋友,B的糖果不能超过A的5个
  • 题意:一家商店在每个小时都需要至少di个人值班,现在有n个人,第j个人可以在fj开始上班,连续工作8个小时,问你要满足商店上班的条件至少需要雇佣多少个人 原题连接:http://poj.org/problem?id=
  • 差分約束(poj 1201
    这里简要记一下差分约束. 所谓差分约束,指的是由a-b>=c这种不等式组组成的约束系统.一
  • (簡單) POJ 3159 Candies,Dijkstra+差分約束。
    Description During the kindergarten days, flymouse was the monitor of his class. Occasionally the head-teacher brought the kids of flymouse’s class a
  • (簡單) POJ 3169 Layout,差分約束+SPFA。
    Description Like everyone else, cows like to
  • POJ 2983 Is the Information Reliable? 差分約束
    裸差分约束. //#pragma comment(linker, "/STACK:1024
一周排行
  • jS事件:target與currentTarget區別
    target在事件流的目标阶段:currentTarget在事件流的捕获,目标及冒泡阶段.
  • 


    		    HTML5遊戲開發進階指南(亞馬遜5星暢銷書,教你用HTML5和JavaScript構建遊戲!)
    HTML5游戏开发进阶指南(亚马逊5星畅销书,教你用HTML5和JavaScript构建游 ...
  • 一.创建RAID 1 添加3块硬盘 2 创建raid [[email protected] ~]# mdadm --create --auto=yes /dev/md10 --level=10 --raid-devices
  • 因为如果covergroup出现错误,比如typo,那么收集到的coverage很可能达到了100%,但实际上检测的coverpoint并不是你真正希望检测的.如何避免出现这种问题呢?七月第一次组会上Henry提出来 ...
  • 


    		    分析 AIX 和 Linux 效能工具nmon
    http://down.51cto.com/data/849411 作用 监控,在检查系统
  • 


    		    Juniper NetScreen5GT的基礎配置
    这篇文章只是Juniper NetScreen-5G的一些入门配置,就是能把这个东西配置起
  • 


    		    圖說DHT
    dht-diskusage.c 它包含dht中关于磁盘空间的获取与控制相关函数. 图片中箭
  • View navigation history management Authors: Yoshiroh Kamiyama The bookmarkable feature In Dojo Mobile 1.8, t ...
  • 


    		    RHEL4 ssh服務(四)ssh之linux客戶端sftp工具
    FTP(是一种文件传输协议)是一种非常广泛使用的网络协议,用来在网络中传输文件,FTP以明 ...
  • 所谓原子操作,就是该操作绝不会在执行完毕前被任何其他任务或事件打断,也就说,它的最小的执行单位,不可能有比它更小的执行单位,因此这里的原子实际是使用了物理学里的物质微粒的概念. 原子操作需要硬件的支持,因此是架构相关