[bzoj2788][Poi2012]Festival floyd 差分限制系統 tarjan

2788: [Poi2012]Festival

Time Limit: 30 Sec  Memory Limit: 64 MB

[ Submit][ Status][ Discuss]

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。容易發現沒有更大的方案。

Source

差分限制建圖先 首先跑一遍Floyd，如果一個點到自己的距離都小于0了，NIE！ 然後tarjan縮點，可以想到各個環中各不影響（其實是貪到） 在一個環中如何統計最大點數？ 我們可以知道，由于距離絕對值不大于1，假設在數軸上，一個環内所有點緊靠，那麼可以取的個數就是 環内最大距離+1 這道題我跑了16000+，有人跑了400+，都怪floyd太暴力了，由于我是懶癌是以。。就floyd吧 非常暴力的代碼，鄰接表還有個沒用的v，懶得去了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 600 + 5;
const int M = 2000000 + 5;
struct Edge{
	int to,next;
}e[M];
int last[N*2],cnt;
void insert( int u, int v, int w ){ e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt; }
int mp[N][N],dfn[N],low[N],scc,sta[N],cot,n,m1,m2,top,bel[N],ans; bool inq[N];
void tarjan( int x ){
	low[x] = dfn[x] = ++cot;
	sta[++top] = x; inq[x] = 1;
	for( int i = last[x]; i; i = e[i].next )
		if( !dfn[e[i].to] ) tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]);
		else if( inq[e[i].to] ) low[x] = min(low[x],dfn[e[i].to]);
	if( dfn[x] == low[x] ){
		int now = 0; scc++;
		while( now != x ){
			now = sta[top--];
			bel[now] = scc;
			inq[now] = 0;
		}
	}
}
int main(){
	scanf("%d%d%d", &n, &m1, &m2);
	memset(mp,0x3f,sizeof(mp));
	for( int i = 1,u,v; i <= m1; i++ ){
		scanf("%d%d", &u, &v);
		mp[u][v] = min(mp[u][v],1); mp[v][u] = min(mp[v][u],-1);
		insert( u, v, 1 ); insert( v, u, -1 );
	}
	for( int i = 1,u,v; i <= m2; i++ ){
		scanf("%d%d", &u, &v);
		mp[v][u] = min(mp[v][u],0);
		insert( v, u, 0 );
	}
	for( int i = 1; i <= n; i++ ) mp[i][i] = 0;
	for( int k = 1; k <= n; k++ )
		for( int i = 1; i <= n; i++ )
			for( int j = 1; j <= n; j++ )
				mp[i][j] = min( mp[i][j], mp[i][k]+mp[k][j] );
	for( int i = 1; i <= n; i++ ) if( mp[i][i] < 0 ){ puts("NIE"); return 0; }
	for( int i = 1; i <= n; i++ ) if( !dfn[i] ) tarjan(i);
	for( int i = 1; i <= scc; i++ ){
		int now = 0;
		for( int j = 1; j <= n; j++ )
			if( bel[j] == i )
				for( int k = 1; k <= n; k++ )
					if( bel[k] == i )
					 now = max(now,mp[j][k]);
		ans += now+1;
	}
	printf("%d\n", ans);
	return 0;
}