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; }