{"id":49,"date":"2009-12-12T14:32:00","date_gmt":"2009-12-12T06:32:00","guid":{"rendered":"http:\/\/localhost\/?p=49"},"modified":"2009-12-12T14:32:00","modified_gmt":"2009-12-12T06:32:00","slug":"usaco_2004_feb_2","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=49","title":{"rendered":"USACO 2004 Feb (2)"},"content":{"rendered":"

1986.Distance Queries
\u5927\u610f\uff1a
\u7ed9\u4e00\u9897\u6811\u3002\u3002\u6bcf\u6b21\u8be2\u95ee\u4e24\u70b9\u4e4b\u95f4\u7684\u8ddd\u79bb\u3002\u3002
\u5f88\u660e\u663e\u662f\u8981\u6c42lca\u7684\u3002\u3002\u53c8\u4e0d\u662f\u8981\u6c42\u5728\u7ebf\u7b97\u6cd5\u3002\u3002\u4e8e\u662f\u6211\u5c31\u7528tarjan\u4e86\u3002\u3002
#include<cstdio>
#include<utility>
#include<vector>
using namespace std;
const int maxn=40000;
typedef pair<int,int> pi;
int F[maxn];
inline void makeset(int x)
{
F[x]=x;
}
int find(int x)
{
if(x!=F[x]) F[x]=find(F[x]);
return F[x];
}
void Union(int x,int y)
{
x=find(x);y=find(y);
F[y]=x;
}
int cnt=0;
vector<pi> Ask[maxn],E[maxn];
int Ans[maxn],Dep[maxn];
bool vis[maxn]={0};
void addQuery(int x,int y)
{
Ask[x].push_back(pi(y,cnt));
Ask[y].push_back(pi(x,cnt));
cnt++;
}
void addEdge(int s,int t,int c)
{
E[s].push_back(pi(t,c));
E[t].push_back(pi(s,c));
}
int n,m,k;
void dfs(int x,int dep)
{
vis[x]=true;
Dep[x]=dep;
makeset(x);
for(int v,i=0;i<E[x].size();i++)
if(!vis[v=E[x][i].first])
{
dfs(v,dep+E[x][i].second);
Union(x,v);
}
for(int lca,v,i=0;i<Ask[x].size();i++)
if(vis[v=Ask[x][i].first])
{
lca=find(v);
Ans[Ask[x][i].second]=Dep[x]+Dep[v]-2*Dep[lca];
}
}
int main()
{
scanf("%d %d",&n,&m);
int s,t,l;char c;
while(m–)
{
scanf("%d %d %d %c",&s,&t,&l,&c);s–;t–;
addEdge(s,t,l);
}
scanf("%d",&k);
for(int i=0;i<k;i++)
{
scanf("%d %d",&s,&t);s–;t–;
addQuery(s,t);
}
dfs(0,0);
for(int i=0;i<k;i++)
{
printf<\/a>("%dn",Ans[i]);
}
}1987.Distance Statistics
\u8fd9\u9053\u6709\u70b9\u610f\u601d\uff1a
\u7ed9\u4e00\u9897\u6811\u3002\u3002\u6c42\u51fa\u5176\u4e2d\u8ddd\u79bb\u4e0d\u8d85\u8fc7K\u7684\u70b9\u6709\u591a\u5c11\u5bf9\u3002\u3002
\u660e\u663e\u662f\u8981\u7528\u5206\u6cbb\u3002\u3002\u9996\u5148\u591a\u53c9\u8f6c\u4e8c\u53c9\u3002\u3002\u6240\u6709\u70b9\u5230\u5144\u5f1f\u7684\u8fb9\u957f\u5ea6\u90fd\u4e3a0\u3002\u3002
\u4e4b\u6240\u4ee5\u8981\u591a\u53c9\u8f6c\u4e8c\u53c9\u662f\u56e0\u4e3a\u5982\u679c\u4e0d\u8f6c\u7684\u8bdd\u3002\u3002\u6709\u4e9b\u60c5\u51b5\uff08\u4f8b\u5982\u661f\u5f62\u6811\u3002\u3002\uff09\u4f60\u5c31\u60b2\u5267\u4e86\u3002\u3002
\u8fd9\u6837\u4e24\u70b9\u4e4b\u95f4\u7684\u8ddd\u79bb\u8fd8\u662f\u4e0d\u53d8\u7684\u3002\u3002
\u7136\u540e\u7528\u57fa\u4e8e\u8fb9\u7684\u5206\u652f\u3002\u3002\u6bcf\u6b21\u627e\u51fa\u4e2d\u5fc3\u8fb9\u3002\u3002\u518d\u5206\u6210\u4e24\u68f5\u5b50\u6811\u3002\u3002
\u7136\u540e\u4e24\u4e2a\u70b9\u90fd\u5728\u5b50\u6811\u5185\u90e8\u7684\u53ef\u4ee5\u9012\u5f52\u89e3\u51b3\u3002\u3002\u9700\u8981\u7b97\u7684\u662f\u4e24\u4e2a\u70b9\u5728\u4e0d\u540c\u5b50\u6811\u7684\u3002\u3002
\u4e24\u4e2a\u5b50\u6811\u6240\u6709\u8282\u70b9\u90fd\u6309\u5230\u6839\u7684\u8ddd\u79bb\u6392\u5e8f\u3002\u3002\u7136\u540e\u5c31\u53ef\u4ee5\u626b\u63cf\u4e86\u3002\u3002
\u53ef\u60dc\u6211\u7684Code\u5199\u6b21\u4e86\u3002\u3002\u65f6\u95f4\u8d85\u4e861\u500d\u3002\u3002\u9700\u8981\u53bb\u6539\u6539\u3002\u3002
\u6ca1AC\u5c31\u4e0d\u53d1\u4e86\u3002\u3002 <\/p>\n","protected":false},"excerpt":{"rendered":"

1986.Distance Queries\u5927\u610f\uff1a\u7ed9\u4e00\u9897\u6811\u3002\u3002\u6bcf\u6b21\u8be2\u95ee\u4e24\u70b9\u4e4b\u95f4\u7684\u8ddd\u79bb\u3002\u3002\u5f88\u660e\u663e\u662f\u8981\u6c42lca\u7684\u3002\u3002\u53c8\u4e0d\u662f\u8981\u6c42\u5728\u7ebf\u7b97\u6cd5\u3002\u3002\u4e8e\u662f\u6211\u5c31\u7528tarjan\u4e86\u3002\u3002#include<cstdio>#include<utility>#include<vector>using namespace std;const int maxn=40000;typedef pair<int,int> pi;int F[maxn];inline void makeset(int x){ F[x]=x;}int find(int x){ if(x!=F[x]) F[x]=find(F[x]); return F[x];}void Union(int x,int y){ x=find(x);y=find(y); F[y]=x;}int cnt=0;vector<pi> Ask[maxn],E[maxn];int Ans[maxn],Dep[maxn];bool vis[maxn]={0};void addQuery(int x,int y){ Ask[x].push_back(pi(y,cnt)); Ask[y].push_back(pi(x,cnt)); cnt++;}void addEdge(int s,int t,int c){ E[s].push_back(pi(t,c)); E[t].push_back(pi(s,c));}int n,m,k;void dfs(int x,int dep){ vis[x]=true; Dep[x]=dep; makeset(x); for(int v,i=0;i<E[x].size();i++) if(!vis[v=E[x][i].first]) { dfs(v,dep+E[x][i].second); Union(x,v); } for(int […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/49"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=49"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/49\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=49"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=49"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=49"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}