好久没写博客没好好打了。记录一下三道中档题。读题能读死。太⛏了。
A. Environment-Friendly Travel
题意：给定二维平面起点、终点，和一些中间点。可以通过最贵的方式从起点到中间点，从中间点到终点。中间点之间存在某些单价便宜的交通方式。费用为距离乘单价。
设置了一个最远距离，点之间距离为欧式距离向上取整。问从起点到终点不超过最远距离的最小费用。不存在输出-1.
想法：如果没有最远距离的限制，那这道题就是一个dijkstra最短路了。注意到最远距离不超过100，点也就1000个，那就存下到某个点距离为某数的合法状态，不断dijkstra bfs扩展即可。
我参考的网上的，用bfs求最短路，不太会分析复杂度V·E。的确跑的慢1000ms以上。测了C队的dijkstra跑的飞快100ms。
看来还是要堆优化。
#include <bits/stdc++.h> #ifndef ONLINE_JUDGE #define debug(x) cout << #x << ": " << x << endl #else #define debug(x) #endif using namespace std; typedef long long ll; const int maxn=1e3+7; const int maxe=1e6+7; const int inf=0x3f3f3f3f; const int mod=1e9+7; int dp[maxn][110],B,T,n; int c[110]; struct point { int x,y; }p[maxn]; vector<pair<int,int> >g[maxn]; int dist(int i,int j) { double dis=sqrt(double((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y))); return (int)ceil(dis); } struct node { int id,dis,cost,pre; }; struct edge { int to,nxt,dis,cost; }e[maxe<<1]; int head[maxn],tot=0; void addedge(int u,int v,int dis,int cost) { e[++tot].to=v; e[tot].dis=dis; e[tot].cost=cost; e[tot].nxt=head[u]; head[u]=tot; } int ans; void bfs(int s,int t) { queue<node>q; ans=inf; q.push({s,0,0,-1}); while(!q.empty()) { node cur=q.front();q.pop(); int u=cur.id; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if(v==cur.pre) continue; if(cur.dis+e[i].dis>B) continue; if(v==t) { ans=min(ans,cur.cost+e[i].cost); continue; } if(dp[v][cur.dis+e[i].dis]>cur.cost+e[i].cost) { dp[v][cur.dis+e[i].dis]=cur.cost+e[i].cost; q.push({v,cur.dis+e[i].dis,cur.cost+e[i].cost,u}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int xs,ys,xd,yd; cin>>xs>>ys>>xd>>yd; cin>>B>>c[0]>>T; for(int i=1;i<=T;++i) cin>>c[i]; cin>>n; for(int i=0,l,id,type;i<n;++i) { cin>>p[i].x>>p[i].y>>l; while(l--) { cin>>id>>type; g[i].push_back({id,type}); } } for(int i=0;i<n;++i) { for(int j=0;j<g[i].size();++j) { auto u=g[i][j]; int id=u.first,type=u.second,dis=dist(i,id); addedge(i,id,dis,c[type]*dis); addedge(id,i,dis,c[type]*dis); } } p[n]={xs,ys}; p[n+1]={xd,yd}; for(int i=0;i<n;++i) { int dis=dist(i,n); addedge(i,n,dis,dis*c[0]); addedge(n,i,dis,dis*c[0]); dis=dist(i,n+1); addedge(i,n+1,dis,dis*c[0]); addedge(n+1,i,dis,dis*c[0]); } int dis=dist(n,n+1); addedge(n,n+1,dis,dis*c[0]); addedge(n+1,n,dis,dis*c[0]); memset(dp,0x3f,sizeof(dp)); bfs(n,n+1); if(ans==inf) ans=-1; cout<<ans<<endl; return 0; }
G. Swapping Places
题意：S个动物名字，L种两两可以交换的关系(并不传递)，N个动物的序列。求字典序最小的动物名字序列。
想法：发现能交换是一种关系，不能交换也是一种关系，就是这些动物之间必然存在先后顺序，利用先后顺序，想到可以拓扑排序。然后O（N*S）建边，但要求字典序最小，需要处理出各个字符对应的字典序排名序号，同时拓扑排序的时候带权。
O（n*s+nlogn）。
#include <bits/stdc++.h> #ifndef ONLINE_JUDGE #define debug(x) cout << #x << ": " << x << endl #else #define debug(x) #endif using namespace std; typedef long long ll; const int maxn=2e5+7; const int inf=0x3f3f3f3f; const int mod=1e9+7; map<string,int>mp; int in[maxn],idx[maxn],last[220],g[220][220],s,l,n; vector<int>to[maxn]; string ans[maxn]; struct node { int id,val; bool operator < (const node &rhs) const { return val>rhs.val; } }; void topsort() { priority_queue<node>pq; for(int i=1;i<=n;++i) if(!in[i]) pq.push({i,idx[i]}); while(!pq.empty()) { node cur=pq.top();pq.pop(); cout<<ans[cur.val]<<' '; for(int i=0;i<to[cur.id].size();++i) { int v=to[cur.id][i]; in[v]--; if(!in[v]) pq.push({v,idx[v]}); } } cout<<endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>s>>l>>n; string str; for(int i=1;i<=s;++i) { cin>>str; mp[str]++; last[i]=-1; } int k=1; for(auto &u:mp) { u.second=k; ans[k]=u.first; k++; } for(int i=1;i<=l;++i) { cin>>str; int u=mp[str]; cin>>str; int v=mp[str]; g[u][v]=g[v][u]=1; } for(int i=1;i<=n;++i) { cin>>str; int now=mp[str]; idx[i]=now; for(int j=1;j<=s;++j) { if(g[j][now]) continue; if(last[j]==-1) continue; to[last[j]].push_back(i); in[i]++; } last[now]=i; } topsort(); return 0; }
K. Birdwatching
题意：挺绕的。就是求有向图到目标点T只有通过邻接边一条路的点。
想法：显然与T直接相连的点，是在我们的考虑范围中的，但并不是特别好搞，不能直接去掉这些边，再逐个dfs，会互相影响。
做法是找出直接相连的点，叫做嫌疑点，这些边不去连接。其他的边反向连接。然后对这些嫌疑点逐个dfs，并记录每个点能从反向建图后的几个嫌疑点到达。能从反向建图后的嫌疑点到达，说明这个点正向能到嫌疑点，也就顺势能到目标点。
能从多个嫌疑点到达，这样的点显然排除，dfs的同时防止环。
最后答案就是只能从一个嫌疑点到达目标点，即从自己到达目标点的嫌疑点就是答案。
#include <bits/stdc++.h> #ifndef ONLINE_JUDGE #define debug(x) cout << #x << ": " << x << endl #else #define debug(x) #endif using namespace std; typedef long long ll; const int maxn=2e5+7; const int inf=0x3f3f3f3f; const int mod=1e9+7; vector<int>g[maxn],ans; set<int>f[maxn],st; void dfs(int u,int t) { if(f[u].size()>1||f[u].count(t)) return; f[u].insert(t); for(auto it:g[u]) dfs(it,t); } int main() { int n,m,t; scanf("%d%d%d",&n,&m,&t); for(int i=1; i<=m; i++) { int u,v; scanf("%d%d",&u,&v); if(v==t) st.insert(u); else g[v].push_back(u); } for(auto &it:st) dfs(it,it); for(auto &it:st) if(f[it].size()==1) ans.push_back(it); printf("%d ",ans.size()); for(auto &it:ans) printf("%d ",it); return 0; }