P3530 [POI2012]FES-Festival

标签：P3530 include POI2012 rd Festival int low now dis

传送门

---

思路

对于第一种限制，我们连接 \((x,y)=1\)，\((y,x)=-1\)

对于第二种限制，我们连接 \((x,y)=0\)

如果一个图只有第一种边，那么要么就是没有解（有环），要么答案就是点的个数

因此我们考虑将图缩成一个 DAG 来判断

如果一个强联通分量中出现负环，那么就无解

否则，最后的答案就是：每个强联通分量中的最长路之和，再加上强联通的数量

我们跑一遍 floyd，如果出现 \(dis_{i,i}<0\)，说明有负环

细节见代码

---

代码

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define LL long long
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
#define PFOR(i, x) for(int i = he[x]; i; i = r[i].nxt)
inline int rd()
{
    int sign = 1, re = 0; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
    while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
    return sign * re;
}
const int INF = 1e9;
int n, m1, m2, dis[605][605];
struct Node
{
    int to, nxt, w;
}r[200005]; int he[605];
inline void Edge_add(int u, int v, int w)
{
    static int cnt = 0;
    r[++cnt] = (Node){v, he[u], w};
    he[u] = cnt;
}
int dfn[605], low[605], dcnt;
int ty[605] ,tcnt;
std::deque<int> q;
inline void dfs(int now)
{
    dfn[now] = low[now] = ++dcnt;
    q.push_back(now);
    PFOR(i, now)
    {
        int to = r[i].to;
        if(!dfn[to])
            dfs(to),
            low[now] = std::min(low[now], low[to]);
        else if(!ty[to]) low[now] = std::min(low[now], dfn[to]);
    }
    if(dfn[now] == low[now])
    {
        ty[now] = ++tcnt;
        while(q.back() != now)
        {
            ty[q.back()] = tcnt;
            q.pop_back();
        }
        q.pop_back();
    }
}
int ans, Lest[605];
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = rd(), m1 = rd(), m2 = rd();
    FOR(i, 1, n) FOR(j, 1, n) dis[i][j] = INF;
    FOR(i, 1, n) dis[i][i] = 0;
    FOR(i, 1, m1)
    {
        int a = rd(), b = rd();
        // a + 1 == b
        Edge_add(a, b, 1), Edge_add(b, a, -1);
        dis[a][b] = 1, dis[b][a] = -1;
    }
    FOR(i, 1, m2)
    {
        int a = rd(), b = rd();
        // a <= b
        Edge_add(b, a, 0);
        if(dis[b][a] == INF) dis[b][a] = 0;
    }
    FOR(i, 1, n) if(!dfn[i]) dfs(i);
    FOR(k, 1, n) FOR(i, 1, n)
    {
        if(ty[k] != ty[i] || dis[i][k] == INF) continue;
        FOR(j, 1, n)
        {
            if(ty[i] != ty[j] || dis[k][j] == INF) continue;
            dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
        }
    }
    FOR(i, 1, n) if(dis[i][i] < 0) return puts("NIE"), 0;
    FOR(i, 1, n) FOR(j, 1, n) if(ty[i] == ty[j])
        Lest[ty[i]] = std::max(Lest[ty[i]], dis[i][j]);
    FOR(i, 1, tcnt) ans += Lest[i];
    printf("%d", ans + tcnt);
    return 0;
}

标签：P3530,include,POI2012,rd,Festival,int,low,now,dis
From： https://www.cnblogs.com/zuytong/p/16719521.html