第一次考慮到輸出路徑點。。。。。
開始的時候本以為不用拓撲，而在見圖的時候全部建成無向圖。。。。結果不言而喻
部分代碼如下：
#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 閱讀(510)
評論(0) 編輯 收藏 引用