BZOJ 2788 Festival 詳解（差分限制 tarjan floyd）

2788: [Poi2012]Festival

Time Limit: 30 Sec Memory Limit: 64 MB

Description

有n個正整數X1,X2,…,Xn，再給出m1+m2個限制條件，限制分為兩類：

1. 給出a,b (1<=a,b<=n)，要求滿足Xa + 1 = Xb

2. 給出c,d (1<=c,d<=n)，要求滿足Xc <= Xd

在滿足所有限制的條件下，求集合{Xi}大小的最大值。

Input

第一行三個正整數n, m1, m2 (2<=n<=600, 1<=m1+m2<=100,000)。

接下來m1行每行兩個正整數a,b (1<=a,b<=n)，表示第一類限制。

接下來m2行每行兩個正整數c,d (1<=c,d<=n)，表示第二類限制。

Output

一個正整數，表示集合{Xi}大小的最大值。

如果無解輸出NIE。

Sample Input

4 2 2

1 2

3 4

1 4

3 1

Sample Output

3

HINT

|X3=1, X1=X4=2, X2=3

這樣答案為3。容易發現沒有更大的方案。

思路：

跑多個式子的可行解考慮差分限制。

把Xa+1=Xb轉化為Xa<=Xb-1，Xb<=Xa+1,建a到b邊權為1的邊，b到a權值為-1的邊。我們可以把它當做雙向邊（1類邊）。

把Xc<=Xd轉化為 Xc-Xd<=0,建一條d到c邊權為0的有向邊。我們可以把它當做單向邊（2類邊）。

建圖之後圖中可能會有強聯通分量。

那麼連接配接強聯通分量的邊不可能是1類邊（不然就聯通起來了）是以隻可能是A<=B（2類邊）。

那麼隻要保證A點所在強聯通分量中的最大值小于B點所在強聯通分量中的最小值，就可以使不同權值最多。（沒有重複）

那麼我們隻需要對每個強聯通求出答案再累加起來就好了。

如果強聯通分量中有2類邊，那麼它們一定是在一個環中的（不然就不是強連通了），由于它們是互相<=的（循環小于等于），那麼隻有當它們都是同一個權值是才有可能。

由于圖中隻有-1，0，1三種邊，是以每個強聯通分量中，權值種類最多就是最長路的絕對值的最大值+1。（最長路的兩端一定是這個強連通分量裡面的最大及最小值，因為如果不是的話，每兩個點之間又是可以互相到達的，那麼這就一定不是一條最長路。）

是以上面說的環的最長路跑出來是0。也是滿足條件的，不會影響我們所求的答案（最長路上的邊一定是1類邊）。

因為點數n<=600那麼floyd是可以的。（因為要限制隻在一個強連通分量裡面跑，是以選用枚舉方式的floyd應該是很好寫的）

怎麼判無解呢？就是當出現正權環的時候。我們要求的是最長路，如果出現了正權環，那麼我們就可以一直跑這個環，我們的ans就可以無限變大，而這肯定是不合法的（和求最短路判負環一樣）

如何判斷正權環呢?

隻需要初始化把dis[i][i]=0，跑完floyd後看是否還是0即可。

#include <cmath>
#include <stack>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1000
#define M 400010
#define INF 0x3f3f3f3f
using namespace std;

int n, m1, m2, idc, idx, top, cnt;
int head[N], dfn[N], low[N], ins[N], vis[N], place[N];
int dis[N][N];
stack <int> state;

struct Edge{
    int from, to, next;
}ed[M];

void init(){
    memset(head, , sizeof(head));
    idc = ;
}

void adde(int u, int v){
    ed[++idc].from = u;
    ed[idc].to = v;
    ed[idc].next = head[u];
    head[u] = idc;
}

void tarjan(int u){
    dfn[u] = low[u] = ++idx;
    vis[u] = ins[u] = ;
    state.push(u);
    for(int i=head[u]; i; i=ed[i].next){
        int v = ed[i].to;
        if( !vis[v] ){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if( ins[v] ){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]){
        cnt++; int t=-;
        while(t != u){
            t = state.top();
            place[t] = cnt;//記錄強連通分量 
            ins[t] = ;
            state.pop();
        }
    }
}

int main(){
    init();
    scanf("%d%d%d", &n, &m1, &m2);
    for(int i=; i<=n; i++)
        for(int j=; j<=n; j++)
            dis[i][j] = -INF;
    for(int i=; i<=n; i++) dis[i][i] = ; 
    for(int i=; i<=m1; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        adde(a, b); adde(b, a);
        dis[a][b] = max(dis[a][b], );
        dis[b][a] = max(dis[b][a], -);
        //a+1=b -> a+1<=b&&a+1>=b -> a<=b-1&&b<=a+1 -> ab.w=1&&ba.w=-1 
        //有沖突情況時，不覆寫，取max讓dis[i][i]不為0 
        //eg:a=b+1&&b=a+1 -> dis[a][b]=dis[b][a]=1 -> dis[a][a]=dis[b][b]=2(更新後)
    }
    for(int i=; i<=m2; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        adde(a, b);
        dis[a][b] = max(dis[a][b], );//b>=a -> a<=b+0
    }
    for(int i=; i<=n; i++){
        if( !dfn[i] ) tarjan(i);
    }
    int ans = ;
    for(int cc=; cc<=cnt; cc++){//枚舉每個強連通分量 
        int ret = ;
        for(int k=; k<=n; k++){//FLOYD 
            if(place[k] != cc) continue;
            for(int i=; i<=n; i++){
                if(place[i] != cc || dis[i][k] == -INF) continue;
                for(int j=; j<=n; j++){//枚舉任意兩個點 
                    if(place[j] != cc || dis[k][j] == -INF) continue;
                    dis[i][j] = max(dis[i][j], dis[i][k] + dis[k][j]);//更新最長路 
                }
            }
        }
        for(int i=; i<=n; i++){
            if(place[i] != cc) continue;
            for(int j=; j<=n; j++){
                if(place[j] != cc) continue;
                ret = max(ret, abs(dis[i][j]));//記錄最長路的max 
            }
        }
        ans += ret + ;//完成一個強連通分量的計算 
    }
    for(int i=; i<=n; i++)
        if(dis[i][i] != ){
            puts("NIE");
            return ;
        }//有正權環，無解 
    printf("%d\n", ans);
    return ;
}