3.13 欧拉回路和欧拉路径
3.13.1 1123. 铲雪车
代码：
#include<bits/stdc++.h> using namespace std; int main() { double x1,y1,x2,y2; cin>>x1>>y1; double sum=0; while(cin>>x1>>y1>>x2>>y2) { double dx=x1-x2; double dy=y1-y2; sum+=sqrt(dx*dx+dy*dy)*2; } int minutes=round(sum/1000/20*60); int hours=minutes/60; minutes%=60; printf("%d:%02d\n",hours,minutes); return 0; }
3.13.2 1184. 欧拉回路
代码：
#include<bits/stdc++.h> using namespace std; const int N=100010,M=400010; int type; int n,m; int ans[M],cnt; int din[N],dout[N]; int h[N],e[M],ne[M],idx; bool used[M]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u) { for(int &i=h[u];i!=-1;) { if(used[i]) { i=ne[i]; continue; } used[i]=true; if(type==1) used[i^1]=true; int t; if(type==1) { t=i/2+1; if(i&1) t=-t; } else t=i+1; int j=e[i]; i=ne[i]; dfs(j); ans[++cnt]=t; } } int main() { memset(h,-1,sizeof h); cin>>type; cin>>n>>m; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; add(a,b); if(type==1) add(b,a); din[b]++,dout[a]++; } if(type==1) { for(int i=1;i<=n;i++) { if(din[i]+dout[i]&1) { cout<<"NO"<<endl; return 0; } } } else { for(int i=1;i<=n;i++) { if(din[i]!=dout[i]) { cout<<"NO"<<endl; return 0; } } } for(int i=1;i<=n;i++) { if(h[i]!=-1) { dfs(i); break; } } if(cnt<m) { cout<<"NO"<<endl; return 0; } cout<<"YES"<<endl; for(int i=cnt;i>0;i--) cout<<ans[i]<<" "; return 0; }
3.13.3 1124. 骑马修栅栏
代码：
#include<bits/stdc++.h> using namespace std; const int N=510,M=1100; int n=500,m; int g[N][N]; int ans[M],cnt; int d[N]; void dfs(int u) { for(int i=1;i<=n;i++) { if(g[u][i]) { g[u][i]--,g[i][u]--; dfs(i); } } ans[++cnt]=u; } int main() { cin>>m; while(m--) { int a,b; cin>>a>>b; g[a][b]++,g[b][a]++; d[a]++,d[b]++; } int start=1; while(!d[start]) start++; for(int i=1;i<=n;i++) { if(d[i]%2) { start=i; break; } } dfs(start); for(int i=cnt;i>0;i--) cout<<ans[i]<<endl; return 0; }
3.13.4 1185. 单词游戏
代码：
#include<bits/stdc++.h> using namespace std; const int N=30; int t,n; int din[N],dout[N]; int p[N]; bool st[N]; int findP(int x) { if(p[x]!=x) return p[x]=findP(p[x]); return p[x]; } int main() { cin>>t; while(t--) { cin>>n; memset(din,0,sizeof din); memset(dout,0,sizeof dout); memset(st,0,sizeof st); for(int i=0;i<26;i++) p[i]=i; string str; for(int i=0;i<n;i++) { cin>>str; int a=str[0]-'a',b=str[str.length()-1]-'a'; dout[a]++,din[b]++; st[a]=true,st[b]=true; p[findP(a)]=findP(b); } bool flag1=true,flag2=true; int start=0,ed=0; for(int i=0;i<26;i++) { if(din[i]!=dout[i]) { flag1=false; if(din[i]-dout[i]==1) ed++; else if(dout[i]-din[i]==1) start++; else { flag2=false; break; } } } int t=findP(0); for(int i=1;i<26;i++) { if(st[i]&&findP(i)!=t) { flag1=false; break; } } if(flag1||flag2&&start==1&&ed==1) cout<<"Ordering is possible."<<endl; else cout<<"The door cannot be opened."<<endl; } return 0; }
3.14 拓扑排序
3.14.1 1191. 家谱树
代码：
#include<bits/stdc++.h> using namespace std; const int N=110,M=10010; int n; int d[N]; vector<int> ans; int h[N],e[M],ne[M],idx; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void topsort() { queue<int> q; for(int i=1;i<=n;i++) { if(d[i]==0) q.push(i); } while(q.size()) { int t=q.front(); q.pop(); ans.push_back(t); for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; d[j]--; if(d[j]==0) q.push(j); } } } int main() { memset(h,-1,sizeof h); cin>>n; for(int i=1;i<=n;i++) { while(true) { int x; cin>>x; if(x==0) break; add(i,x); d[x]++; } } topsort(); for(int i=0;i<ans.size();i++) { cout<<ans[i]<<" "; } return 0; }
3.14.2 1192. 奖金
代码：
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N=10010,M=20010; int n,m; int d[N]; int h[N],e[M],ne[M],idx; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int topsort() { int res=0,cnt=0; queue<PII> q; for(int i=1;i<=n;i++) { if(d[i]==0) { q.push(make_pair(i,100)); res+=100; cnt++; } } while(q.size()) { PII t=q.front(); q.pop(); for(int i=h[t.first];i!=-1;i=ne[i]) { int j=e[i]; d[j]--; if(d[j]==0) { res+=t.second+1; q.push(make_pair(j,t.second+1)); cnt++; } } } if(cnt<n) return -1; return res; } int main() { memset(h,-1,sizeof h); cin>>n>>m; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; add(b,a); d[a]++; } int t=topsort(); if(t==-1) cout<<"Poor Xed"<<endl; else cout<<t<<endl; return 0; }
3.14.3 164. 可达性统计
代码：
#include<bits/stdc++.h> using namespace std; const int N=30010; int n,m; int d[N]; vector<int> seq; bitset<N> f[N]; int h[N],e[N],ne[N],idx; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void topsort() { queue<int> q; for(int i=1;i<=n;i++) { if(d[i]==0) { q.push(i); seq.push_back(i); } } while(q.size()) { int t=q.front(); q.pop(); for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; d[j]--; if(d[j]==0) { q.push(j); seq.push_back(j); } } } } int main() { ios::sync_with_stdio(0); memset(h,-1,sizeof h); cin>>n>>m; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; add(a,b); d[b]++; } topsort(); for(int i=n-1;i>=0;i--) { int j=seq[i]; f[j][j]=1; for(int k=h[j];k!=-1;k=ne[k]) f[j]|=f[e[k]]; } for(int i=1;i<=n;i++) cout<<f[i].count()<<endl; return 0; }
3.14.4 456. 车站分级
代码：
#include<bits/stdc++.h> using namespace std; const int N=2010,M=1000010; int n,m; int d[N]; bool stop[N]; vector<int> seq; int dis[N]; int h[N],e[M],w[M],ne[M],idx; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void topsort() { queue<int> q; for(int i=1;i<=n+m;i++) { if(d[i]==0) { q.push(i); seq.push_back(i); } } while(q.size()) { int t=q.front(); q.pop(); for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; d[j]--; if(d[j]==0) { q.push(j); seq.push_back(j); } } } } int main() { memset(h,-1,sizeof h); cin>>n>>m; for(int i=1;i<=m;i++) { int s; cin>>s; int start,ed; memset(stop,0,sizeof stop); for(int j=0;j<s;j++) { int x; cin>>x; if(j==0) start=x; if(j==s-1) ed=x; stop[x]=true; } int vir=n+i; for(int j=start;j<=ed;j++) { if(stop[j]) { add(vir,j,1); d[j]++; } else { add(j,vir,0); d[vir]++; } } } topsort(); for(int i=1;i<=n;i++) dis[i]=1; for(int i=0;i<seq.size();i++) { int t=seq[i]; for(int j=h[t];j!=-1;j=ne[j]) { int k=e[j]; dis[k]=max(dis[k],dis[t]+w[j]); } } set<int> eq; for(int i=1;i<=n;i++) eq.insert(dis[i]); cout<<eq.size(); return 0; }
