运输计划noip

运输计划noip

靠！这道题TM搞了我好几天，真是烦死人！！！早上打了一个倍增的TM只有95分QAQ。。。

然后一气之下开始不断卡常，各种玄学优化，可是就是T。。TAT。。

可恶！晚上我就直接打了个tarjan，还好跑过了，可是打的我身心俱残！！！仿佛想起了打splay的岁月，各个代码3000+。。。

不过一次就打成功了，还算比较好吧。。。

先上95分的代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define maxn 600500
#define ll long long 
using namespace std;
struct st{ll u,v,next,val;
}s[maxn];struct qu{ll a,b,lca,len;
}quest[maxn];ll n,m,u,v,root,tot,val,head[maxn],ceng[maxn],fa[maxn][20],len[maxn],fedge[maxn],zou[maxn],cf[maxn],maxlen,l,r,ma;inline void add(ll u,ll v,ll val)
{tot++;s[tot].val = val;s[tot].u = u;s[tot].v = v;s[tot].next = head[u];head[u] = tot;
}inline void dfs(ll f,ll now)
{fa[now][0] = f;ceng[now] = ceng[f] + 1;for(ll i = head[now];i;i = s[i].next){v = s[i].v;if(!ceng[v]){fedge[v] = s[i].val;len[v] = len[now] + s[i].val;dfs(now,v);}}
}inline void init()
{for(ll j=1;(1<<j)<=n;j++){for(ll i=1;i<=n;i++){fa[i][j]=fa[fa[i][j-1]][j-1];}}    
}inline ll lca(ll a,ll b)
{if(ceng[a] > ceng[b]) swap(a,b);ll cha = ceng[b] - ceng[a];for(ll i = 0;(1 << i) <= cha;i++){if((1 << i) & cha) b = fa[b][i];}if(a!=b){for(ll i=(ll)log2(n);i>=0;i--){if(fa[a][i]!=fa[b][i]){a=fa[a][i];b=fa[b][i];}}a = fa[a][0];}return a;
}inline ll find(ll pos,ll num)
{ll val = cf[pos];zou[pos] = 1;for(ll i=head[pos];i;i=s[i].next){if(zou[s[i].v]) continue;val += find(s[i].v,num);}if(val >= num) ma = max(ma,fedge[pos]);return val;
}inline ll check(ll ans)
{memset(zou,0,sizeof(zou));memset(cf,0,sizeof(cf));ll ce = 0;for(ll i=1;i<=m;i++){if(quest[i].len > ans){cf[quest[i].a]++;cf[quest[i].b]++;cf[quest[i].lca] -= 2;ce++;}}ma = -1;find(1,ce);if(ma == -1) return 0;if(ans + ma >= maxlen) return 1;return 0;
}int main(){scanf("%lld%lld%",&n,&m);for(ll i=1;i<n;i++){scanf("%lld%lld%lld",&u,&v,&val);add(u,v,val);add(v,u,val);}dfs(0,1);init();for(ll i=1;i<=m;i++){scanf("%lld%lld",&u,&v);quest[i].a = u;quest[i].b = v;quest[i].lca = lca(u,v);quest[i].len = len[u] + len[v] - 2 * len[quest[i].lca];maxlen = max(maxlen , quest[i].len);}r = maxlen;while(l < r){ll mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}printf("%lld",l);
} 

 然后上个100 的！！！

#include<cstdio>
#include<algorithm>
#define maxn 300300 << 1
using namespace std;
int head_edge[maxn],head_quest[maxn],fedge[maxn],f[maxn],len[maxn],vis[maxn],cf[maxn],n,m,ma,maxlen,tot,u,v,val,l,r;struct st{int v,val,next;
}s[maxn];struct que{int u,v,lca,len,next;que *es;
}quest[maxn];inline int find(int x)
{if(f[x] == x) return x;f[x] = find(f[x]);return f[x];
}inline void add_edge(int u,int v,int val)
{tot++;s[tot].v = v;s[tot].val = val;s[tot].next = head_edge[u];head_edge[u] = tot;
}inline void add_quest(int u,int v)
{tot++;quest[tot].u = u;quest[tot].v = v;if(tot & 1)    quest[tot].es = &quest[tot + 1];else quest[tot].es = &quest[tot - 1];quest[tot].next = head_quest[u];head_quest[u] = tot;
}inline void dfs_tarjan(int father,int now)
{for(int i=head_edge[now];i;i=s[i].next){if(father == s[i].v) continue;fedge[s[i].v] = s[i].val;len[s[i].v] = len[now] + s[i].val;dfs_tarjan(now,s[i].v);}
}inline void lca_tarjan(int father,int now)
{for(int i=head_edge[now];i;i=s[i].next){if(s[i].v == father) continue;lca_tarjan(now,s[i].v);}for(int i=head_quest[now];i;i=quest[i].next){if(vis[quest[i].v]){quest[i].lca = find(quest[i].v);quest[i].len = len[quest[i].u] + len[quest[i].v] - 2 * len[quest[i].lca];quest[i].es -> lca = quest[i].lca;quest[i].es -> len = quest[i].len;maxlen = max(maxlen,quest[i].len);}}vis[now] = 1;f[now] = father;
}inline int dfs_check(int pos,int num)
{vis[pos] = 1;int val = cf[pos];for(int i=head_edge[pos];i;i=s[i].next){if(vis[s[i].v]) continue;val += dfs_check(s[i].v,num);}if(val >= num) ma = max(ma,fedge[pos]);return val;
}inline int check(int ans)
{for(int i=1;i<=n;i++){vis[i] = 0;cf[i] = 0;}int num = 0;ma = -1;for(int i=1;i<=m;i++){if(quest[i].len > ans){cf[quest[i].u]++;cf[quest[i].v]++;cf[quest[i].lca] -= 2;num++;}}if(!num) return 1;dfs_check(1,num);if(ma == -1 || ans + ma < maxlen) return 0;return 1;
}int main(){scanf("%d%d",&n,&m);for(int i=1;i<n;i++){scanf("%d%d%d",&u,&v,&val);add_edge(u,v,val);add_edge(v,u,val);}dfs_tarjan(0,1);tot = 0;for(int i=1;i<=n;i++) f[i] = i;for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);add_quest(u,v);add_quest(v,u);}lca_tarjan(0,1);for(int i=1;i<=m;i++) quest[i] = quest[i * 2];r = maxlen;l = max(0,r - 1000);while(l < r){int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}printf("%d",l);
}

转载于:.html