hogloidのブログ

へなちょこ

XIX OI Festival

問題分はこちら
http://wikiwiki.jp/poiwiki/?%CC%E4%C2%EA%B0%EC%CD%F7%2F%C2%E819%B2%F3%2FFestival%20%CC%E4%C2%EA
















































人iの到着時刻をCiとおくと、
aはbより1秒早い、という条件は
Ca=Cb-1
つまり、
Ca-Cb<=-1
Cb-Ca<=1
と表せる。

cはdより早い、という条件は、
Cc-Cd<=0
と表せる。

上の条件を、牛ゲー風にグラフにする。
(Ca-Cb<=-1 なら、b->aにコスト-1の辺を張る)
強連結成分ごとにグラフを分けて、それぞれの成分ごとの答えの和を求めればよい。
(別の強連結成分の人間の到着時刻は、自由に引き離せる)
上の条件を満たす中で、到着時刻の最大の差が強連結成分ごとの答え。
(強連結成分内での到着時刻に差があるとき、その間の整数の到着時刻を取る人間は常にいる)
これは、グラフの2点間の最短経路の長さの最大値。(蟻本Layoutみたいな感じで)
条件を満たせないときは、負閉路ができている。

強連結成分分解、負閉路検出、最短経路はすべてWarshall Floyd風にO(N^3)でできる。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
using namespace std;
static const int INF =500000000; 
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }
typedef long long int lint;
typedef pair<int,int> pi;

int g[605][605];
bool reach[605][605];//到着可能か
int n,m1,m2;

int done[605],mark[605];
int main(){
	cin>>n>>m1>>m2;
	REP(i,n) REP(j,n) g[i][j]=INF;
	REP(i,n) REP(j,n) g[i][i]=0;
	REP(i,m1){
		int a,b;cin>>a>>b;--a;--b;
		chmin(g[a][b],1);
		chmin(g[b][a],-1);
		reach[a][b]=reach[b][a]=true;
	}
	REP(i,m2){
		int a,b;cin>>a>>b;--a;--b;
		chmin(g[b][a],0);
		reach[b][a]=true;
	}

	REP(i,n) REP(j,n) REP(k,n){
		reach[j][k]|=(reach[j][i]&reach[i][k]);
		chmin(g[j][k],g[j][i]+g[i][k]);
	}

	REP(i,n) if(g[i][i]<0){
		puts("NIE");
		return 0;
	}
	
	int res=0;
	REP(i,n) if(!done[i]){
		memset(mark,0,sizeof(mark));

		REP(j,n) if(reach[i][j] && reach[j][i]) done[j]=mark[j]=1;
//相互に到着可能<->同じ強連結成分
		
		int tmp=0;
		REP(j,n) if(mark[j]) REP(k,n) if(mark[k]) chmax(tmp,g[j][k]);
//最大の最短経路の距離
		res+=tmp+1;
	}
	printf("%d\n",res);

	return 0;
}