poj 3683 2-SAT入门

原题模型:两者(A,B)不能同时取

 #include "cstdio"
#include "vector"
#include "stack"
#include "cstring"
using namespace std;
#define maxn 2010 int n,N,dfs_clock,scc_cnt,v,tt=;
char st[];
int S[maxn],T[maxn],D[maxn],pre[maxn],sccno[maxn],lowlink[maxn],id[maxn],cfl[maxn],color[maxn],done[maxn];
int G[maxn][maxn],G2[maxn][maxn];
stack<int> St; void tarjan(int u)
{
pre[u]=lowlink[u]=++dfs_clock;
St.push(u);
for (int i=;i<=G[u][];i++)
{
int v=G[u][i];
if (!pre[v])
{
tarjan(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
}
else if (!sccno[v])
{
lowlink[u]=min(lowlink[u],pre[v]);
}
}
if (lowlink[u]==pre[u])
{
scc_cnt++;
for (;;)
{
int x=St.top();
St.pop();
sccno[x]=scc_cnt;
if (x==u) break;
}
}
} void find_scc(int n)
{
dfs_clock=scc_cnt=;
memset(sccno,,sizeof(sccno));
memset(pre,,sizeof(pre));
for (int i=;i<=n;i++)
if (!pre[i])
tarjan(i);
} void add_edge(int x,int y)
{
G[x][]++;
G[x][G[x][]]=y;
} void _add_edge(int x,int y)
{
G2[x][]++;
G2[x][G2[x][]]=y;
} void solve()
{
//1->N:x[i] N+1->2N:not x[i]
v=N*;
for (int i=;i<=N;i++)
{
for (int j=i+;j<=N;j++)
{
if (min(S[i]+D[i],S[j]+D[j])>max(S[i],S[j])) //事件i和j不能同时满足,连边
{
add_edge(i,N+j);
add_edge(j,N+i);
}
if (min(S[i]+D[i],T[j])>max(S[i],T[j]-D[j]))
{
add_edge(i,j);
add_edge(N+j,N+i);
}
if (min(T[i],S[j]+D[j])>max(T[i]-D[i],S[j]))
{
add_edge(N+i,N+j);
add_edge(j,i);
}
if (min(T[i],T[j])>max(T[i]-D[i],T[j]-D[j]))
{
add_edge(N+i,j);
add_edge(N+j,i);
}
}
}
} void topsort(int x)
{
int j;
id[x] = -;
done[++tt]=x;
for(int k=;k<=G2[x][];k++)
{
j = G2[x][k];
id[j]--;
if( id[j] == ) topsort( j );
}
} void dfs( int i )
{
int j;
color[i] = ;
for(int k=;k<=G[i][];k++)
{
j = G2[i][k];
if( color[j] == ) dfs( j );
}
} void print( int aa, int bb )
{
if( aa / < ) printf( "" );
printf( "%d:", aa / );
if( aa % < ) printf( "" );
printf( "%d ", aa % );
if( bb / < ) printf( "" );
printf( "%d:", bb / );
if( bb % < ) printf( "" );
printf( "%d\n", bb % );
} int main()
{
scanf("%d",&N);
for( int i = ; i <= N; i++ ) //时间统一转化成分钟存储
{
scanf( "%s", st );
S[i] = ( st[]- )* + ( st[]- )*;
S[i] += ( st[]- )* + st[]-;
scanf( "%s", st );
T[i] = ( st[]- )* + ( st[]- )*;
T[i] += ( st[]- )* + st[]-;
scanf( "%d", &D[i] );
} solve();
find_scc(*N); for (int i=;i<=N;i++)
{
if (sccno[i]==sccno[N+i])
{
printf("NO\n");
return ;
}
} //printf("YES\n");
for (int i=;i<=*N;i++) //强连通分量缩点并对块反向连边
{
for (int j=;j<=G[i][];j++)
{
int tm=G[i][j];
if (sccno[i]!=sccno[tm])
{
_add_edge(sccno[tm],sccno[i]);
id[sccno[i]]++;
}
}
}
for (int i=;i<=scc_cnt;i++) //对缩点之后的块拓扑排序,
if (id[i]==)
topsort(i); for( int i = ; i <= N; i++ )
{
cfl[ sccno[i] ] = sccno[i+N];
cfl[ sccno[i+N] ] = sccno[i];
} for( int ii = ; ii <= scc_cnt; ii++ ) //按拓扑序对块染色,求方案
{
int i = done[ii]; //done[]:拓扑序列
if( color[i] != ) continue;
color[i] = ; //color[]=1:选刚开始的时段,S~S+D
dfs( cfl[i] ); //color[]=2:选结束的时段,T-D~T
}
printf("YES\n");
for( int i = ; i <= N; i++ )
if( color[ sccno[i] ] == )
print( S[i], S[i]+D[i] );
else
print( T[i]-D[i], T[i] ); return ;
} //一直觉得ICPC不应该是种功利性的东西,那样就彻底变味了,也没意义了
//今年要干就好好干吧,也许明年就不打了
//没办法,有些事太复杂
//反正个人认为几个真心的朋友比所谓的成绩重要得多得多。
//。
//就这样吧
上一篇:2016 Al-Baath University Training Camp Contest-1 H


下一篇:oracle数据库无法连接 The Network Adapter could not establish