POJ训练记录2
3613.Cow Relays
求经过n条边的最短路，floyd+倍增QAQ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<map> #include<cmath> #include<ctime> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define mod 1000000009 #define inf 1000000000 #define eps 1e-8 using namespace std; int n,m,T,S,E; int u[105],v[105],l[105]; vector<int>q; int H(int x) { return lower_bound(q.begin(),q.end(),x)-q.begin(); } struct M{ int v[205][205]; M(){ memset(v,127/2,sizeof(v)); } friend M operator*(M a,M b){ M c; for(int i=0;i<m;i++) for(int j=0;j<m;j++) for(int k=0;k<m;k++) c.v[i][j]=min(c.v[i][j],a.v[i][k]+b.v[k][j]); return c; } }a[105]; int main() { scanf("%d%d%d%d",&n,&T,&S,&E); for(int i=1;i<=T;i++) { scanf("%d%d%d",&l[i],&u[i],&v[i]); q.push_back(u[i]); q.push_back(v[i]); } sort(q.begin(),q.end()); q.erase(unique(q.begin(),q.end()),q.end()); for(int i=1;i<=T;i++) { int x=H(u[i]),y=H(v[i]); a[0].v[y][x]=a[0].v[x][y]=l[i]; } m=q.size();S=H(S);E=H(E); for(int i=1;i<=20;i++) a[i]=a[i-1]*a[i-1]; M ans=a[0]; n--; for(int i=20;i>=0;i--) if((1<<i)&n) ans=ans*a[i]; printf("%d\n",ans.v[S][E]); return 0; } |
2728.Desert King
最优比率生成树
分数规划
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define mod 1000000009 #define inf 1000000000 #define eps 1e-8 using namespace std; int n,cnt; int x[1005],y[1005],z[1005],last[1005]; double d[1005],mp[1005][1005],ans; bool vis[1005]; void prim() { for(int i=1;i<=n;i++) { d[i]=inf;vis[i]=0; } d[1]=0; for(int i=1;i<=n;i++) { int now=0;d[now]=inf; for(int j=1;j<=n;j++)if(d[j]<d[now]&&!vis[j])now=j; ans+=d[now];vis[now]=1; for(int j=1;j<=n;j++) if(mp[now][j]<d[j]&&!vis[j]) d[j]=mp[now][j]; } } double sqr(double x) { return x*x; } double dis(int a,int b) { return sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b])); } void cal(double mid) { ans=0; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) mp[i][j]=mp[j][i]=abs(z[i]-z[j])-mid*dis(i,j); prim(); } int main() { while(scanf("%d",&n)) { if(n==0)break; for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]); double l=0,r=1000; for(int i=1;i<=30;i++) { double mid=(l+r)/2; cal(mid); if(ans<0)r=mid; else l=mid; } printf("%.3f\n",l); } return 0; } |
1639.Picnic Planning
带度数限制的最小生成树
http://wenku.baidu.com/link?url=UKcnK1pZvaVwypQOrIFRTOPzM4edIlBmqvnZjZipGf2o_6u-aB1F2tFsMGdUQbA1O-96menmbgyxNoSoWKWBeJnr-RJKuG2yM4b6Jf7IvR3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define mod 1000000009 #define inf 1000000000 #define eps 1e-8 using namespace std; int n,m,K,ans; int dis[505],p[505][505]; int vis[505],pre[505],mn[505],mx[505],fa[505]; map<string,int>mp; void prim(int x,int id) { dis[x]=0;dis[0]=inf; while(1) { int now=0; for(int j=1;j<=n;j++) if(dis[j]<dis[now]&&!vis[j])now=j; if(now==0)break;vis[now]=id; ans+=dis[now]; for(int j=1;j<=n;j++) if(p[now][j]<dis[j]&&!vis[j]) { dis[j]=p[now][j]; pre[j]=now; } } } void dfs(int x) { for(int i=1;i<=n;i++) if(i!=fa[x]&&p[x][i]<inf&&(pre[x]==i||pre[i]==x)) { mx[i]=max(mx[x],p[x][i]); fa[i]=x; dfs(i); } } void solve() { vis[1]=n+1; for(int i=1;i<=n;i++)dis[i]=inf; int id=0; for(int i=1;i<=n;i++) if(!vis[i]) prim(i,++id); for(int i=2;i<=n;i++) if(p[1][i]<p[1][mn[vis[i]]]) mn[vis[i]]=i; for(int i=1;i<=id;i++) { int t=mn[i]; ans+=p[1][t]; p[1][t]=p[t][1]=inf; mx[t]=0;fa[t]=1; dfs(t); } K-=id; while(K--) { int now=0; for(int i=1;i<=n;i++) if(p[1][i]<inf&&mx[now]-p[1][now]<mx[i]-p[1][i]) now=i; if(mx[now]-p[1][now]<0)break; ans-=mx[now]-p[1][now]; p[1][now]=p[now][1]=inf; int t=0; for(int i=now;fa[i]!=1;i=fa[i]) if((t==0||p[t][fa[t]]<p[i][fa[i]])&&p[i][fa[i]]<inf) t=i; p[t][fa[t]]=p[fa[t]][t]=inf; mx[now]=0;fa[now]=1; dfs(now); } } int main() { while(scanf("%d",&m)!=EOF) { n=ans=0;mp.clear(); memset(p,127,sizeof(p)); memset(vis,0,sizeof(vis)); memset(pre,0,sizeof(pre)); memset(mx,0,sizeof(mx)); memset(mn,0,sizeof(mn)); string a,b;int x; mp["Park"]=++n; for(int i=1;i<=m;i++) { cin>>a;cin>>b;scanf("%d",&x); if(!mp[a])mp[a]=++n; if(!mp[b])mp[b]=++n; p[mp[a]][mp[b]]=p[mp[b]][mp[a]]=x; } scanf("%d",&K); solve(); printf("Total miles driven: %d\n",ans); } return 0; } |
2749.Building roads
二分+2-sat
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define p(x) x+n using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int l,r,mid; int n,A,B,cnt,scc,ind,top; int u[2005],v[2005],last[1005]; int low[1005],dfn[1005],q[1005],bl[1005]; bool inq[1005]; struct P{ int x,y; void r(){ scanf("%d%d",&x,&y); } }p[505]; struct edge{ int to,next; }e[5000005]; void insert(int u,int v) { e[++cnt]=(edge){v,last[u]};last[u]=cnt; } int dis(int a,int b) { return abs(p[a].x-p[b].x)+abs(p[a].y-p[b].y); } void build() { cnt=0; memset(last,0,sizeof(last)); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { if(dis(i,n+1)+dis(j,n+1)>mid)insert(i,p(j)),insert(j,p(i)); if(dis(i,n+2)+dis(j,n+2)>mid)insert(p(i),j),insert(p(j),i); if(dis(i,n+1)+dis(n+1,n+2)+dis(n+2,j)>mid) insert(i,j),insert(p(j),p(i)); if(dis(i,n+2)+dis(n+1,n+2)+dis(n+1,j)>mid) insert(p(i),p(j)),insert(j,i); } for(int i=1;i<=A;i++) { int a=u[i],b=v[i]; insert(a,p(b)); insert(p(a),b); insert(b,p(a)); insert(p(b),a); } for(int i=1;i<=B;i++) { int a=u[i+A],b=v[i+A]; insert(a,b); insert(b,a); insert(p(a),p(b)); insert(p(b),p(a)); } } void tarjan(int x) { dfn[x]=low[x]=++ind; inq[x]=1;q[++top]=x; for(int i=last[x];i;i=e[i].next) if(!dfn[e[i].to]) tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]); else if(inq[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); if(low[x]==dfn[x]) { int now=-1; scc++; while(now!=x) { now=q[top--];inq[now]=0; bl[now]=scc; } } } bool check() { scc=top=ind=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); for(int i=1;i<=n+n;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;i++) if(bl[i]==bl[p(i)])return 0; return 1; } int main() { scanf("%d%d%d",&n,&A,&B); p[n+1].r();p[n+2].r(); for(int i=1;i<=n;i++)p[i].r(); for(int i=1;i<=A;i++)scanf("%d%d",&u[i],&v[i]); for(int i=1;i<=B;i++)scanf("%d%d",&u[A+i],&v[A+i]); r=4000000; int ans=-1; while(l<=r) { mid=(l+r)/2; build(); if(check())ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans); return 0; } |
2054.Color a Tree
神奇的贪心，题解到处是
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,rt,cnt; int last[1005],fa[1005]; int size[1005],r[1005],nxt[1005]; ll w[1005],sum[1005]; bool vis[1005]; struct edge{ int to,next; }e[2005]; void insert(int u,int v) { e[++cnt]=(edge){v,last[u]};last[u]=cnt; e[++cnt]=(edge){u,last[v]};last[v]=cnt; } void dfs(int x) { for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa[x]) { fa[e[i].to]=x; dfs(e[i].to); } } int mx() { int t=-1; for(int i=1;i<=n;i++) if(!vis[i]) { if(t==-1)t=i; else if((double)sum[t]/size[t]<(double)sum[i]/size[i])t=i; } return t; } int main() { while(scanf("%d%d",&n,&rt)) { if(n==0)return 0; cnt=0;memset(last,0,sizeof(last)); memset(nxt,0,sizeof(nxt)); memset(vis,0,sizeof(vis)); memset(fa,0,sizeof(fa)); for(int i=1;i<=n;i++)w[i]=sum[i]=read(); for(int i=1;i<=n;i++)r[i]=i,size[i]=1; for(int i=1;i<n;i++) { int u,v;scanf("%d%d",&u,&v); insert(u,v); } dfs(rt);vis[rt]=1; for(int i=1;i<n;i++) { int t=mx(),f=fa[t];vis[t]=1; nxt[r[f]]=t;r[f]=r[t]; for(int j=1;j<=n;j++) if(fa[j]==t)fa[j]=f; sum[f]+=sum[t]; size[f]+=size[t]; } int t=0;ll ans=0; for(int i=rt;i;i=nxt[i]) ans+=(++t)*w[i]; printf("%lld\n",ans); } return 0; } |
1182.食物链
带权？并查集
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans; int d[50005],fa[50005]; //x=y x->y y->x int find(int x) { if(x==fa[x])return x; int t=fa[x];fa[x]=find(fa[x]); d[x]=(d[x]+d[t])%3; return fa[x]; } void un(int x,int y,int f) { int fx=find(x),fy=find(y); fa[fx]=fy; d[fx]=(d[y]-f-d[x]+3)%3; } int main() { n=read();m=read(); int f,u,v; for(int i=1;i<=n;i++)fa[i]=i; while(m--) { f=read(),u=read(),v=read(); if(u>n||v>n||(f==2&&u==v))ans++; else { if(find(u)==find(v)) { if(f==1&&d[u]!=d[v])ans++; if(f==2&&(d[u]+1)%3!=d[v])ans++; } else un(u,v,f-1); } } printf("%d\n",ans); return 0; } |
Subscribe
计数器 9774024
OI 课件=>
OI 课件=>