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

\u8fd9\u7edd\u5bf9\u662f\u6811\u7a9d\u3002\u3002\u5168\u662f\u5173\u4e8e\u6811\u7684\u9898\u76ee\u3002\u3002\u3002\u5012\u3002\u3002
1984.Navigation Nightmare
\u5927\u610f:
\u5c31\u662f\u4e00\u4e2a\u5730\u56fe\u3002\u3002\u6bcf\u6b21\u544a\u8bc9\u4f60\u4e00\u4e2a\u70b9\u76f8\u5bf9\u4e8e\u53e6\u4e00\u4e2a\u70b9\u7684\u5750\u6807\u3002\u3002\u7136\u540e\u6709\u4e00\u4e9b\u8be2\u95ee\u3002\u3002
\u90fd\u662f\u95ee\u4e24\u4e2a\u70b9\u4e4b\u95f4\u7684\u66fc\u54c8\u987f\u8ddd\u79bb\u662f\u591a\u5c11\u3002\u3002\u5982\u679c\u4fe1\u606f\u4e0d\u591f\u5c31\u8f93\u51fa-1\u3002\u3002
\u597d\u50cf\u6709\u70b9\u96be\u3002\u3002\u5982\u679c\u4e0d\u662f\u52a8\u6001\u67e5\u8be2\u7684\u8bdd\u53ea\u597d\u7b97\u51fa\u6bcf\u4e2a\u70b9\u7684\u5750\u6807\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u4f46\u8fd9\u91cc\u662f\u52a8\u6001\u7684\u3002
\u5f88\u9ebb\u70e6\u3002\u3002\u6211\u60f3\u4e86\u60f3\u53d1\u73b0\u662f\u53ef\u4ee5\u7528\u5e76\u67e5\u96c6\u505a\u7684\u3002\u3002
\u5bf9\u6bcf\u4e2a\u70b9i\u3002F[i]\u662f\u5176\u7236\u4eb2\u3002\u3002D[i]\u662f\u76f8\u5bf9\u4e8e\u5176\u7236\u4eb2\u4ed6\u7684\u5750\u6807\u3002\u3002
\u90a3\u4e48\u5728\u8def\u5f84\u538b\u7f29\u7684\u65f6\u5019\u53ef\u4ee5\u987a\u4fbf\u7ef4\u62a4D[i]\u3002\u3002
\u5bf9\u4e8e\u4e00\u4e2a\u70b9Find\u4e00\u4e0b\u5c31\u53ef\u4ee5\u7b97\u51fa\u5176\u5bf9\u4e8e\u6839\u7684\u5750\u6807\u3002\u3002\u67e5\u8be2\u5982\u679c\u6839\u4e0d\u540c\u5219\u4e0d\u77e5\u9053\u3002\u3002
\u8fde\u63a5\u7684\u65f6\u5019\u8bb0\u5f97\u8981\u8f6c\u6362\u4e00\u4e0b\u76f8\u5bf9\u7684\u5750\u6807\u3002\u3002
\u5426\u5219\u5c31\u662f\u5750\u6807\u7684\u66fc\u54c8\u987f\u8ddd\u79bb\u3002\u3002
Code\u3002\u3002
#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
const int maxn=40000;
typedef pair<int,int> pi;
inline int abs(int x){return x<0?-x:x;}
inline pi operator+(const pi&x,const pi&y)
{
return pi(x.first+y.first,x.second+y.second);
}
inline pi operator-(const pi&x,const pi&y)
{
return pi(x.first-y.first,x.second-y.second);
}
inline int dist(const pi&x,const pi&y)
{
return abs(x.first-y.first)+abs(x.second-y.second);
}
pi get(int l,char d)
{
switch(d)
{
case ‘N’:return pi(0,l);
case ‘S’:return pi(0,-l);
case ‘E’:return pi(l,0);
case ‘W’:return pi(-l,0);
}
}
struct data
{
int s,t,l;
char d;
}D[maxn];
struct query
{
int x,y,t,n;
bool operator<(const query&x) const
{return t<x.t;}
}Q[maxn];
int n,m,k;
void init()
{
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++)
scanf("%d %d %d %c",&D[i].s,&D[i].t,&D[i].l,&D[i].d);
scanf("%d",&k);
for(int i=0;i<k;i++)
scanf("%d %d %d",&Q[i].x,&Q[i].y,&Q[i].t),Q[i].n=i;
sort(Q,Q+k);
}
int F[maxn];
pi P[maxn];
void set(int n)
{
for(int i=0;i<n;i++)
F[i]=i,P[i]=pi(0,0);
}
void find(int x)
{
if(x!=F[x])
find(F[x]),P[x]=P[x]+P[F[x]],F[x]=F[F[x]];
}
void Union(int x,int y,pi d)
{
find(x);d=d-P[x];x=F[x];
find(y);d=d+P[y];y=F[y];
F[x]=y;P[x]=d;
}
int ask(int x,int y)
{
find(x);find(y);
if(F[x]!=F[y]) return -1;
return dist(P[x],P[y]);
}
void deal(data x)
{
x.s–;x.t–;
pi d=get(x.l,x.d);
Union(x.s,x.t,d);
}
int main()
{
init();
set(n);
int last=0;
int Ans[maxn];
for(int i=0;i<k;i++)
{
for(int j=last;j<Q[i].t;j++)
{
deal(D[j]);
}
last=Q[i].t;Ans[Q[i].n]=ask(Q[i].x-1,Q[i].y-1);
}
for(int i=0;i<k;i++)
printf<\/a>("%dn",Ans[i]);
}1985.Cow Marathon
\u5927\u610f:
\u4e00\u9897\u6811\uff0c\u6c42\u5176\u4e2d\u8ddd\u79bb\u6700\u8fdc\u7684\u4e24\u70b9\u7684\u8ddd\u79bb\u3002\u3002
\u7ecf\u5178\u7b97\u6cd5\u3002\u3002\u4e24\u6b21dfs\u3002\u3002
\u4e5f\u53ef\u4ee5DP\u3002\u3002
\u6c34\u9898\u5c31\u4e0d\u591a\u8bf4\u4e86\u3002\u3002\u3002
Code\u3002\u3002
#include<cstdio>
#include<utility>
#include<vector>
#include<cstring>
using namespace std;
typedef pair<int,int> pi;
typedef vector<pi>::iterator it;
const int maxn=40000;
int n,m;
vector<pi> E[maxn];
inline void add(int s,int t,int c)
{
E[s].push_back(pi(t,c));
E[t].push_back(pi(s,c));
}
void init()
{
scanf("%d %d",&n,&m);int s,t,c;char a;
while(m–)
{
scanf("%d %d %d %c",&s,&t,&c,&a);s–;t–;
add(s,t,c);
}
}
int dist[maxn];
bool vis[maxn];
void dfs(int x,int d)
{
vis[x]=true;dist[x]=d;
for(it i=E[x].begin();i!=E[x].end();i++)
if(!vis[i->first])
{
dfs(i->first,d+i->second);
}
}
int find(int t)
{
memset(vis,false,sizeof(vis));
dfs(t,0);int mi=0;
for(int i=1;i<n;i++)
if(dist[i]>dist[mi])
mi=i;
return mi;
}
int main()
{
init();
int t=find(0);
printf<\/a>("%dn",dist[find(t)]);
} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u8fd9\u7edd\u5bf9\u662f\u6811\u7a9d\u3002\u3002\u5168\u662f\u5173\u4e8e\u6811\u7684\u9898\u76ee\u3002\u3002\u3002\u5012\u3002\u30021984.Navigation Nightmare\u5927\u610f:\u5c31\u662f\u4e00\u4e2a\u5730\u56fe\u3002\u3002\u6bcf\u6b21\u544a\u8bc9\u4f60\u4e00\u4e2a\u70b9\u76f8\u5bf9\u4e8e\u53e6\u4e00\u4e2a\u70b9\u7684\u5750\u6807\u3002\u3002\u7136\u540e\u6709\u4e00\u4e9b\u8be2\u95ee\u3002\u3002\u90fd\u662f\u95ee\u4e24\u4e2a\u70b9\u4e4b\u95f4\u7684\u66fc\u54c8\u987f\u8ddd\u79bb\u662f\u591a\u5c11\u3002\u3002\u5982\u679c\u4fe1\u606f\u4e0d\u591f\u5c31\u8f93\u51fa-1\u3002\u3002\u597d\u50cf\u6709\u70b9\u96be\u3002\u3002\u5982\u679c\u4e0d\u662f\u52a8\u6001\u67e5\u8be2\u7684\u8bdd\u53ea\u597d\u7b97\u51fa\u6bcf\u4e2a\u70b9\u7684\u5750\u6807\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u4f46\u8fd9\u91cc\u662f\u52a8\u6001\u7684\u3002\u5f88\u9ebb\u70e6\u3002\u3002\u6211\u60f3\u4e86\u60f3\u53d1\u73b0\u662f\u53ef\u4ee5\u7528\u5e76\u67e5\u96c6\u505a\u7684\u3002\u3002\u5bf9\u6bcf\u4e2a\u70b9i\u3002F[i]\u662f\u5176\u7236\u4eb2\u3002\u3002D[i]\u662f\u76f8\u5bf9\u4e8e\u5176\u7236\u4eb2\u4ed6\u7684\u5750\u6807\u3002\u3002\u90a3\u4e48\u5728\u8def\u5f84\u538b\u7f29\u7684\u65f6\u5019\u53ef\u4ee5\u987a\u4fbf\u7ef4\u62a4D[i]\u3002\u3002\u5bf9\u4e8e\u4e00\u4e2a\u70b9Find\u4e00\u4e0b\u5c31\u53ef\u4ee5\u7b97\u51fa\u5176\u5bf9\u4e8e\u6839\u7684\u5750\u6807\u3002\u3002\u67e5\u8be2\u5982\u679c\u6839\u4e0d\u540c\u5219\u4e0d\u77e5\u9053\u3002\u3002\u8fde\u63a5\u7684\u65f6\u5019\u8bb0\u5f97\u8981\u8f6c\u6362\u4e00\u4e0b\u76f8\u5bf9\u7684\u5750\u6807\u3002\u3002\u5426\u5219\u5c31\u662f\u5750\u6807\u7684\u66fc\u54c8\u987f\u8ddd\u79bb\u3002\u3002Code\u3002\u3002#include<cstdio>#include<utility>#include<algorithm>using namespace std;const int maxn=40000;typedef pair<int,int> pi;inline int abs(int x){return x<0?-x:x;}inline pi operator+(const pi&x,const pi&y){ return pi(x.first+y.first,x.second+y.second);}inline pi operator-(const pi&x,const pi&y){ return pi(x.first-y.first,x.second-y.second);}inline int dist(const pi&x,const pi&y){ return abs(x.first-y.first)+abs(x.second-y.second);}pi get(int l,char d){ switch(d) { case ‘N’:return pi(0,l); case ‘S’:return pi(0,-l); case ‘E’:return pi(l,0); case ‘W’:return pi(-l,0); }}struct data{ int s,t,l; char d;}D[maxn];struct query{ 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\/48"}],"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=48"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/48\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=48"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=48"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=48"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}