第一次考虑到输出路径点。。。。。
开始的时候本以为不用拓扑，而在见图的时候全部建成无向图。。。。结果不言而喻
部分代码如下：
#include<iostream>
#include<stack>
#include<vector>
#define MAXN 2100
using namespace std;
vector<int>v[MAXN],nv[MAXN],cont[MAXN];
int pre[MAXN],low[MAXN],id[MAXN];
int ans[MAXN],dfn[MAXN];
int cnt,scnt,n,m,N;
stack<int>ST;
struct NODE
{
int x,y;
}arr[MAXN];
void Tarjan(int x){
int t,i;
int min=low[x]=pre[x]=cnt++;
ST.push(x);
for(i=0;i<v[x].size();i++){
t=v[x][i];
if(pre[t]==-1)Tarjan(t);
if(low[t]<min)min=low[t];
}
if(min<low[x]){
low[x]=min;
return;
}
do{
id[t=ST.top()]=scnt;
low[t]=m;ST.pop();
}while(t!=x);
scnt++;
}
int SCC(){
scnt=cnt=0;
while(!ST.empty())ST.pop();
memset(pre,0xff,sizeof(pre));
memset(low,0,sizeof(low));
for(int i=0;i<m;i++)
if(pre[i]==-1)Tarjan(i);
for(int i=0;i<m;i++)
cont[id[i]].push_back(i);
return scnt;
}
void DFS(int k){
dfn[k]=cnt++;
for(int i=0;i<nv[k].size();i++){
int w=nv[k][i];
if(dfn[w]==-1)DFS(w);
}
ans[scnt++]=k;
}
void ColDFS(int k){
dfn[k]=2;
for(int i=0;i<nv[k].size();i++){
int w=nv[k][i];
if(dfn[w]==-1)ColDFS(w);
}
}
void GetOneAnswer(){
memset(dfn,0xff,sizeof(dfn));
for(int i=0;i<m;i++)
for(int j=0;j<v[i].size();j++){
int x=id[i],y=id[v[i][j]];
if(x!=y)nv[x].push_back(y);
}
cnt=scnt=0;
for(int i=0;i<N;i++)
if(dfn[i]==-1)DFS(i);
memset(dfn,0xff,sizeof(dfn));
for(int i=scnt-1;i>=0;i--)
if(dfn[ans[i]]==-1) {
int a=cont[ans[i]][0],b;
if(a<n)b=a+n;
else b=a-n;
dfn[ans[i]]=1;
if (dfn[id[b]]==-1)ColDFS(id[b]);
}
}
void PRINTF(){
printf("YES\n");
GetOneAnswer();
for(int i=0;i<n;i++){
int x=arr[i].x,y=arr[i].y;
int tx=arr[i+n].x,ty=arr[i+n].y;
if(dfn[id[i]]==2)printf("%02d:%02d %02d:%02d\n",x/60,x%60,y/60,y%60);
else printf("%02d:%02d %02d:%02d\n",tx/60,tx%60,ty/60,ty%60);
}
}
void solve(){
int i=0;
for(N=SCC();i<n;i++)
if(id[i]==id[n+i])break;
if(i==n)PRINTF();
else printf("NO\n");
}posted on 2009-06-07 10:39
KNIGHT 阅读(495)
评论(0) 编辑 收藏 引用