icontofig | 发布于 2019-08-18 19:27:53 | 阅读量 259 | 差分约束系统
发布于 2019-08-18 19:27:53 | 差分约束系统

题目大意

两个人从家里出发,Panda比Sheep晚走x分钟,在地铁上两人保持m次通信,每次通信Panda在a和b之间,Sheep在c和d之间。到终点后,求问每两站之间所需要的时间是多少,如果无法计算输出IMPOSSIBLE

题解

我们可以在草稿纸上画画图,把两人的位置之间连线,标记上表示这一段的时间为x。

然后我们可以看到两者区间两端点的关系,进行分类讨论:

如果a = b:

1.c = d 那么就是c - a = x,也就是c - a <= x, c - a >= x,也即 c - a  <= x,a - c <= -x;

2.c ≠ d 则c - a < x,d - a > x,也即c - a  <= x-1,a - d <= -x-1;

如果a ≠ b:

1. c = d 那么就是 c - a > x,c - b < x,也即a - c <= -x-1,c - b <= x-1;

2. c ≠ d 那么就是c - b < x,d - a > x,也即c - b <= x - 1,a - d <= -x-1;

根据这些关系很容易就能想到此题是一个差分约束系统。只需要用SPFA求解就行了。

IMPOSSIBLE的情况就是出现负环或者正环(看自己怎么定义边了,要注意SPFA中的更新的不等号方向要和建边一致,不然会WA)。

非IMPOSSIBLE的情况,两站之间的距离就是dis[i] - dis[i-1](标程里面写的是最长路,所以也就是非正环情况)。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 2005;
typedef long long ll;
struct edge{
    int to,next;
    ll dis;
}e[maxn<<5];
int cnt = 0;
int t;
int h[maxn];
int a,b,c,d;
int n,m;
ll x;
void add(int u,int v,int d){
    e[cnt].to = v;e[cnt].next = h[u];e[cnt].dis = d;
    h[u] = cnt++;
    return;
}
ll ds[maxn];
int vis[maxn],tot[maxn];
int l,r;
int SPFA(int s,int t){
    for(int i = 1;i <= n;++i){
        vis[i] = 0;
        ds[i] = 0;
        tot[i] = 0;
    }
    queue<int>q;
    ds[s] = 0;
    q.push(s);
    tot[s] = 1;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        vis[now] = 0;
        for(int i = h[now];i != -1;i = e[i].next){
            if(ds[now] + e[i].dis > ds[e[i].to]){
                ds[e[i].to] = ds[now] + e[i].dis;
                if(!vis[e[i].to]){
                    vis[e[i].to] = 1;
                    tot[e[i].to]++;
                    if(tot[e[i].to] >= n)return 0;
                    q.push(e[i].to);
                }
            }
        }
    }
    return 1;
}
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num << 3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
int main(){
    t = get_num();
    for(int cas = 1;cas <= t;++cas){
        n = get_num();
        m = get_num();
        x = get_num();
        for(int i = 1;i <= n;++i){
            h[i] = -1;
        }
        cnt = 0;
        for(int i = 1;i <= m;++i){
            a = get_num();
            b = get_num();
            c = get_num();
            d = get_num();
            if(a == b){
                if(c == d){
                    add(a,d,x);
                    add(d,a,-x);
                }
                else{
                    add(a,d,x+1);
                    add(c,a,1-x);
                }
            }
            else{
                if(c == d){
                    add(a,c,x+1);
                    add(d,b,1-x);
                }
                else{
                    add(a,d,x+1);
                    add(c,b,1-x);
                }
            }
        }
        for(int i = 2;i <= n;++i){
            add(i-1,i,1);
        }
        int flag = SPFA(1,n);
        printf("Case #%d:",cas);
        if(!flag)
            printf(" IMPOSSIBLE\n");
        else{
            for(int i = 2;i <= n;++i){
                printf(" %lld",ds[i] - ds[i-1]);
            }
            printf("\n");
        }
    }
    return 0;
}



内容更新于: 2019-08-18 19:27:53
链接地址: http://blog.leanote.com/post/icontofig/8eca65a797d9

上一篇: Codeforces Round 580div2 1025B Shortest Cycle 思维题

下一篇: 2019 Multi-University Training Contest 8 1008 Andy and Maze 状压DP + color coding

259 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航