codeforces 567 E President and Roads (优先队列+迪杰斯特拉+tarjan)

Posted by 111qqz on Sunday, August 16, 2015

TOC

题意是说,给定一个有向图,对于每一条边,问是否是s到t的最短路上一定会经过的边.

如果是就输出yes

如果不是,问能否通过减少这条边的权值(减少的权值就是修理费用),使得这条边成为新的最短路上的边.

对于一条边是否一定是最短路上的边,我们可以从s做一遍最短路,然后反响建边,从t再做一遍最短路.

得到两个d1,d2数组

如果一条边d1[u] + d2[v] + w(u, v) = 最短路,那这条边在最短路上的边.但是未必不能缺少.

我们还要判断这条边是否是不能缺少的.

不能缺少的意思是说,如果没有这条边,就不能构成最短路.

那么这条边一定是桥.

我们可以用tarjan算法求桥.

据说是水题,不过图论还没怎么刷,所以对我来说还是很有难度的.

只是基本懂了

下面的代码是我仿照其他人的代码写出来的….求不鄙视 ><

/*************************************************************************
    > File Name: code/cf/#314/E.cpp
    > Author: 111qqz
    > Email: rkz2013@126.com 
    > Created Time: 2015年08月17日 星期一 03时09分39秒
 ************************************************************************/
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#define y0 abc111qqz
#define y1 hust111qqz
#define yn hez111qqz
#define j1 cute111qqz
#define tm crazy111qqz
#define lr dying111qqz
using namespace std;
#define REP(i, n) for (int i=0;i<int(n);++i)  
typedef long long LL;
typedef pair<LL,LL> P;
const int maxn = 200005;
const LL mod1 = 1e9 + 7;
const LL mod2 = 99999991;
const LL inf = 1e15;
struct Nod{
    LL b,val,next,idx;
    void init(LL b,LL val,LL next,LL idx){
        this->b=b;this->val=val;this->next=next;this->idx=idx;
    }
}buf[2][maxn];
LL len[2],E[2][maxn];
LL n,m,s,t;
LL dis[2][maxn],cnt[2][2][maxn],ans1[maxn],ans2[maxn];
priority_queue<P,vector<P>,greater<P> > q;
void init()
{
    memset(E,-1,sizeof(E));
    memset(cnt,0,sizeof(cnt));
    len[0] = len[1] = 0;
}
void add_edge(LL a,LL b,LL val,LL idx)
{
    buf[0][len[0]].init(b,val,E[0][a],idx);E[0][a]=len[0]++;
    buf[1][len[1]].init(a,val,E[1][b],idx);E[1][b]=len[1]++;
}
void dij(LL s,LL o)
{
    while(!q.empty()) q.pop();
    fill(dis[o],dis[o]+maxn,inf);
    dis[o][s] = 0;cnt[o][0][s] = cnt[o][1][s] = 1;
    q.push(P(dis[o][s],s));
    LL u,v,i;
    while(!q.empty())
    {
        P p = q.top();q.pop();
        u = p.second;
        if(dis[o][u] != p.first) continue;
        for(i=E[o][u];i!=-1;i=buf[o][i].next)
    {
            v = buf[o][i].b;
            if(dis[o][v] > dis[o][u] + buf[o][i].val)
        {
                 dis[o][v] = dis[o][u] + buf[o][i].val;
                cnt[o][0][v] = cnt[o][0][u];
                cnt[o][1][v] = cnt[o][1][u];
                q.push(P(dis[o][v],v));
            }else if(dis[o][v] == dis[o][u] + buf[o][i].val){
                 cnt[o][0][v] = (cnt[o][0][v] + cnt[o][0][u]) % mod1;
                cnt[o][1][v] = (cnt[o][1][v] + cnt[o][1][u]) % mod2;
            }
        }
    }
}
int main()
{
    init();
    LL u,v,i,a,b,val;
    LL cost;
    cin>>n>>m>>s>>t;
    for(i=1;i<=m;i++){
        cin>>a>>b>>val;
        add_edge(a,b,val,i);
    }
    dij(s,0);dij(t,1);
    for(u=1;u<=n;u++)
    {
        for(i=E[0][u];i!=-1;i=buf[0][i].next){
            v = buf[0][i].b;
            if(dis[0][u]+dis[1][v]+buf[0][i].val==dis[0][t]){
                 if(cnt[0][0][u]*cnt[1][0][v]%mod1 == cnt[0][0][t]&&
                   cnt[0][1][u]*cnt[1][1][v]%mod2 == cnt[0][1][t]){
                     ans1[buf[0][i].idx] = 1;
                    continue;
                }
            }
            cost = dis[0][u]+dis[1][v]+buf[0][i].val-dis[0][t]+1;
            if(buf[0][i].val - cost > 0){
                ans1[buf[0][i].idx] = 0;
                ans2[buf[0][i].idx] = cost; 
            }else{
                ans1[buf[0][i].idx] = -1;
            }
        }
    }
    for(i=1;i<=m;i++){
        if(ans1[i] == 1) printf("YES\n");
        else if(ans1[i] == -1) printf("NO\n");
        else{
        printf("CAN %I64d\n",ans2[i]);
        }
    }
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付