不会.jpg

Problem

给定多组限制，限制分成 2 类，第一类是 ax+1=ay 第二类是 ax≤ay，求这些数最多有多少种不同的取值

Solution

建立方程后

求 SCC

然后对于每一个 SCC

求每一个 $x_i-x_j\leq y$，其中的 $y_{max}$。

至于为什么？

因为 SCC 缩点之后，点与点之间的边一定是 0.

代表着他们之间并没有特殊的约束

如果只是找全部点的 $y_{max}$，这个值可能会大上很多。

同时在一个联通分量中的约束条件互相规约，这使我们得到的 $y_{max}$ 一定是在当前可用的方程组中利用值到了最大的，因此一定合法。

我大概讲这么多感性理解下就行了，其实我也不懂。

Code

// Code by ajcxsu
// Problem: FES

#include<bits/stdc++.h>
using namespace std;

const int N=700, M=2e5+10;
int h[N], to[M], nexp[M], W[M], p=1;
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }

int dist[N];
char S[N];
int qu[N], head, tail;
inline void push(int x) { qu[tail++]=x; tail=(tail==N?0:tail); }
inline int pop() {
    int ret=qu[head++];
    return head=(head==N?0:head), ret;
}
int n, m1, m2;
int cnt[N];
void dij(int s) {
    memset(dist, 0x3f, sizeof(dist)), memset(cnt, 0, sizeof(cnt));
    int v;
    head=tail=0, dist[s]=0, push(s);
    while(head!=tail) {
        v=pop(), S[v]=0;
        cnt[v]++;
        if(cnt[v]>n) cout<<"NIE"<<endl, exit(0);
        for(int u=h[v];u;u=nexp[u])
            if(dist[to[u]]>dist[v]+W[u]) {
                dist[to[u]]=dist[v]+W[u];
                if(!S[to[u]]) push(to[u]), S[to[u]]=1;
            }
    }
}

int dfn[N], low[N], idx, sidx, stk[N], t, scc[N], nans[N];
char instk[N];
void tarjan(int x) {
    dfn[x]=low[x]=++idx, stk[++t]=x, instk[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) tarjan(to[u]), low[x]=min(low[x], low[to[u]]);
        else if(instk[to[u]]) low[x]=min(low[x], dfn[to[u]]);
    if(dfn[x]==low[x]) {
        ++sidx;
        do {
            instk[stk[t]]=false, scc[stk[t]]=sidx;
        } while(stk[t--]!=x);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m1>>m2;
    int a, b;
    for(int i=0;i<m1;i++)
        cin>>a>>b, ins(b, a, -1), ins(a, b, 1);
    for(int i=0;i<m2;i++)
        cin>>a>>b, ins(b, a, 0);
    int ans=0;
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    memset(nans, -1, sizeof(nans));
    for(int i=1;i<=n;i++) {
        dij(i);
        for(int j=1;j<=n;j++)
            if(scc[j]==scc[i]) nans[scc[i]]=max(nans[scc[i]], dist[j]);
    }
    for(int i=1;i<=sidx;i++) ans+=nans[i]+1;
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3530.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆